请教一道算法编程题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1363 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

权重

哈希表

键值

服务器

12 条回复 • 2021-02-18 16:42:00 +08:00

impl

2021-02-15 19:37:04 +08:00 via Android

s/键值 /键

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 。
不知道有没有理解对。

ccagml

2021-02-15 22:18:32 +08:00 via Android

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

Exple

2021-02-15 22:46:42 +08:00 via Android

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

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

impl

2021-02-16 00:01:15 +08:00 via Android

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

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

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

impl

2021-02-16 00:20:38 +08:00 via Android

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

cassyfar

2021-02-16 06:42:45 +08:00

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

copper20

2021-02-16 09:49:11 +08:00

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

jones2000

2021-02-17 00:11:56 +08:00

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

Harry1993

2021-02-17 00:18:23 +08:00

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

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 。。。。