查找算法【哈希表】 - 处理冲突的方法：链地址法 & 建立公共溢出区

查找算法【哈希表】 - 处理冲突的方法：链地址法 & 建立公共溢出区

【链地址法】

链地址法又被称为拉链法，指如果不同的关键字通过散列函数映射到同一地址，而这些关键字为同义词，则将所有同义词都存储在一个线性链表中，查找、插入、删除操作主要在这个链表中进行。

链地址法适用于经常进行插入、删除的情况。

【举个栗子】

例如，有一组关键字(14,36,42,38,40,15,19,12,51,65,34,25)，若表长为15，散列函数为hash(key) =key%13，则可采用链地址法处理冲突，构造该散列表。

[构造步骤]

按照关键字顺序，根据散列函数计算散列地址，如果该地址空间为空，则直接放入；如果该地址空间已存储数据，则采用链地址法处理冲突。

• hash(14)=14%13=1，放入1号空间后面的单链表中。
• hash(36)=36%13=10，放入10号空间后面的单链表中。
• hash(42)=42%13=3，放入3号空间后面的单链表中。
• hash(38)=38%13=12，放入12号空间后面的单链表中。
• hash(40)=40%13=1，放入1号空间后面的单链表中。
• hash(15)=15%13=2，放入2号空间后面的单链表中。
• hash(19)=19%13=6，放入6号空间后面的单链表中。
• hash(12)=12%13=12，放入12号空间后面的单链表中。
• hash(51)=51%13=12，放入12号空间后面的单链表中。
• hash(65)=65%13=0，放入0号空间后面的单链表中。
• hash(34)=34%13=8，放入8号空间后面的单链表中。
• hash(25)=25%13=12，放入12号空间后面的单链表中。

最终形成的链

【性能分析】

查找成功的平均查找长度。

假设查找的概率均等（12个关键字，每个关键字查找的概率均为1/12），查找成功的平均查找长度等于所有关键字的比较次数乘以查找概率之和。从上图可以看出，1次比较成功的有8个，2次比较成功的有2个，3次比较成功的有1个，4次比较成功的有1个，其查找成功的平均查找长度为ASLsucc =(1×8+2×2+3+4)/12=19/12。

查找失败的平均查找长度

本题中的散列函数为hash(key)=key%13，计算得到的散列地址为0,1,…,12，共有13种情况。假设查找失败的概率均等（13种失败情况，每种情况发生的概率均为1/13），则查找失败的平均查找长度等于所有关键字查找失败的比较次数乘以概率之和。当hash(key)=0时，如果该空间为空，则比较1次即可确定查找失败；如果该空间非空，则在其后面的单链表中查找，遇到空时，查找失败。如果在单链表中有两个节点，则需要比较3次才能确定查找失败。类似地，在hash(key)= 1,…,12时也如此计算，如下图所示：

在上图中有5个空，比较1次失败；有6个含有1个节点，比较2次失败；有1个含有2个节点，比较3次失败；有1个含有4个节点，比较5次失败。其查找失败的平均查找长度为ASLunsucc =(1×5+2×6+3+5)/13=25/13。

【建立公共溢出区】

除了以上处理冲突的方法，也可以建立一个公共溢出区，当发生冲突时，将关键字放入公共溢出区。

查找时，先根据待查找关键字的散列地址在散列表中查找，如果为空，则查找失败；如果非空且关键字不相等，则到公共溢出区中查找，如果仍未找到，则查找失败。