亲手实现并统计哈希、树与堆

目标

亲手实现线性探测哈希表、不做平衡的二叉搜索树、最小堆和有序数组，用确定性的数字来统计：随装载因子变化的探测数、随输入顺序变化的树高度、top-k 的堆替换次数，以及区间个数。最后针对四种工作负载选出结构，并以这些数字作为依据。

为什么重要

数据结构的开销在测量时间之前就可以数出来。哈希表的装载因子越高，查找一个不存在的键所要走的槽位数就按平方增长；不做平衡的树一遇到有序输入就退化成链表；用于选取前 k 名的堆，对大多数项只需比较一次就丢弃。这些数字即使在共享 CPU 的 Pod 上也不会波动，因此可以作为向别人证明为什么选这种结构的依据。所以评分器不测量时间，而是把你的类和函数放到不在材料里的输入上重新运行，把探测数、高度、pop 顺序、读取元素的次数与参考实现对照。

材料

位于 /opt/fixtures/svccs/structures/ 之下。只读取，不要修改。

keys.txt        세션 토큰 8,000개(한 줄에 하나, 서로 다름)
absent.txt      keys.txt 에 없는 토큰 3,000개
bst_keys.txt    서로 다른 정수 3,000개(섞인 순서)
stream.csv      id,score 40,000줄(점수 동점이 많다)
timestamps.txt  정렬된 초 단위 시각 30,000줄(같은 초가 여러 번 나온다)
queries.json    {"queries": [[lo, hi], …]} 구간 질의
workload.json   {"scenarios": [{name, desc, …부하별 값, evidence: [근거 키 이름]}]}
params.json     table_size · loads(적재율 목록) · k

计数规则

집 칸     home(key, size) = int.from_bytes(sha256(key.encode("utf-8")).digest()[:8], "big") % size
탐사      집 칸부터 한 칸씩(끝에서 0 으로 돈다) 본다. 본 칸의 수가 탐사 수 — 첫 칸도 1회,
          찾은 칸도 1회, 없는 키면 마지막 빈 칸도 1회
높이      뿌리에서 잎까지 가장 긴 경로의 노드 수. 빈 트리 0, 노드 하나 1. 같은 키는 다시 넣지 않는다
top-k     점수 큰 순, 동점이면 id 작은 순. 크기 k 최소 힙(키 (score, -id)) — k 개가 찬 뒤
          새 항목의 키가 루트보다 크면 루트를 바꾸고 replacements +1
구간      [lo, hi) — lo 포함, hi 제외, lo >= hi 면 0

步骤

1. 在 /root/svccs/structures/home.json 中写入 size（params.json 中的 table_size）、first5（keys.txt 前 5 个键的首选槽位列表）、distinct_homes（keys.txt 前 size÷2 个键的首选槽位中，互不相同的槽位数）。
2. 在 /root/svccs/structures/structs.py 中编写 LinearProbeTable(size)。insert(key) 返回查看过的槽位数（如果键已存在就不插入，返回查找时查看过的槽位数），search(key) 返回 (찾았나, 본 칸의 수) 元组（占位符依次为是否找到、查看过的槽位数），len(table) 是元素个数。
3. 对 params.json 的 loads 中的每个装载因子，向新表（大小为 table_size）插入 keys.txt 前 n = round(α × size) 个键，并把 {"size", "rows": [{"alpha", "n", "avg_hit", "avg_miss", "max_hit", "theory_hit", "theory_miss"}]} 写入 /root/svccs/structures/loads.json。avg_hit 是对已插入的键做 search 的探测数平均值，avg_miss 是对 absent.txt 做 search 的平均值，max_hit 是已插入键中的最大值，theory_hit = ½(1 + 1/(1−α))，theory_miss = ½(1 + 1/(1−α)²)，平均值和理论值都保留三位小数。
4. 在同一个文件里编写 bst_height(keys)（依次插入不做平衡的 BST 之后的高度），并把 n、shuffled_height（bst_keys.txt 的文件顺序）、sorted_height（升序）、min_height（ceil(log2(n + 1))）写入 /root/svccs/structures/bst.json。
5. 在同一个文件里编写 MinHeap——push(value)、pop()（最小的值，为空时抛出 IndexError）、len(heap)。只用一个数组自己实现，类里不使用 heapq 或排序。
6. 在同一个文件里编写 top_k(stream, k)。stream 是只能遍历一次的 (id, score) 迭代器，返回 {"top": [[id, score], …], "replacements": 정수}（占位符为整数；可以使用 heapq）。用 stream.csv 和 params.json 的 k，把 k、n（数据行数）、top、replacements 写入 /root/svccs/structures/topk.json。
7. 在同一个文件里编写 count_range(values, lo, hi)（values 是有序序列）。不要复制或遍历 values，而是用二分查找来统计。把 n（timestamps.txt 的行数）和 counts（按 queries.json 的顺序得到的个数）写入 /root/svccs/structures/ranges.json。
8. 针对 workload.json 中的每个负载，把 {"choice", "evidence", "reason"} 写入 /root/svccs/structures/choose.json。choice 是 hash、bst、heap、sorted_array 之一，reason 是一句话，evidence 是该负载的 evidence 列表中的键，按下面的规则算出的值。

