这是一个创建于 1373 天前的主题，其中的信息可能已经有所发展或是发生改变。
面试遇到过的，给一组服务器 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