这是一个创建于 1765 天前的主题，其中的信息可能已经有所发展或是发生改变。
面试遇到过的，给一组服务器 IP 和权重，然后根据权重随机返回服务器 IP 。例如，[{A,4},{B,4},{C,4},{D,1}]。看网上解法是将权重累加，然后用二分查找，看随机数落在哪个区间。但面试官要求用哈希表，而且是用 IP 做键值。有人知道怎么做的吗？
 | 1 impl OP s/键值 /键 |
 | 2 ytmsdy 2021-02-15 21:22:19 +08:00 把权重相加一下，例如帖子里面所说的 4+4+4+1，然后开一个长度为 13 的数组。 例如 [A,A,A,A,B,B,B,B,C,C,C,C,D] 一个请求过来以后，搞个随机数，然后 13 取模。余数是那个，就返回那个 IP 。 不知道有没有理解对。 |
 | 3 ccagml 2021-02-15 22:18:32 +08:00 via Android 一致性哈希，不知道有没有理解对 |
 | 4 Exple 2021-02-15 22:46:42 +08:00 via Android  1 |
 | 5 OldCarMan 2021-02-15 23:29:34 +08:00 不知道楼主说“IP 做键值”我理解成“IP 做哈希表的值”有没有错（如果是做键，我就有点不明白了）。如果是的话，个人觉得大概思路如#2 楼大哥所说，只不过根据 IP 的权重，同个 ip 值有多个不同键的记录，至于同个值的多条记录怎么表示，可以这样：[A1,IP1],[A2,IP1],[A3,IP1],[A4,IP1],[B1,IP2],[B2,IP2],[B3,IP1],[B4,IP1],[C1,IP3],[C2,IP3],[C3,IP3],[C4,IP3],[D1,IP4]。不过有点鸡肋，没其他需求的话，还不如直接如#2 楼大哥说的一样，直接用一个一维数组，在[0,总权重值-1]之间获取一个随机下标或者当前时间对总权重值取模。 |
| 6 impl OP |
 | 8 cassyfar 2021-02-16 06:42:45 +08:00 哈希就没法随机了。但是如果不随机，可以用 ring hash 。 |
 | 9 copper20 2021-02-16 09:49:11 +08:00 2 @impl 说的应该是带虚拟节点的一致性哈希。若一台服务器的权重为 n，可以把这台服务器看成 n 台虚拟的服务器，比如 {A,4} 这台服务器可以看成 A1 A2 A3 A4 四个虚拟节点。然后再把 A1 ... A4 B1 ... B4 C1 ... C4 D1 这些虚拟节点用哈希函数映射到环形空间上。这样子选中 A 这个物理节点的概率就是选中 A1 ~ A4 四个虚拟节点的概率的和了，也就间接引入了权重的概念。 |
 | 10 jones2000 2021-02-17 00:11:56 +08:00 怎么不考虑服务器的当前的负载和连接数呢, 这么分有什么用. |
 | 11 Harry1993 2021-02-17 00:18:23 +08:00 Bernoulli distribution 的拓展。先骰子定是 A 是{B,C,D}，如果是 A，那就返回 A ；如果是{B,C,D}那就重步：骰子定 B 是{C,D}... |
 | 12 sadfQED2 2021-02-18 16:42:00 +08:00 via Android 结合 2 楼老哥的答案，再结合面试官的要求，我突然灵光一现，面试官想要的可能是这样的 IP1:3 IP2:7 IP3:11 IP4:12 程序 random(0,12)如果小于等于 3，返回 ip1 。。。。 |
Select Language