本专栏中，我们会围绕一些有意思的数据结构展开讨论，希望能够帮助大家利用碎片时间熟悉这些数据结构背后的原理，共同体验技术之美，同时避免面试时 Naive. 欢迎大家在留言讨论，也可以留言建议写作主题！

散列函数与确定性

我们在上一篇文章中讨论了散列表（哈希表），并提到了散列函数。在散列表中，散列函数的作用就是根据 KEY 生成一个整数坐标，并给出了一个非常 NAIVE 的散列函数实现：

const int SIZE = 1024;
int hash(int x) { return x % SIZE; }

这个实现基本能满足散列函数最基本的要求：它首先是个函数，也即，对于同样的 KEY, 总是会给出相同的输出，我们下文将会称为「确定性」。这也很容易理解（甚至听起来有点废话）：对同一个 KEY 给出相同的输出才能保证从散列表中查表时能够找到之前存进去的元素。

散列表中需要根据 KEY 确定存储元素的桶，实际实现中通常分为两步，一是根据 KEY 生成一个整数，如 32 位无符号数，这个整数的取值范围常常是覆盖 32 位无符号数的全部取值范围。而后根据这个整数再进行取模等操作确定实际的桶编号。

对于整数作为 KEY, 第一步映射其实可以返回这个整数本身，也就是 hash(x)=x. 如果你对 Python 比较熟悉，可以试着运行 hash(1), 结果就是 1.

下文讨论中，我们主要针对第一步，将兴趣集中在根据各种不同的数据结构输入，输出一个整数作为散列结果。

散列函数与随机性

除「确定性」外，我们其实是希望散列函数的输出尽可能的随机、没有规律。因为对于散列表而言，散列函数的随机性越好，越能保证数据在散列表上随机分布，最大限度避免碰撞。比如，如果我们的存储的 KEY 是个浮点数，而且都在某个值附近，散列函数完成映射后，最好能让输出值的分布尽可能的毫无规律，而不是也挤在一起，这才能最大限度避免碰撞。

由于「尽可能随机」这个要求，散列函数其实有点像伪随机数发生器：KEY 就是随机数种子，根据种子生成一个随机数，并且两者的性能指标都能归结为「尽可能的没有规律」。不同的是，随机数发生器我们其实希望它「真的」毫无规律，多数应用中我们会希望它不需要一个种子。但散列函数则是，「被 KEY 唯一确定，但在此前提下尽可能随机」。另一个不同是散列函数的 KEY 可能是各种不同的数据结构。

散列函数的其他要求，大都可以归结为「尽可能的随机」。如上文中提到的，多数应用中会希望散列函数对于「接近」的 KEY 给出尽量无关的输出。同时，也希望散列函数尽可能的跟整个 KEY 有关。比如，字符串作为 KEY，则希望散列函数跟整个字符串有关，而不是跟字符串的某个部分有关。这样能避免输入中含有大量相似的字符串时发生碰撞。

散列函数与数据类型

考虑这样一个问题：假设我们现在已经有一个无符号 64 位整数的散列函数，想要实现一个有符号数的散列函数。（请思考 30 秒。。。）

我们其实可以直接强制类型转换为无符号数，然后使用无符号数的散列函数：毕竟我们只要保证「确定性」就行了，做什么操作都没有关系，甚至是 -1 被强制类型转换为 UINT_MAX 也没有关系。甚至对于浮点数，也可以强制类型转换为无符号数求散列。类似的，所有的指针类型，都可以强制类型转换为整数来求散列。

这里提到的对浮点数强制类型转换不是指各种编程语言提供的强制类型转换操作，而是指直接对浮点数指针类型擦除、再类型转换。可以粗暴地理解为，拿到存这个数据结构的指针，不管那个位置上实际上是什么东西，只要字段在物理内存上长度跟无符号数相同，就统统视为无符号数进行处理。

但对于字符串这种变长（而且可能比各种数长的多）的数据结构，我们需要开动脑筋为它设计一个散列函数。刚刚我们已经提到散列函数的硬性要求只有「是个函数，对于相同的输入给出相同的输出」一条，因此不难设计出一些比较简单的散列函数，比如每个 Char 代表一个数字，然后求和。但加法是可交换的，这样的散列函数对于字符串不同的排列组合会给出相同的散列结果。稍加改进，一种实用的字符串散列算法是多项式散列函数：

// hash(s) = sum s[i] * (A ^ i)
// A 是个魔法数字（没有什么道理的数字）
// 「有人」指出 33 工作良好。。。
const int A = 33;
unsigned hash(string& s) {
    unsigned r = 0, a = 1;
    for(char c: s) {
        r += a * c;
        a *= A;
    }
    return r;
}

有了字符串散列函数之后，对于任何字节流，其实都可以使用字符串散列函数进行处理。更进一步，任何复杂对象，可以先序列化为字节流，再使用类似于字符串散列函数的散列函数进行处理。

写到这里，其实已经可以感觉到散列函数就像是一个「摘要」：对任何数据结构，生成一个固定长度的数据结构（如，一个 32 位整数）作为摘要。实际上，MD5, SHA1 等可以认为是字符串散列函数 (SHA1: Secure Hash Algorithm). 从「摘要」这个角度更加能够理解散列函数的特点：它最好能够最大限度总结原数据，因此，散列函数应该与原数据所有字段相关，通常不应该只对某一部分求散列；对原数据做任何不丢失信息的操作都不会影响散列性能，因此无论有无符号、是否为浮点数，只要字段长度一致，都可以强制类型转换后使用相同的散列函数。

由于这篇文章全是文字，太干了，估计读者大人的耐心差不多了，今天先到这里，下一篇继续吧。。。