COMP5270 Assignment 2 Feedback-only 中文详细题解

Posted on 2026-04-21 Edited on 2026-06-02 In Course Notes , COMP5270 Word count in article: 7.1k Reading time ≈ 26 mins.

来源: Assignment 2 (Feedback-only) Solutions.pdf
主题: universal hashing, consistent hashing, dynamic data structures, load balancing, variance reduction

这份 feedback-only assignment 有 4 个问题：

题目	官方定位	核心内容
Problem 1	easy	用普通 hash table 把学生分配到 tutorial，并分析开新 tutorial 时为什么几乎全员要重分配
Problem 2	medium /	用圆环上的 consistent hashing 降低开关 tutorial 的重分配成本
Problem 3	medium /	把 Problem 2 的策略实现成实际 data structure，用 BST 支持查询、插入、删除、开关 tutorial
Problem 4	hard /	分析 pairwise independent hashing 下的负载方差，并用多个 tutorial hashes 降低方差

这份作业最重要的主线是：

普通 hash table 对动态增删 bucket 很差；consistent hashing 只移动局部区间；但单个 hash 负载波动较大，所以用多个 virtual nodes / multiple hashes 降低 variance。

统一符号

作业背景是 COMP9999 tutorial 分配问题。

符号	含义
	全校 roster / catalogue 中所有可能学生的集合
	所有可能学生数量，非常大
	当前真正 enrolled in COMP9999 的学生数量，且
	当前开放的 tutorial 数量
	学校政策允许的最大 tutorial 数量上界
	consistent hashing 圆环上的 hash bucket 总数
	学生 hash function
	tutorial hash function
	tutorial 当前被分配到的学生数量
	tutorial 在圆环上负责的 hash buckets 数量

注意：

是所有可能学生数量，通常很大；
是当前实际选课人数；
数据结构空间应该主要依赖，而不是。

Problem 1: 普通 Hash Table 分配 Tutorial

题目要求

设计一个简单 data structure，把至多个学生分配到个 tutorials，要求：

给定学生，能很快知道他被分到哪个 tutorial；
平均每个 tutorial 不要有太多学生；
数据结构使用 memory。

需要支持：

FindTutorial(x): 返回学生被分配到的 tutorial，若不在课程中则返回；
Load(y): 返回 tutorial 当前有多少学生。

之后再问：如果开一个新 tutorial，变成，有多少学生平均需要被重新分配？

1.1 数据结构设计

最直接的方案是用 hash table。

选择一个 hash function

这里，表示 tutorial 编号。

数据结构维护一个数组

其中

$当前分到的学生数$

初始化时：

创建大小为的数组；
对每个，令；
随机选择一个 hash function ；
对每个当前 enrolled 的学生，计算，并令

于是：

FindTutorial(x) 返回；
Load(y) 返回。

1.2 为什么要用 strongly universal hash family

官方答案说从 suitable strongly universal hash family 中选择

这里真正需要的最基本性质是：

对任意固定学生，在上均匀分布。

strongly universal hashing 还给出更强的 pairwise independence：

对不同学生，和类似独立均匀。

这对后面算 variance 有用。

1.3 操作时间复杂度

假设 hash function 的 evaluation 是。

那么：

因为只要算一次。

因为只要读取数组。

初始化时间是

其中：

用于创建数组；
用于处理当前 enrolled 的学生；
是存储/选择 hash function 的量级。

1.4 平均负载分析

固定一个 tutorial 。定义 indicator：

那么 tutorial 的人数是

其中是当前 enrolled 学生集合，。

因为在上均匀分布：

所以

由期望线性性：

因此每个 tutorial 的 expected load 是

1.5 方差补充

如果 hash family 是 strongly universal，那么不同学生的 hash 值 pairwise independent。

于是：

对 Bernoulli 变量：

所以

这说明单个 tutorial 的 load 会集中在平均值附近，但这个普通 hash table 有一个更严重的问题：一旦 tutorial 数量改变，hash function 的 codomain 改了，几乎所有学生都可能被重新分配。

1.6 空间复杂度

数据结构要存：

hash function ；
数组中个计数。

官方答案假设 hash function 可用

bit 存储。

每个计数的范围是到，所以需要

bit。

总空间：

因为，也可粗略写成：

