哈希表又称为散列表(hash)是一种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)时间复杂度仅为0(1)。

主要有六种构造方法

1、直接定址法

取关键字或关键字的某个线性函数为Hash地址,即H(key)=key或者H(key)=a*key+b,a、b都为常数。

2、数字分析法

取关键字的若干数位组成Hash地址。选择的原则是使得到的Hash地址尽量避免冲突,即所选数位上的数字尽可能是随机的。

3、平方取中法

取关键字平方后的中间几位作为Hash地址。通常在选定Hash函数的时候不一定能知道关键字的全部情况,仅取其中的几位为地址不一定合适,而一个数平方后的中间几位数和数的每一位相关,由此得到的Hash地址随机性更大,取的位数由表长决定。

4、除留余数法

取关键字被某个不大于Hash表表长m的数P除后所得的余数为Hash地址,即H(key)=key mod p(p<=m)。一般P选择为小于或者等于表长的最大素数。

5、折叠法

6、随机数法

哈希表冲突的四种解决方法:

1、开放地址法

1)线性探查法

2)  平方探查法

2、链地址法

链地址法就是把所有的同义词用单链表连接起来的方法。在这种方法中,Hash表每个单元中存放的不再是记录本身,而是相应同义词单链表的表头指针。

3、再散列法(再哈希法)

4、建立一个公共的溢出区


0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注