请教一道算法编程题

• 主 資深大佬 : 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 。。。。