在合理参数下，tutorial 数量远小于可能学生数量，所以

1.7 开新 tutorial 为什么代价很大

现在从个 tutorials 变成个 tutorials。

普通 hash table 的问题是：

原来的 hash function 是

新的 hash function 应该是

也就是说，codomain 变了，必须重新选择 hash function，并重新 hash 所有学生。

对固定学生，他原来留在 tutorial 的概率是：

新 hash function 下：

因为和独立，所以学生留在原 tutorial 的概率为：

代入：

所以学生被重新分配的概率是

当前有个 enrolled students，因此 expected number of moved students 是

这个数几乎等于，即几乎所有学生都要重分配。

这就是 Problem 1 的核心结论：

普通 hash table 的 average load 很好，但动态改变 bucket/tutorial 数量时非常差。

Problem 1 用到的知识点

hash table；
universal / strongly universal hashing；
indicator random variables；
expectation linearity；
pairwise independence；
variance of Bernoulli variables；
space complexity in bits；
dynamic resizing 的 rehashing cost。

Problem 2: Consistent Hashing 圆环方案

Problem 1 的问题是：开新 tutorial 时，整个 hash function 从改到，导致几乎所有学生都要重新 hash。

Problem 2 的策略是 consistent hashing：

把学生和 tutorials 都 hash 到同一个大圆环上。学生分给顺时针方向上遇到的第一个 tutorial。开/关 tutorial 只影响这个 tutorial 附近的一小段区间。

2.1 两个 hash functions

使用两个 hash functions：

用于 hash students；

用于 hash tutorials。

其中：

是允许的最大 tutorial 数；
是圆环上的 bucket 数；
要远大于或至少远大于，方便避免 tutorial hash collisions。

2.2 圆环解释

把看成一个圆环：

首尾相接。

每个学生有一个位置：

每个 tutorial 有一个位置：

分配规则：

学生被分给从出发顺时针方向遇到的第一个 tutorial hash point。

等价地，tutorial 负责它前一个 tutorial hash point 到之间的那段圆环区间。

这个规则天然处理 wrap-around：如果学生的位置在最大 tutorial hash 之后，就绕回去分给最小 tutorial hash 对应的 tutorial。

2.3 避免 tutorial hash collisions

为了让圆环上的 tutorial points 不重合，需要让之间无 collision。

这和 birthday paradox 一样。

若把个 tutorial hashes 放进个 buckets，collision 概率可用 union bound 粗略估计：

如果想让 collision 概率小于常数，比如，只需要

其中是足够大的常数。

所以官方答案写：

即可保证以至少概率没有 tutorial hash collision。

之后分析都在“没有 tutorial collision”的条件下进行。

2.4 每个 tutorial 的期望学生数

固定一个 tutorial 。

因为 tutorial hash points 在圆环上完全随机且对称，每个 tutorial 在期望上负责同样长度的圆环区间。

所以每个 tutorial 的 expected load 都一样：

又因为每个学生一定被分配给且只分配给一个 tutorial：

两边取期望：

由于所有相同：

因此：

注意这里用到了官方的 simplifying assumption：

hash functions behave like totally random functions。

也就是的分布足够对称，圆环上每个 tutorial 没有偏向。

2.5 开新 tutorial 的重分配成本

现在从个 tutorials 增加到个 tutorials。

consistent hashing 不需要重新 hash 所有学生。只需要：

计算新 tutorial 的位置

找到它在圆环上的前一个 tutorial hash point；
把这两个点之间那段区间里的学生移动到新 tutorial。

设这段新 tutorial 接管的区间长度为，即它负责的 hash buckets 数。

因为个 tutorial points 在圆环上对称，平均每个 tutorial 负责

个 buckets。

给定后，一个学生落到这段区间的概率是

所以条件期望为：

其中是需要移动的学生数量。

再用 total expectation：

所以开新 tutorial 的 expected energy cost 是：

这和 Problem 1 的普通 hash table 形成强烈对比：

方法	开新 tutorial 平均移动人数
普通 hash table
consistent hashing

2.6 删除 tutorial 的重分配成本

删除 tutorial 时，也只影响一个局部区间：

原来分给 tutorial 的学生需要移动；
这些学生会被交给圆环上下一个 tutorial；
其他 tutorial 的学生都不用动。

