Day 13：杂凑表(hash table)

在通讯录或朋友列表里，我们可以搜寻一个名字，就找到电话或页面，只需要O(1)。如果想要实现这样的操作，可以想像一种融合上一回阵列和链结串列的资料结构。

杂凑表是可以储存键(key)和值(value)的资料结构，但它并不是像试算表一样，只是单纯地把「John Smith」和他的电话「521-1234」存在一起。它做的事情比较像是，当我们输入John Smith，可以找到他的电话的储存位址。而杂凑表就是透过杂凑函式的运算，来做到这种比较复杂的结构。

杂凑函式可以输入资料，并回传一个值。以下图为例，杂凑函式将John Smith这个字串转为一个杂凑值(02)，并以这个值作为阵列的索引，将John Smith的电话储存在这个位址。换句话说，透过杂凑函式，我们可以得到一个资料存放的位址。

杂凑函式的特性是：

理想的情况下，我们希望每个资料都有一个独一无二的阵列位址，这样存取所有的资料都可以实现O(1)，可是当资料量很大时，必须考虑阵列的储存空间，而且很难实现杂凑函式回传的值都不重复，所以必须想办法解决杂凑冲突的问题。

举例来说，如果有一个英文名单，我们用杂凑函式将所有人名的第一个字母转为0-25的其中一个数字，存在长度为26的阵列中。

那很快就会出现冲突的情况，因为名字开头字母很容易重复。冲突的一个解决方法是使用链结串列(linked list)，我们可以使用链结串列储存索引位置相同的资料(如下图)。这种情况的杂凑表基本上就是每个元素都是一个链结串列的阵列。

但这时候可能又有另一个问题，假设名单里S开头的人名特别多，那就会变成阵列中S的索引位置是一个超长的链结串列，而其他位址是空的，那麽其实跟直接把名单存在一个链结串列中没有两样，存取也会变得非常没有效率。

所以由此可知，一个好的杂凑函式要能减少冲突的发生、让资料平均分布在杂凑表中，提升资料结构的效率。要从零开始设计出一个时间空间效率俱佳的杂凑函式不是非常容易，不过好消息是在开发时基本上不会需要自己撰写杂凑函式，各种语言的函式库里都有效能不错的杂凑函式可以直接使用。