📚 Goodness of Fit in Hash Functions | 哈希函数的拟合优度
In A-Level Computer Science (Edexcel), the concept of 'goodness of fit' describes how well a hash function distributes keys uniformly across the available slots in a hash table. A hash function with a good fit minimises collisions and keeps the table operating efficiently, which is essential for achieving average O(1) time complexity for insertions, deletions, and lookups. This article explores what goodness of fit means, how it is measured, and why it matters in the design and maintenance of hash tables, with a focus on the Edexcel specification.
在A-Level计算机科学（Edexcel）中，‘拟合优度’概念描述的是哈希函数将键均匀分布到哈希表各个槽位的能力。拟合度良好的哈希函数可以最大限度地减少冲突，使表保持高效运行，这对于实现插入、删除和查找的平均 O(1) 时间复杂度至关重要。本文将探讨拟合优度的含义、衡量方式，以及它在哈希表设计和维护中的重要性，紧扣 Edexcel 考试大纲。
1. What is Goodness of Fit? | 什么是拟合优度？
Goodness of fit, in the context of hash tables, refers to the degree to which a hash function produces an even spread of hash values across the table's slots. When goodness of fit is high, each slot is expected to receive roughly the same number of keys, avoiding empty spaces on one side and heavy clustering on the other. Poor fit leads to many collisions, degrading performance from expected constant time towards O(n) in the worst case.
在哈希表语境中，拟合优度指的是哈希函数将哈希值均匀分布到表的各个槽位的程度。拟合度高时，每个槽位预计将接收大致相同数量的键，避免一端出现大量空槽而另一端严重聚集。拟合度差会导致冲突频繁发生，使性能从预期的常数时间退化到最坏情况下的 O(n)。
For the Edexcel specification, you are expected to understand that a 'good' hash function achieves a high goodness of fit, meaning the keys are spread uniformly. You should also be able to discuss how to evaluate whether a given hash function is suitable, often by using the concept of load factor and by observing the distribution of keys after insertion.
根据 Edexcel 大纲，你需要理解‘好’的哈希函数能够实现高拟合优度，即键被均匀分布。你还应当能够讨论如何评估一个哈希函数的适用性，通常可借助负载因子的概念，并观察插入后键的分布情况。
2. The Role of Hash Functions | 哈希函数的作用
ple is the modulo function: h(k) = k mod m, where m is the table size. The quality of the function' ic fit; conversely, a function that scatters indices unpredictably but evenly approaches the ideal.
哈希函数接收一个键（如字符串或整数）并计算出一个整数，作为哈希表的索引。最简单的例子是取模函数：h(k) = k mod m，其中 m 是表的大小。函数输出分布的质量直接决定拟合优度。若函数对不同输入总是产生相同索引，拟合度极差；反之，若函数能不可预测但均匀地分散索引，就接近理想状态。
Common hash functions studied at A-Level include the division method (modulo), the midsquare method, and the folding method. For string keys, one might sum the character codes and then apply modulo m. A good hash function should also be fast to compute, deterministic, and make use of the entire key space to reduce bias.
A-Level 阶段学习的常见哈希函数包括除留余数法（取模）、平方取中法和折叠法。对于字符串键，可以先将字符编码求和，再对 m 取模。一个好的哈希函数还应计算迅速、确定性高，并能利用整个键空间以减少偏差。
3. Uniform Distribution: The Ideal | 均匀分布：理想状态
An ideal hash function exhibits perfect uniformity: each of the m slots receives exactly the same probability of being selected for any given key, i.e., 1/m. Under this assumption, the distribution of keys among slots follows a uniform distribution. The goodness of fit is then measured by how closely the actual distribution after inserting n keys matches this expected uniform model.
理想哈希函数呈现完美的均匀性：对于任意给定的键，每个槽位被选中的概率完全相同，均为 1/m。在此假设下，键在槽中的分布服从均匀分布。拟合优度就通过比较插入 n 个键后实际的分布与这一均匀预期模型的接近程度来衡量。
When a hash function achieves near-uniform distribution, the average number of keys per slot – the load factor – remains balanced, and even if collisions occur, they are spread across the table rather than concentrated. This behaviour keeps linked lists (in separate chaining) short and probing sequences (in open addressing) short, maintaining efficiency.
当哈希函数实现近均匀分布时，每个槽的平均键数——负载因子——保持均衡，即使发生冲突，也会分散在整张表中而非集中一处。这种特性使得分离链接法中的链表保持较短，开地址法中的探测序列也较短，从而维持高效率。
4. Measuring Goodness with the Chi-Squared Test | 用卡方检验度量拟合度
served number of keys in slot i, and the expected frequency E = n/m under uniformity. The chi-squared statistic is then calculated as:
量化拟合优度的一种统计方法是使用卡方（χ²）检验。对于具有 m 个槽位的哈希表，插入 n 个键后，设 Oᵢ 为槽 i 中实际存储的键数，均匀分布下的期望频率 E = n/m。卡方统计量计算如下：
χ² = Σ (Oᵢ − E)² / E, for i = 0 to m‑1
A small χ² value indicates that the observed distribution is close to the expected uniform distribution, signifying a good fit. In practice, developers may not compute this formally during runtime, but the principle guides the design phase: a hand‑test with sample keys can reveal bias before deployment.
较小的 χ² 值表示观测分布接近预期的均匀分布，说明拟合良好。实践中，开发者通常不会在运行时正式计算此值，但这一原理指导设计阶段：在部署前用样本键进行手动测试即可发现偏差。
For A-Level exam questions, you might be asked to evaluate a hash function by looking at the final table and commenting on whether the keys are evenly spread. You can describe clustering patterns, count empty slots, or even refer to the chi‑squared concept to justify your conclusion.
在 A-Level 考试中，你可能会被要求通过观察最终哈希表来评价一个哈希函数，评论键是否均匀分布。你可以描述聚集模式、统计空槽数量，甚至引用卡方概念来支持你的结论。
5. Load Factor and Its Effect on Fit | 负载因子及其影响
The load factor α is defined as n/m, where n is the number of stored entries and m is the table size. While α does not directly measure the evenness of distribution, it interacts strongly with goodness of fit. Even a well‑designed hash function will suffer a degradation in performance if α becomes too high, because more keys per slot inevitably increase collision chains.
负载因子 α 定义为 n/m，其中 n 为已存储条目数，m 为表大小。虽然 α 并不直接衡量分布的均匀程度，但它与拟合优度密切相关。即使哈希函数设计得再好，若 α 过高，由于每个槽的键数增加，冲突链不可避免地变长，性能依然会下降。
tain short linked lists. In open addressing, α must be strictly less than 1, and typical implementations rehash when α exceeds about 0.6 to 0.7. A poor goodness of fit will cause the table to behave as if it is fuller than it really is, triggering premature rehashing or excessive collisions.
在分离链接法中，通常保持 α ≤ 1，并往往要求低于 0.75 以保证链表较短。在开地址法中，α 必须严格小于 1，典型的实现会在 α 超过约 0.6 至 0.7 时进行再哈希。较差的拟合优度会使表表现得比实际更满，从而过早触发再哈希或产生过多冲突。
6. Primary and Secondary Clustering | 主聚集与次聚集
Clustering is a direct symptom of poor goodness of fit. Primary clustering occurs in open addressing when keys that hash to different initial indices become 'bunched' together because the probing sequence forces them to follow the same path. For example, with linear probing, once a block of consecutive occupied slots forms, new keys that hash anywhere into that block must traverse the entire cluster, making it grow rapidly.
聚集是拟合优度差的直接表现。主聚集发生在开地址法中，由于探测序列强制让原本散列到不同初始索引的键聚在一起。以线性探测为例，一旦形成连续占用槽块，散列到该块内任何位置的新键都必须遍历整个聚集区，导致其迅速扩大。
Secondary clustering is a milder phenomenon where keys that hash to the same initial index follow the same probing sequence, but keys with different initial indices do not interfere. This is typical in quadratic probing and double hashing, and while it does not degrade performance as severely as primary clustering, it still indicates that the hash function alone has not achieved perfect uniformity.
次聚集是一种较轻微的现象：散列到相同初始索引的键会遵循相同的探测序列，但不同初始索引的键不会互相干扰。这种情况常见于二次探测和双重哈希，虽然它对性能的损害不如主聚集严重，但仍然反映出仅靠哈希函数未能实现完美的均匀性。
7. Collision Resolution Strategies and Fit | 冲突解决策略与拟合
The choice of collision resolution method can either compensate for or amplify a poor fit. Separate chaining is relatively forgiving; even if goodness of fit is suboptimal, the linked lists absorb extra keys without destabilising the table. However, scanning long chains still hurts performance, so a good hash function remains important.
冲突解决方法的选择可以弥补或放大较差的拟合度。分离链接法相对宽容；即使拟合优度不理想，链表也能容纳额外的键而不会破坏表的稳定性。但是扫描长链表依然会降低性能，因此良好的哈希函数仍然很重要。
In open addressing, the probing interval determines how clustering manifests. Linear probing suffers badly when fitness is low because it forms long contiguous runs. Double hashing uses a second hash function to produce probe intervals, effectively giving each key a different 'skip' step; this often improves the observed goodness of fit because it scatters keys more evenly, even if the first hash function is only moderately good.
在开地址法中，探测间隔决定了聚集的表现形式。拟合度低时，线性探测严重受损，因为它会形成长连续占位区。双重哈希使用第二个哈希函数生成探测步长，有效地为每个键提供了不同的‘跳跃’距离；即便第一个哈希函数质量一般，这也常能改善观测到的拟合优度，因为它更均匀地分散了键。
8. Rehashing to Restore Good Fit | 再哈希以恢复良好拟合
Rehashing is the process of creating a new, larger hash table and reinserting all existing keys using the (possibly modified) hash function. This operation is triggered when the load factor exceeds a threshold or when the current distribution is heavily clustered. Rehashing provides an opportunity to improve goodness of fit by resizing to a prime number of slots or by refining the hash function itself.
再哈希是指创建一个新的、更大的哈希表，并使用（可能经过调整的）哈希函数重新插入所有现有键的过程。当负载因子超过阈值或当前分布严重聚集时，就会触发此操作。再哈希通过将表大小调整为质数或优化哈希函数本身，为改善拟合优度提供了机会。
A typical strategy is to double the table size and choose the new size as a prime number not close to a power of two, to avoid biases in modulo‑based hash functions. After rehashing, the keys should be more evenly distributed, effectively resetting the goodness of fit and lowering α. At A‑Level, you may be required to simulate rehashing with given data and comment on the resulting distribution.
一种典型策略是将表大小加倍，并选择一个不接近 2 的幂的质数作为新大小，以避免取模哈希函数的偏差。再哈希后，键的分布应更加均匀，有效重置拟合优度并降低 α。在 A‑Level 考试中，你可能需要根据给定数据模拟再哈希过程，并对结果分布作出评论。
9. Examples: Good vs Poor Hash Functions | 实例分析：好与差哈希函数
14, 28, 45, 72, 93, 101. A poor hash function h(k) = k mod 10 would map: 4, 8, 5, 2, 3, 1 – m. But if keys were 10, 20, 30, 40, 50, the same function maps all to slot 0, giving a chi‑ ndicating a very poor fit. A better function could be h(k) = (k² + k) mod 10, or using mid‑square extraction before mod.
考虑一个大小为 m = 10 的表，键为：14, 28, 45, 72, 93, 101。较差的哈希函数 h(k) = k mod 10 映射为：4, 8, 5, 2, 3, 1 – 看起来均匀。但如果键是 10, 20, 30, 40, 50，同样的函数会将所有键映射到 0 槽，χ² 值为 25（假设 5 个键，每槽期望 0.5），表明拟合极差。更好的函数可以是 h(k) = (k² + k) mod 10，或者在取模前使用平方取中法。
The table below demonstrates the slot occupancy after inserting the second set of keys using two different hash functions. Notice how the folding method scatters keys more effectively, achieving a higher goodness of fit.
下表展示了使用两种不同哈希函数插入第二组键后的槽占用情况。可以看出折叠法更有效地分散键，实现了更高的拟合优度。
| Slot | Mod 10 (poor) | Folding method (better) |
|---|---|---|
| 0 | 5 | 0 |
| 1 | 0 | 1 |
| 2 | 0 | 1 |
| 3 | 0 | 1 |
| 4 | 0 | 0 |
| 5 | 0 | 1 |
| 6 | 0 | 0 |
| 7 | 0 | 1 |
| 8 | 0 | 0 |
| 9 | 0 | 0 |
10. Exam Tips and Summary | 考试技巧与总结
When faced with an exam question on goodness of fit, start by explaining what it means: a measure of how uniformly a hash function distributes keys. Support your answer by referring to the load factor, clustering, and collision resolution. If a table is given, point out clusters, count the number of empty slots, and contrast with the expected occupancy.
面对关于拟合优度的考题时，首先解释其含义：衡量哈希函数分配键的均匀程度。通过引用负载因子、聚集和冲突解决来支撑你的回答。如果给出了哈希表，指出聚集区域，统计空槽数，并与预期占用情况进行对比。
Remember that a function with a high goodness of fit does not guarantee zero collisions; it guarantees that collisions are minimised and evenly spread. Common pitfalls include confusing load factor with fit, or assuming that a bigger table automatically results in a better fit – resizing alone cannot fix a biased hash function. Always aim to use precise terminology such as 'uniform distribution', 'chi‑squared', and 'clustering' where appropriate.
记住，高拟合优度的哈希函数并不能保证零冲突；它保证冲突被最小化且均匀分布。常见的陷阱包括将负载因子与拟合度混淆，或认为更大的表会自动带来更好的拟合——仅靠调整大小无法修复有偏的哈希函数。尽量使用‘均匀分布’、‘卡方’、‘聚集’等精准术语。
Finally, in the Edexcel assessment, marks are awarded for demonstrating an understanding of the trade‑off between hash function design and collision handling, and for evaluating the effectiveness of a given hash table configuration. Mastering goodness of fit will put you in a strong position to tackle both short‑answer and extended‑writing questions on data structures.
最后，在 Edexcel 考试中，展现出对哈希函数设计与冲突处理之间权衡的理解，以及对给定哈希表配置有效性的评价，将获得高分。掌握拟合优度将使你在数据结构的简答题和长篇作答题中游刃有余。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图