因为每个 tutorial 的 expected load 是，所以删除一个 tutorial 的 expected moved students 是：

这也是 consistent hashing 的核心优势：

bucket 数量变化时，只移动被新增/删除节点局部影响的 keys。

2.7 单个 tutorial 负责多少 hash buckets 的高概率上界

令表示 tutorial 负责的 hash buckets 数。

令

表示任何 tutorial 负责的最大 bucket 数。

目标是证明：对任意，除了概率至多

没有 tutorial 负责超过

个 buckets。

换句话说：

第一步：把圆环分成区间

把个 buckets 分成大约

个 disjoint intervals，每个 interval 长度为

忽略 floor/ceiling。

第二步：某个 interval 没有 tutorial hash 的概率

固定一个 interval ，长度是。

一个 tutorial hash 不落入的概率是

个 tutorial hashes 都不落入的概率是

这里用到：

第三步：union bound

interval 总数约为，所以存在某个 interval 为空的概率至多：

因此，至少以概率

每个 interval 里都有至少一个 tutorial hash。

第四步：为什么出现 factor 2

如果每个 interval 都有 tutorial hash，那么任意两个相邻 tutorial hash points 之间的 gap 最多跨过两个 interval。

所以任何 tutorial 负责的 buckets 数至多是：

这就是：

2.8 最大 bucket 数的期望上界

利用 tail integral：

前面已经有：

选择分界点：

直观上：

小于的部分，用概率上界 1；
大于这个值的尾部，用积掉。

官方解答得到：

所以：

这表示 consistent hashing 的最大区间长度比平均值多一个因子。

Problem 2 用到的知识点

consistent hashing；
circular hash space；
birthday paradox / collision bound；
symmetry argument；
law of total expectation；
local reassignment；
union bound；
exponential inequality ；
tail integral formula；
maximum spacing / load imbalance analysis。

Problem 3: 实现 Consistent Hashing 的 Data Structure

Problem 2 只是策略分析。Problem 3 要把它实现成一个真实 data structure，支持：

FindStudent(x)；
Load(y)；
InsertStudent(x)；
RemoveStudent(x)；
OpenTutorial()；
CloseTutorial(y)。

要求：

FindStudent(x) 需要；
空间主要依赖，对只有 logarithmic dependence。

3.1 使用 self-balancing BST

核心数据结构：

用一个 self-balancing Binary Search Tree（如 AVL tree / Red-Black tree）存 tutorial hash points。

BST 的 key 是 tutorial 的 hash 值：

每个 node 存：

其中：

是 tutorial 编号；
是当前 tutorial 的学生数；
是分配给 tutorial 的学生列表；
按学生 hash 值排序。

也就是说：

并且

为什么要排序？

开新 tutorial 时，只需要从某一个 tutorial 的列表开头/结尾切出一段学生；排序让这件事不用扫描所有学生。

3.2 FindStudent(x)

目标：找到学生应该被分配到哪个 tutorial。

步骤：

计算学生位置：

在 BST 中寻找 key 大于等于的第一个 tutorial hash，即 successor。
如果存在 successor，就返回该 node 对应的 tutorial。
如果不存在 successor，说明在最大 tutorial hash 后面，需要 wrap around，于是返回 BST 中最左边 node，也就是最小 tutorial hash。

时间复杂度：

注意官方解答指出：这个操作只是返回学生“应该被分配到哪个 tutorial”，不一定检查学生是否真的 enrolled。如果要检查 enrolled，还要在中查找，可能增加额外时间。

3.3 Load(y)

目标：返回 tutorial 当前有多少学生。

步骤：

计算或直接知道；
在 BST 中查找 key ；
找到 node

后返回。

时间复杂度：

3.4 InsertStudent(x)

目标：把学生加入课程。如果已经 enrolled，则什么都不做。

步骤：

用 FindStudent(x) 的逻辑找到 tutorial ；
在对应列表中查找；
如果已存在，则不做事；
否则把插入，并保持按排序；
更新

时间复杂度取决于的实现。

官方解答把当作 sorted list，因此在中查找/插入可能需要。

所以：

期望下：

所以 expected time：

最坏情况下，所有学生都可能在同一个 tutorial：

3.5 RemoveStudent(x)

目标：把学生从课程中删除。如果他没有 enrolled，则什么都不做。

