哈希表原理、底层实现剖析

一个在校大二学生，在CSDN记录自我成长！！！最近在自学数据结构和算法时，学到了哈希表，有很多地方都不明白。如何使用哈希表？原理是什么？如何工作的？我们如何设计哈希表？等等，所以就在网络上查了相关博客、资料等，总结了这些笔记。以便于日后复习。。

---

 目录

什么是哈希表？

为什么会有哈希表呢？

那么hash函数原理是什么呢？

如何实现哈希表呢？

哈希函数构造方法：

         构造哈希函数的三个要点：

哈希函数有哪些呢？

散列法：元素特征转变为数组下标的方法

    1.除法散列法

     2. 平方散列法

    3. 数字分析法：

现在存是存进去了，但是如何查找呢？

散列表的查找步骤

关键字——散列函数（哈希函数）——散列地址

哈希表优缺点分析

哈希表的应用

总结

---

下面我们进入正题，首先浅浅的了解一下哈希表：

什么是哈希表？

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构 。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度（在此之前的我们都是采用遍历来查找指定元素，当数据量庞大时（亿万级别），挨个遍历就显得很慢，而哈希表可以通过某个函数直接访问到指定元素，这就是哈希表的NB之处）。这个映射函数叫做散列函数或者哈希函数，存放记录的数组叫做散列表。

那么我们如何不通过遍历的方式而直接访问元素呢？下面就是玄妙所在：

——哈希函数（f）的格式：

• 记录的存储位置=f(关键字（key）)；
• 注释：通过对象的某个关键字在函数f中经过一系列计算，返回一个地址值，然后通过该地址值直接访问元素。

这里的对应关系f称为散列函数（什么是对应关系呢？就是我们要想将对象存到哈希表中，不得需要一个算法，这个算法就是对应关系，就像在一元函数中 x  可以通过一元函数求出对应的 y  ，此时一元函数就是对应关系），又称为哈希（Hash函数），采用散列技术将对象存储在一块连续的存储空间中（为什么会是连续的呢？这就涉及到哈希表的底层实现了（下面会一一讲述）。因为他的底层实现包含数组），这块连续存储空间称为 散列表或哈希表（Hash table); 

说到这里：不得不提一下equals方法了，因为我们常常会在一个类中重写equals方法，然而重写equals方法后，就会影响hash函数，具体影响可参考：

有关equals方法及equals方法重写知识点_南斋孤鹤的博客-CSDN博客_对象equals重写java自学之equals方法知识点总结equals重写注意点及完美建议、​instanceof 与getClass比较及如何选择：为什么重写equals后要重写hashcode?https://blog.csdn.net/m0_64231944/article/details/125352503?spm=1001.2014.3001.5501

为什么会有哈希表呢？

当然是现有的结构对一些特有的数据操作存在缺陷，就是有不足。具体是什么呢？下面我们了解：

之前我们学过数组和链表，下面对他们分析。

分析：数组存储方式的分析：

优点：通过下标方式访问元素，速度快。对于有序数组，还可以使用二分查找提高检索速度。

缺点：如果要检索某个具体的值，或者插入值（按一定顺序）会整体移动，效率较低。

链式存储方式的分析：

优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除的效率也很好）。

缺点：在进行检索时，效率仍然较低，比如（检索某个值，需要从头节点开始遍历）。

总结：

• 数组的特点是：寻址容易，插入和删除困难；
• 而链表的特点是：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构呢？相信你也瞬间明白了，这就是我们要说的哈希表数据结构了。。

---

那么hash函数原理是什么呢？

哈希表hashtable(key，value) 是将对象的Key通过哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，（这里为什么要提到数组？因为哈希表地底层实现是数组，这也随之带来了一些问题，后文解惑：）取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。）

这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

如何实现哈希表呢？

哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

很明显，哈希表就是有一个数组，数组中存储链表的头结点，每当加入新元素就先找到对应数组的索引，然后添加在该索引处的链表后面。

为了更了解哈希表，我们看一个在示例，思路分析图：

---

 该图取自：【尚硅谷】数据结构与算法（Java数据结构与算法）韩顺平老师的课程，讲的也很不错，想学习数据结构的同学，可以看一下这个课程，有很大帮助的。

---

上图定义了一个自定义类型的数组，然后在每个索引处存的都是一个链表，这样很容易看出哈希表是由  数组+链表   实现的。

哈希函数构造方法：

        哈希表的构造方法是：假设要存储的数据元素个数为n，设置一个长度为m（m≥n）的连续存储单元，分别以每个数据元素的关键字 Ki(0<= i <=n-1) 为自变量，通过哈希函数 hash(Ki) 把 Ki 映射为内存单元的某个地址 hash(ki)，并将该数据元素存储在该内存单元中。

从数学的角度来看，哈希函数实际上是关键字到内存单元的映射，因此我们希望用哈希函数通过尽量简单的运算，使得通过哈希函数计算出的哈希地址尽量均匀地被映射到一系列的内存单元中。这里均匀分布也是哈希表的一大亮点。

构造哈希函数的三个要点：

第一，运算过程要尽量简单高效，以提高哈希表的插入和检索效率；

第二，哈希函数应该具有较好的散列性，以降低哈希冲突的概率；

第三，哈希函数应具有较大的压缩性，以节省内存。

哈希函数有哪些呢？

一般有以下几种常见的方法：

散列法：元素特征转变为数组下标的方法

元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的：

    1.除法散列法

最直观的一种，上图使用的就是这种散列法，公式：

index = value % 16；

学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

     2. 平方散列法

求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：

index = （value*value）>> 28;

如果你不认识上面表达式中的“>>”,可以参考文章（有详细讲解）：

位移运算（“＜＜”和“＞＞”）详解_南斋孤鹤的博客-CSDN博客位移运算（“＜＜”和“＞＞”）详解https://blog.csdn.net/m0_64231944/article/details/126866111?spm=1001.2014.3001.5501

如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

    3. 数字分析法：

该方法是取数据元素关键字中某些取值较均匀的数字位来作为哈希地址的方法，这样可以尽量避免冲突，但是该方法只适合于所有关键字已知的情况。对于想要设计出更加通用的哈希表并不适用。

这个我自己也没看明白，就不瞎解释了。。

看到这里我想大家都在想一个很严重的问题：“如果两个字符串在哈希表中对应的位置相同怎么办？”,毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用“链表”。我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。

现在存是存进去了，但是如何查找呢？

散列表的查找步骤

• 当存储记录时，通过散列函数计算出记录的散列地址
• 当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

关键字——散列函数（哈希函数）——散列地址

优点：一对一的查找效率很高；

缺点：一个关键字可能对应多个散列地址；需要查找一个范围时，效果不好。

散列冲突：不同的关键字经过散列函数的计算得到了相同的散列地址。

好的散列函数=计算简单+分布均匀（计算得到的散列地址分布均匀）

哈希表优缺点分析

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。

优点：不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。

哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

哈希表的应用

1. Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。
2. 查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！

举一个例子，假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。

hash就是找到一种数据内容和数据存放地址之间的映射关系。

---

总结

以上讲解了哈希表的原理、底层实现，其中参考了许许多多的资料。其中多有尚未讲到的知识点、后面在自学中涉及到、我会持续更新和补充上的。

---

我已不再年少，我有爱的人，有要保护的人，怎么能不努力呢？怎么能像以往嘻嘻哈哈、无所事事，一无所成呢？

                                                                                ——致不在年少的我自己