理论与进阶专题
哈希函数
哈希函数接受一个键——字符串、数字、任何数据——把它压缩成一个固定大小的数，常用作一个桶数组的下标。可以把它想成寄存处的工作人员：你递上一件任意形状的外套，拿回一个带号码的小牌子。它的意义在于，把「我该把它存到哪、又去哪找？」从一次搜索变成一次计算：把键喂给函数，得到桶号，直奔那里。
用于数据结构的好哈希函数有三个特点。它要快，因为每次查找都要算它一遍。它要确定——同一个键必须永远算出同一个数，否则你永远找不回存进去的东西。它还要把键均匀地撒到各个桶里，让相近的键也落到不同位置，使各桶大致均衡，而不是把所有东西都堆进一个桶。具备这些性质，哈希表平均就能以 O(1) 找到一个键。
有一个躲不掉的坑：冲突是不可避免的。当你把一个庞大的可能键空间映射到有限个桶时，鸽笼原理保证总会有两个不同的键落进同一个桶——鸽子就是比笼子多。好的哈希函数能让冲突稀少且分布均匀，却无法让它绝迹，因此任何基于哈希的结构还得有一套办法（如链地址法或开放定址法），来应对两个键相撞时该怎么办。
// deterministic, fast, spreads keys across m buckets
int hash(const std::string& key, int m) {
unsigned long h = 1469598103934665603ULL; // a seed
for (char c : key) {
h ^= (unsigned char)c;
h *= 1099511628211ULL; // mix the bits
}
return (int)(h % m); // confine to [0, m)
}相同输入永远得到相同的桶；取模把它限定在 [0, m) 内。
密码学哈希（如 SHA-256）追求的是另一个目标——难以逆推。数据结构里的哈希只需快、且把键撒得均匀。
又称
另见