请教一道算法编程题

[impl]

面试遇到过的，给一组服务器 IP 和权重，然后根据权重随机返回服务器 IP 。例如，[{A,4},{B,4},{C,4},{D,1}]。看网上解法是将权重累加，然后用二分查找，看随机数落在哪个区间。但面试官要求用哈希表，而且是用 IP 做键值。有人知道怎么做的吗？

[impl]

s/键值 /键

[ytmsdy]

把权重相加一下，例如帖子里面所说的 4+4+4+1，然后开一个长度为 13 的数组。
例如 [A,A,A,A,B,B,B,B,C,C,C,C,D]
一个请求过来以后，搞个随机数，然后 13 取模。余数是那个，就返回那个 IP 。
不知道有没有理解对。

[ccagml]

一致性哈希，不知道有没有理解对

[Exple]

https://stackoverflow.com/questions/1761626/weighted-random-numbers

[OldCarMan]

不知道楼主说“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]之间获取一个随机下标或者当前时间对总权重值取模。

[impl]

@ytmsdy 这种实现最容易想到，但权重如果是个很大数值，会很耗内存。这不是面试官要的答案

@Exple 看了第一个答案，好像跟我说的解法类似

@OldCarMan 是键。我也不明白为什么 IP 是键而不是值，问了面试官，说是”也可以返回的是键”

[impl]

@ccagml 看了一下，一致性哈希好像没有涉及到权重的概念？

[cassyfar]

哈希就没法随机了。但是如果不随机，可以用 ring hash 。

[copper20]

@impl 说的应该是带虚拟节点的一致性哈希。若一台服务器的权重为 n，可以把这台服务器看成 n 台虚拟的服务器，比如 {A,4} 这台服务器可以看成 A1 A2 A3 A4 四个虚拟节点。然后再把 A1 ... A4 B1 ... B4 C1 ... C4 D1 这些虚拟节点用哈希函数映射到环形空间上。这样子选中 A 这个物理节点的概率就是选中 A1 ~ A4 四个虚拟节点的概率的和了，也就间接引入了权重的概念。

[jones2000]

怎么不考虑服务器的当前的负载和连接数呢, 这么分有什么用.

[Harry1993]

Bernoulli distribution 的拓展。先搖骰子決定是 A 還是{B,C,D}，如果是 A，那就返回 A ；如果是{B,C,D}那就重複步驟：搖骰子決定 B 還是{C,D}...

[sadfQED2]

结合 2 楼老哥的答案，再结合面试官的要求，我突然灵光一现，面试官想要的可能是这样的

IP1:3
IP2:7
IP3:11
IP4:12

程序 random(0,12)如果小于等于 3，返回 ip1 。。。。