步骤和 InsertStudent(x) 类似：

找到应该所在的 tutorial ；
在中查找；
如果存在，删除它；
更新

使用 sorted list 时，复杂度同样是：

期望：

3.6 OpenTutorial()

目标：新开 tutorial 。

consistent hashing 的关键是：

新 tutorial 只会抢走它在圆环上前一个区间内的一部分学生。

步骤：

计算新 tutorial 的 hash：

在 BST 中插入一个新 node：

找到圆环上与它相邻、会被它分走部分学生的旧 tutorial。
在旧 tutorial 的 sorted list 中，把现在应该属于新 tutorial 的学生切出来。
把这些学生移动到。
更新两个 tutorial 的 loads。

Problem 2 已经证明，开新 tutorial 时 expected moved students 是：

因为按排序，这些要移动的学生集中在列表的一段，不需要遍历整个系统。

所以 expected time：

其中：

是 BST 插入/查找；
是期望移动学生数。

3.7 CloseTutorial(y)

目标：关闭 tutorial 。

步骤：

在 BST 中查找；
如果不存在，什么都不做；
若存在，找到它在圆环上的 successor tutorial ；
把中所有学生移到；
更新；
从 BST 中删除 node 。

Problem 2 证明，删除 tutorial 时 expected moved students 是：

官方给出的 expected complexity 形式是：

具体常数和实现方式有关：

BST 查找/删除有；
移动学生数量期望是；
如果移动时需要维护 sorted list，可能还会有 list merge / insertion 的代价。

复习时记住主线即可：

OpenTutorial 和 CloseTutorial 的 expected cost 都和被移动的局部学生数成正比，不再是。

3.8 空间复杂度

需要存：

hash functions ；
BST 中个 tutorial nodes；
所有 enrolled students 的列表项。

hash functions 占：

bits。

每个 BST node 存：

其中：

需要 bits；
需要 bits；
中每个学生 ID 需要 bits。

所有 lists 总共存了个学生，所以学生 ID 总空间是：

BST nodes 的额外空间是：

总空间：

如果合理假设

则主导项通常是：

这符合要求：空间主要依赖当前 enrolled 的学生数，对总 roster 大小只有 logarithmic dependence。

Problem 3 用到的知识点

self-balancing BST；
successor query；
circular order / wrap-around；
sorted lists；
dynamic data structure operations；
expected update cost；
space complexity in bits；
consistent hashing 的实际实现。

Problem 4: Pairwise Independent Hashing 下的负载方差与改进

Problem 2 的分析用了一个 simplifying assumption：hash functions behave like fully random functions。

Problem 4 更现实一些：

学生 hash function 只来自 pairwise independent hash family；
tutorial hash function 仍假设 fully random，方便分析。

问题是：consistent hashing 虽然降低了重分配成本，但单个 tutorial 负责的圆环区间可能很长，导致 load variance 很大。

Part A: 单个 tutorial 的二阶矩和方差

4.1 目标

固定 tutorial 。

令：

是 tutorial 负责的 hash bucket 数；
是 tutorial 负责的学生数；
是被分给 tutorial 的学生集合。

目标是证明：

这个结果其实不够好，后面会解释为什么。

4.2 展开

因为

所以

展开：

取期望：

第一项就是：

第二项要用 pairwise independence。

4.3 给定后，学生落入该 tutorial 的概率

如果 tutorial 负责个 buckets，那么一个学生被分给的概率是：

对两个不同学生，因为是 pairwise independent：

因此：

这就是官方要求证明的第一条：

4.4 用 tail-sum bound 控制

对非负整数随机变量，有：

所以：

而

为了处理整数，写成：

所以：

4.5 计算

固定 tutorial 的 hash point 。

的意思是：

在逆时针方向之前的个 buckets 中，没有任何其他 tutorial hash。

如果有其他 tutorial hash 落在这段长度为的区间里，那么负责的区间就不会超过。

对任意另一个 tutorial ，它不落入这段区间的概率是：

因为假设 fully random，其他个 tutorial hashes 独立，所以：

这里明确用到了 full independence of 。

4.6 得到方差上界

把上面的 tail bound 与 Riemann sum 比较，可以得到官方给出的结论：

直观解释：

