链地址法构造哈希表
-
利用链地址法构造哈希表是一种经典的散列技术，具有两大优点：①不存在冲突，即关键字都映射在一个准确的位置上；②它能够快速的查找到任意的一个元素，并且它对存储空间的利用可谓非常高效。首先我们来了解一下如何使用链地址法构造哈希表。
1、哈希表的结构
哈希表是一种基于数组的数据结构，其中的每一个元素存储一个关键字，以及一个指向下一个元素的引用，也被称为桶。在哈希表中，元素的存储化是基于哈希函数的，哈希函数的作用就是将输入的关键字映射为一个哈希地址，也可以称为散列函数，其作用是用来确定元素要存储在哈希表的哪一个桶中。
2、用链地址法构造哈希表
(1)利用哈希函数将输入的关键字映射成一个哈希地址，这个哈希地址指向一个桶，而这个桶存储着这个关键字，以及指向下一个元素的引用
(2)假如这个桶中存在其他的元素，则说明存在冲突，此时需要使用链地址法来解决这个冲突。首先将要插入的元素插入到桶中的末尾，然后将上一个元素的引用指向该元素，一直到找到桶的头结点，即最先插入的元素
(3)当插入新的元素时，应该在桶的头结点前插入新元素，即先将新元素的引用指向原有的头结点，然后将它插入到桶的前面，即成为新的头结点。
(4)当删除某个元素时，应该先找到它的前一个元素，将它的引用指向被删除元素的下一个元素，从而删除该元素。
以上就是链地址法构造哈希表的一般流程，除了空间利用效率高之外，它还具有插入、删除速度快以及查找元素本身更加快捷等优点。因此链地址法构造的哈希表深受各个领域的应用，在编程实现中尤其有优势。
24小时热点
热点专题
4247167 