依据数字规则（第 8 步）

sessions      alpha = round(n / table_size, 3)
              avg_hit_probes = 크기 table_size 표에 keys.txt 앞 n 개를 넣고 그 키들을 search 한 평균(셋째 자리)
leaderboard   kept = k, replacements = top_k(stream.csv, k) 의 replacements
audit-window  count = timestamps.txt 에서 window 의 [lo, hi) 개수
order-ids     bst_height_sorted = bst_height(1, 2, …, n)
              bst_height_shuffled = bst_height(bst_keys.txt 앞 n 개, 파일 순서)

参考

• 评分器会导入 structs.py。读取文件并生成结果的代码，请放在 if __name__ == "__main__": 之下或单独的脚本里。
• 常见错误：把探测数按冲突数（探测 − 1）来计；把高度按边数来计；在有序输入上递归超过限制；在区间的 hi 一侧使用 bisect_right。
• 产出会在会话结束后消失。需要的话请另行保存。

用哈希规则求出首选槽位

把 keys.txt 前 5 个键的首选槽位，以及前 size÷2 个键中互不相同的首选槽位数，以 size、first5、distinct_homes 的形式写入 /root/svccs/structures/home.json。

取 hashlib.sha256(key.encode('utf-8')).digest()[:8]，用 int.from_bytes(…, 'big') 读出，再对 size 取余。如果明明装载因子只有 0.5，互不相同的首选槽位数却比键的数量少得多，就说明有相应数量的键从一开始就把别人的槽位当成了自己的首选。

构建线性探测表并统计探测次数

在 /root/svccs/structures/structs.py 中编写 LinearProbeTable(size)——insert 返回查看过的槽位数，search 返回 (是否找到, 查看过的槽位数)。评分器会用变形键逐个把探测数与参考实现对照。

从首选槽位开始，一个槽位一个槽位地走，直到遇到空槽位或该键，并计数。第一个槽位也算 1 次。最后一个槽位之后是 0 号槽位（% size）。如果把查找路径和插入路径放在同一个函数里，两种操作的计数方式就不会不一致。

装载因子会改变探测数

对装载因子 0.5、0.75、0.9，各自用新表插入键，把存在的键与不存在的键的平均探测数、最大探测数和理论值写入 /root/svccs/structures/loads.json。

每个装载因子都要重新建表。不存在的键必须走到遇见空槽位为止，所以装载因子一升高，它就比查找成功增长得快得多。理论值是均匀哈希假设下的近似，与实测值可能略有差别。

有序输入会把树变成链表

在 structs.py 中编写 bst_height(keys)，把 bst_keys.txt 按文件顺序和升序插入后的高度写入 /root/svccs/structures/bst.json。评分器还会用有序的 1,500 个键、重复键和空输入来调用。

高度是节点数（只有一个节点时为 1）。用递归往下走，在有序输入上深度会变成 n，触发 RecursionError——把插入写成循环，并随身带着“挂上新节点的深度”的最大值作为高度，就不必另外计算了。

亲手实现最小堆

在 structs.py 中用一个数组实现 MinHeap（push、pop、len）。评分器会在混合了 push 和 pop 的操作序列（含重复值和元组）上，把 pop 顺序与 heapq 对照。

push 把元素追加到末尾，只要比父节点小就往上提。pop 取出根，把最后一个元素放到根上，再与两个子节点中较小的一个交换，往下沉。如果只看左子节点，pop 顺序就会错乱。下标为 k 的节点，其子节点是 2k+1、2k+2。

用大小为 k 的堆求出流中的前 k 名

在 structs.py 中编写 top_k(stream, k)，并用 stream.csv 和 params.json 的 k，把 k、n、top、replacements 写入 /root/svccs/structures/topk.json。评分器会把并列很多的变形流以迭代器的形式传入。

不是最大堆，而是大小为 k 的最小堆——根就是门槛。要在并列时留下 id 较小的一方，就把键设为 (score, -id)。top 要在最后把堆按分数从大到小排序，转换成 [id, score]。stream 只能遍历一次。

用有序数组和 bisect 统计区间

在 structs.py 中编写 count_range(values, lo, hi)，并把 queries.json 中各区间的个数写入 /root/svccs/structures/ranges.json。评分器会用边界落在重复值上的变形数组来调用，还会统计读取了多少次元素。

bisect_left 给出的是“比这个值小的元素个数”。所以 [lo, hi) 就是两个 bisect_left 之差。如果在 hi 一侧用 bisect_right，会把与 hi 相等的值也算进去。用 list() 复制 values 或用 for 遍历，就会读取全部元素。

用数字为工作负载选出合适的结构

针对 workload.json 中的四种负载，分别选出结构（hash、bst、heap、sorted_array），用前面步骤实现的函数算出依据数字，写入 /root/svccs/structures/choose.json。

看每个负载问的是什么（精确匹配、前 k 名、区间），以及输入按什么顺序到来。把总是变大的键放进不做平衡的树，高度会变成多少，在第 4 步已经测过了。依据规则就是说明中的“依据数字规则”。