一个 tutorial 平均负责个 buckets；
所以的典型规模像；
但由于区间长度有长尾，需要用上面的积分论证控制二阶矩。

代回二阶矩公式：

在合理设定下，主导项可以写成：

而

因此：

Part B: 这个方差界为什么不够好

平均值是：

方差上界是：

所以标准差是：

这和平均值同阶。

用 Chebyshev：

但因为

这个结论只能说：

以 99% 概率成立。

这太弱了。

例如它不能很好地保证：

或者

所以这个 variance bound 对“负载均衡”来说不够强。

Part C: 高概率存在一个 tutorial 负载非常小

官方要求证明：以至少 99% 概率，至少有一个 tutorial 只负责非常小的一段 hash buckets，从而 expected load 只有

做法是把个 buckets 分成

个 intervals，每个 interval 长度为

其中是足够大的常数。

现在把个 tutorial hash points 放进这些 intervals。

interval 数量约为，而 tutorial 数量是。Birthday paradox 告诉我们：

当有个点放进约个 boxes 时，选足够大的，发生 collision 的概率可以达到至少 99%。

如果两个 tutorial hashes 落到同一个很短的 interval 里，那么这两个 tutorial 中至少有一个负责的 gap 不超过这个 interval 长度：

一个学生落入这段 buckets 的概率是：

所以该 tutorial 的 expected load 是：

这说明：

单个 hash point 的 consistent hashing 会导致明显的不均衡：有的 tutorial 可能几乎没有学生。

严格来说，官方解答这里主要通过 bucket 区间长度推出对学生数的期望上界；如果要对实际学生数也给高概率保证，还需要额外 concentration 分析。

Part D: 用个 tutorial hashes 改进负载均衡

为了解决单个 tutorial hash point 负载波动太大的问题，可以给每个 tutorial 多个 hash points。

这就是 consistent hashing 里常见的 virtual nodes 思想。

4.7 新策略

对每个 tutorial ，不再只有一个 hash：

而是有个 hash functions：

每个 tutorial 在圆环上有个位置：

整个圆环上一共有

个 tutorial hash points。

学生仍然按同样规则分配：

学生分给从出发顺时针方向遇到的第一个 tutorial hash point；这个 hash point 属于哪个 tutorial，学生就归哪个 tutorial。

于是每个 tutorial 的总学生数是它个 virtual nodes 的学生数之和。

4.8 数据结构如何改

Problem 3 的 BST 仍然可以用，只是节点数量从变成。

每个 node 现在存：

其中：

是 tutorial；
是 tutorial 的第几个 hash point；
是这个 virtual node 负责的学生数；
是对应学生列表。

tutorial 的总 load 是：

因为总共有个 tutorial hash points，要避免 collisions，需要：

这是把之前的换成后得到的 birthday bound。

4.9 期望 load 不变

虽然每个 tutorial 有个 hash points，但 symmetry 仍然成立。

每个 tutorial 在期望上占总圆环的，所以：

也就是说，多放 virtual nodes 不改变平均负载，只是降低波动。

4.10 方差降低倍

单个 hash point 时：

现在圆环上有个 points。

每个 virtual node 负责的区间更小；单个 virtual node 的 variance 大约下降为原来的倍。

一个 tutorial 有个 virtual nodes，把它们加起来后，总 variance 下降一个因子：

这就是 multiple hashes / virtual nodes 的核心效果：

平均值不变，方差除以。

4.11 空间复杂度

相比 Problem 3，主要变化有两个：

要存个 tutorial hash functions；
BST 节点从个变成个。

总空间：

官方写成：

其中所有学生列表总共仍然只存个学生，所以学生 ID 部分没有乘。

4.12 如何选择保证

目标：对一个固定 tutorial ，希望以至少 99% 概率有

令

现在 variance bound 是：

用 Chebyshev：

代入 variance：

要让右边至多，只需要：

所以：

就足以保证任意一个固定 tutorial 的 load 在内，概率至少 99%。

注意这是对 fixed tutorial 的保证。如果要同时保证所有 tutorials，需要再对个 tutorials 做 union bound，可能需要多一个因子。

Problem 4 用到的知识点

