数据结构——拉链法（链地址法）

- 日理万妓 2023-06-20 15:58 128阅读 0赞

当存储结构是链表时，多采用拉链法，用拉链法处理冲突的办法是：把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T\[0..m-1\]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T\[i\]为指针的单链表中。T中各分量的初值应为空指针。  
　　例如，按上面例9.4所给的关键字序列，用拉链法构造散列表如图９.14所示。

![aHR0cDovL21lZGlhLm9wZW5vbmxpbmUuY29tLmNuL21lZGlhX2ZpbGUvcm0vemhvbmdrZWRhMjAwNi9zaHVqdWppZWdvdS9saW5rL2NvbnRlbnQvaW1hZ2VzLzk0MzEuZ2lm][]  
　　用拉链法处理冲突，虽然比开放定址法多占用一些存储空间用做链接指针，但它可以减少在插入和查找过程中同关键字平均比较次数(平均查找长度)，这是因为，在拉链法中待比较的结点都是同义词结点，而在开放定址法中，待比较的结点不仅包含有同义词结点，而且包含有非同义词结点，往往非同义词结点比同义词结点还要多。  
　　如前面介绍的例9.4中，用线性探测法构造散列表的过程，我们知道，对前5个关键字的查找，每一个仅需要比较一次，对关键字49和24的查找，则需要比较2次，对关键字38的查找则需要比较4次，而对43的查找则需要比较3次。因此，对用线性探测法构造的散列表的平均查找长度为：  
　　　　ASL=(1×5＋2×2＋3×1＋4×1)/9 ≈1.78  
而用拉链法构造的散列表上查找成功的平均查找长度为：  
　　　　ASL=(1×5+2×3+3×1)/9≈1.55  
显然，开放定址法处理冲突的的平均查找长度要高于拉链法处理冲突的平均查找长度。但它们都比前面介绍的其它查找方法的平均查找长度要短。

[aHR0cDovL21lZGlhLm9wZW5vbmxpbmUuY29tLmNuL21lZGlhX2ZpbGUvcm0vemhvbmdrZWRhMjAwNi9zaHVqdWppZWdvdS9saW5rL2NvbnRlbnQvaW1hZ2VzLzk0MzEuZ2lm]: https://imgconvert.csdnimg.cn/aHR0cDovL21lZGlhLm9wZW5vbmxpbmUuY29tLmNuL21lZGlhX2ZpbGUvcm0vemhvbmdrZWRhMjAwNi9zaHVqdWppZWdvdS9saW5rL2NvbnRlbnQvaW1hZ2VzLzk0MzEuZ2lm