课程大纲 第 27 课,共 148 课 · 用 AI 来理解
用 AI 来理解

关闭 AI 的双胞胎题:哈希环

为什么重要 “执着于你自己”中的环绕日志,核心只有一个想法。它在这里又出现了,在一个你可能真的会构建的系统里,而且导师是关闭的。

这道题的导师已经关闭。自己把它解出来。

一个缓存集群用一致性哈希把键分散到各台服务器上。每台服务器拥有一个由从 0 到大约二十亿的整数组成的环上的某些位置。一个键被哈希成一个数字,它属于沿着环走、位于这个数字处或之后的第一个节点位置:越过最大的位置后,它会绕回到最小的位置。

节点位置按顺序存放在一张共享的表里,但这张表是一个环形缓冲区:它从上一个写入者停下的地方开始。每读一次这张表都是一次网络往返,所以读取次数会被统计。

数据

from creative.budget import Tape
ring = Tape([700, 900, 100, 300])   # sorted positions 100, 300, 700, 900, stored from 700
hashes = [250, 950]
# owners(ring, hashes) -> [300, 100]
轮到你了

编写 owners(ring, hashes)。ring 是一个由互不相同的节点位置组成的 Tape,这些位置是有序的,但可能被旋转过(从任意一个起点开始存储,可能是 0)。它至少包含一个节点。对于每个哈希值 h,返回最小的 >= h 的位置;如果没有,就返回所有位置中最小的那个。预算:在 100,000 个节点和 200 个哈希值的情况下,你最多只能读取 20,000 个值。len(ring) 是免费的。

关闭 AI:这一题没有导师、提示或参考答案。只靠你自己的思考。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。