点击蓝字 关注我们

★哈希表（散列表）

今天小企鹅和大家分享和学习我们数据结构与算法中哈希表的一些知识。首先先问两个问题什么是哈希表？我为什么要去用他呢？

哈希表又称散列表。

哈希表存储的基本思想是：以数据表中的每个记录的关键字 k为自变量，通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。这是我们哈希表的定义和原理，接下来我们看看具体例子；

哈希表存储原理

例如我们现在要存的数据是（3,15,22,24）

存储到我们编号为0到4的表长为5的哈希表中，如果我们的哈希函数是：K(k)=k%5;

那将会得到下面的哈希表：

现在这样看看是没有什么问题，但是经过这样计算有没有计算结果一样的呢？答案肯定是有的，比如我现在要把数据25存进去然后我发现计算25%5=0，那把它放到0的位置，但是0的位置已经放了15了。我们把这种数据不一样但是经过哈希函数计算后的结果是一样的叫冲突，我们研究哈希表就是要研究：

1、我们如何设计我们的哈希函数，可以尽可能地减少我们冲突。

2、如果实在避免不了我们应该如何解决这个问题。

哈希表的常用构造方法

一、直接地址法：

直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。该哈希函数H(k)为： H(k)=k+c (c≥0)

2．除留余数法

取关键字k除以哈希表长度m所得余数作为哈希函数地址的方法。即： H(k)=k％m

注：在m取值为素数（质数）时，冲突可能性相对较少。

还有一些比较多的构造方法感兴趣可以自己去查找资料，因为说白了这部分就没固定的知识可以讲的。

冲突的解决办法

已知哈希表地址区间为0～10，给定关键字序列 （20，30，70，15，8，12，18，63，19）。哈希 函数为H(k)=k％11，

这个才是重点要了解的，当遇到冲突的时候我们解决，解决班也有很多种，我就挑一个比较好的解决办法讲一下——链地址法：

用链地址法解决冲突的方法是：把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。并将这些链表的表头指针放在数组中（下标从0到m-1）。这类似于图中的邻接表和树中孩子链表的结构。

看到表的结构我们就知道他是怎么解决冲突的了，当发现计算的值产生冲突时你建立一个链表存放，直接就很好解决了冲突的问题。

那这样的表我们怎么查找和使用里面的值呢？举个例子：我们现在要查找63这个数，那我们首先按照哈希函数计算63%11=8，我就找到下标为8 的链表，然后就是按值查找链表，这样就完成了对数据的查找和使用。

希望看到这里对你理解哈希表有一定的帮助，哈希表其他没涉及到的知识点如果感兴趣你可以私信我，可以一起探讨一下。