pairwise independent hashing；
full independence assumption for tutorial hashes；
second moment method；
variance calculation；
tail-sum formula for nonnegative integer variables；
Riemann sum / integral comparison；
Chebyshev inequality；
Birthday Paradox；
virtual nodes / multiple hashes；
variance reduction by averaging；
space complexity with replicated hash points。

总结：这份 Assignment 2 到底在考什么

1. 普通 hash table 的优缺点

普通 hash table：

查询快：；
平均负载好：；
空间小：；
但动态改变 tutorial 数量时很差：开新 tutorial 平均移动

个学生，几乎全员重分配。

2. Consistent hashing 的核心优势

把 students 和 tutorials 都 hash 到圆环上：

学生分给顺时针遇到的第一个 tutorial；
开新 tutorial 只移动它接管区间内的学生；
删除 tutorial 只移动被删 tutorial 的学生。

移动成本：

3. 圆环负载不是自动完美均衡

单个 tutorial hash point 时：

平均负载仍是；
但最大负责区间期望是

方差和平均值同阶，Chebyshev 给不出很强的 concentration；
甚至高概率存在某个 tutorial 负责很短区间，expected load 只有。

4. 多个 hash points / virtual nodes 改善方差

每个 tutorial 放个 hash points：

期望 load 不变：

方差下降倍：

可让固定 tutorial 的 load 以 99% 概率落在

附近。

5. 期末复习优先级

最值得背熟的推导：

普通 hash table 开新 bucket 为什么几乎全员重分配；
consistent hashing 的圆环分配规则；
open/close tutorial 的 expected moved students；
collision-free 需要；
最大 interval 长度的 union bound 证明；
BST 如何支持 successor query；
second moment / variance 推导；
multiple hashes 如何把 variance 降低倍；
用 Chebyshev 推出。

如果只记一句话：

Assignment 2 的核心是 consistent hashing：用圆环上的局部性把动态增删 tutorial 的重分配成本从降到，再用多个 virtual nodes 改善负载方差。

统一符号

Problem 1: 普通 Hash Table 分配 Tutorial

题目要求

1.1 数据结构设计

1.2 为什么要用 strongly universal hash family

1.3 操作时间复杂度

1.4 平均负载分析

1.5 方差补充

1.6 空间复杂度

1.7 开新 tutorial 为什么代价很大

Problem 1 用到的知识点

Problem 2: Consistent Hashing 圆环方案

2.1 两个 hash functions

2.2 圆环解释

2.3 避免 tutorial hash collisions

2.4 每个 tutorial 的期望学生数

2.5 开新 tutorial 的重分配成本

2.6 删除 tutorial 的重分配成本

2.7 单个 tutorial 负责多少 hash buckets 的高概率上界

第一步：把圆环分成区间

第二步：某个 interval 没有 tutorial hash 的概率

第三步：union bound

第四步：为什么出现 factor 2

2.8 最大 bucket 数的期望上界

Problem 2 用到的知识点

Problem 3: 实现 Consistent Hashing 的 Data Structure

3.1 使用 self-balancing BST

3.2 FindStudent(x)

3.3 Load(y)

3.4 InsertStudent(x)

3.5 RemoveStudent(x)

3.6 OpenTutorial()

3.7 CloseTutorial(y)

3.8 空间复杂度

Problem 3 用到的知识点

Problem 4: Pairwise Independent Hashing 下的负载方差与改进

Part A: 单个 tutorial 的二阶矩和方差

4.1 目标

4.2 展开

4.3 给定 后，学生落入该 tutorial 的概率

4.4 用 tail-sum bound 控制

4.5 计算

4.6 得到方差上界

Part B: 这个方差界为什么不够好

Part C: 高概率存在一个 tutorial 负载非常小

Part D: 用 个 tutorial hashes 改进负载均衡

4.7 新策略

4.8 数据结构如何改

4.9 期望 load 不变

4.10 方差降低 倍

4.11 空间复杂度

4.12 如何选择 保证

Problem 4 用到的知识点

总结：这份 Assignment 2 到底在考什么

1. 普通 hash table 的优缺点

2. Consistent hashing 的核心优势

3. 圆环负载不是自动完美均衡

4. 多个 hash points / virtual nodes 改善方差

5. 期末复习优先级

4.3 给定后，学生落入该 tutorial 的概率

Part D: 用个 tutorial hashes 改进负载均衡

4.10 方差降低倍

4.12 如何选择保证