然后是HashTable类的骨架(我在这里把它封装成类了):
接下来是构造函数:
先略去哈希函数,介绍插入函数:
然后是查找:
当然可以根据具体情况做各种改动,如果要极限追求效率可以在t_node里面把key改为指针,然后使用自己编写的内存分配函数代替new。最简单的哈希函数:其实最简单的哈希表1就是H(x)=x,意思是若记录对象是整数,就直接采用这个整数为下标(char类型也可视为整数),这个就是数组,但它也可以看作哈希表。最简单的哈希表2就是H(x)=1,意思是不管是什么元素都放到同一个下标,这个就是链表,也可视为一种哈希表。大整数的哈希函数:当记录对象是大整数的时候,若再用H(x)=x,数组的范围将会承受不起,所以这时候要考虑哈希函数的设计问题,又有很多种设计方法,最广泛的一种就是H(x)=x%k,k通常是一个质数。一般的哈希函数:我们也许会记录一些class或者struct之类的东西,这时候我们可以选取里面的某些关键变量进行一种运算来确定下标。冲突的处理:再好的哈希函数也很难避免冲突,所谓冲突就是说H(a)=H(b)的情况,而开散列的处理方法是在数组后面挂的是链表,这样冲突的元素可以直接挂在链表的末端,而闭散列没有链表,一般是重复Hn(x)或者往H(x)+a(a=1,2,3..)寻找,这会使哈希表变得一塌糊涂,而且冲突还可能引发别的冲突,而且也不便于估计哈希数组的范围,所以鄙人不提倡使用闭散列的组织方式。顺便说一句:好的哈希函数是尽量减少和平衡冲突,尽量使得每个链的长度分布得平均,好的哈希函数的设计要靠长久的经验积累,绝非一日之功。哈希表的本质思想:散列表本质思想就是把数组与链表的优势结合起来,数组的访问复杂度是O(1),链表的插入复杂度是O(1),然而数组的插入复杂度和链表的访问复杂度都比较高,所以就产生了散列表。我们可以把这个思想运用到许多地方,这本是我想说的重点,但鄙人才疏学浅,不知如何表达,日后整理一下代码说明吧。