算法导论-哈希表

Introduction to Algorithms 3rd Edition

Part III - Data Structures

Chapter 11: Hash Tables

有一些应用场景需要在集合上有较多的插入、删除和查找的操作，要求时间复杂度越低越好。对于此类应用，为了通用性考虑，在不知道或者需要支持众多输入元素数据类型的情况下，一般是采用平衡的二叉树来实现，例如红黑树，这几中操作的平均性能都是O(lgn)。但是如果知道输入的数据类型，甚至知道输入数据的取值方式和范围的情况下，就存在一种更好的选择：哈希表。在理想的情况下，哈希表在插入、删除和查找上都能实现O(1)的时间复杂度，这也是我们梦寐以求的。

可以将哈希表看作一个大数组，将输入采用某种方式映射到数组中的特定位置，y = f(x)，当然，映射函数f的选择很重要，好的映射函数f能降低不同的x值取得同一个y值的概率。对于不同的数据类型，一般都会选择不同的哈希函数。设计合适的哈希函数是一个比较困难的问题。对于哈希表，由于其随机性，一般是分析平均情况下的时间复杂度。

当哈希表发生地址冲突时，解决办法一般是采用某种方法探测哈希表的另一个可用存储单元，直至找到可用的空位置。采用的方法一般有链地址法和开放地址法。链地址法比较简单，如果发生冲突，就在该地址上创建一个链表，将冲突的元素加入到链表中即可。开放地址法可以描述为 x' = x + g(i) (i = 1, 2, ...)。如果g(i) = i，就是线性探测再散列，也就是从冲突位置往后找到空位；如果g(i) = (-1)^(i+1)*((i+1)/2)^2，也即g(i) = 1^2, -1^2, 2^2, -2^2, ...，称为二次探测再散列。当然还有其它方法，比如再散列 g(i) = f'(x)等等。

不管怎样，哈希的终极目标就是在集合上的插入、删除和查找等操作的平均时间复杂度达到O(1)。

在哈希表上的时间复杂度分析比较复杂，涉及较多数学计算，在此表达不便，因此不涉及，有兴趣可以参考教材。