分离链接法与性能分析

分离链接法

分离链接法也称拉链法、链地址法，将相应位置上有冲突的所有关键字存储在同一个单链表中。

例如关键字序列为{47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21}，哈希函数h(key) = key % 11，用分离链接法处理冲突。

分离链接法

性能分析

哈希表的平均查找长度（ASL, Average Search Length）用来度量哈希表查找效率。关键字的比较次数，取决于产生冲突的多少。影响产生冲突多少有三个因素：

1. 哈希函数是否均匀

2. 处理冲突的方法

3. 哈希表的装填因子$\alpha$

采用开放地址法时，合理的最大装填因子$\alpha$通常不超过0.85；分离链接法的装填因子可以大于1，选择合适的哈希函数可以使哈希表的查找效率期望是常数$O(1)$，它几乎与关键字的空间大小n无关。这是以较小的$\alpha$为前提，因此哈希表是一个以空间换时间的结构。

哈希表的存储对关键字是随机的，因此哈希表不便于顺序查找、范围查找、最大值/最小值查找等操作。