哈希（hashtable）表，查找方式的颠覆者！

淡淡的烟草味﹌ 2023-06-15 13:25 29阅读 0赞

### 目录 ###

*  前言
 *  一、比较查找方式
 *  二、查找方式颠覆者
 *   *  数据结构
     *  存入
     *  取出
     *  鸡肋？
 *  三、改良hash函数
 *  四、哈希冲突
 *   *  1.链地址法
     *  2.开放寻址法
     *   *  线性探测
         *  二次探测
         *  再哈希

--------------------

# 前言 #

这是这个系列的最后一篇文章，与哈希表（Hash table）结缘也是在分析JDK1.8以后HashMap源码的时候，因为HashMap一共用到了三种数据结构——链表、红黑树、哈希表。之后为了学习红黑树，又把而二叉树、二叉排序树（搜索树）复习了一遍，并促成了这个系列的文章。

# 一、比较查找方式 #

不论是数组、链表还是二叉树、二叉排序树（搜索树）、红黑树，我们要找到其中特定的一个元素，方法只有一个那就是挨个比较直到找到为止，这就造成了查找的时间复杂度总是与N有关系。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>二叉树</th> 
   <th>二叉排序树</th> 
   <th>红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>查找</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
   <td>O(log N)~O(N)</td> 
   <td>O(log N)</td> 
  </tr> 
 </tbody> 
</table>

**数组**：假设数组中有N个元素，我们要找到其中一个特定的元素，通常要进过N/2次比较，所以时间复杂度上来说还是O(N)。如果数组是有序数组的话，相当于折半查找，此时的时间复杂度是O(log N)。

**链表**：同理与数组，假设有N个元素，要找到其中一个特定的元素，时间复杂度还是O(N)。

**二叉树**：注意是二叉树，左、右节点之间没有大小关系，实在不明白，可以看看这篇文章[二叉树（从建树、遍历到存储）Java][Java]。此时要从N个节点中找到特定的节点，时间复杂度是O(N)。

**二叉排序树**：此时父节点与左、右子节点之间就有大小关系了。在节点分布均匀的情况下相当于折半查找，所以时间复杂度是O(log N)，一般情况下时间复杂度在O(N)到O(log N)之间。

**红黑树**：虽然红黑树在插入、删除操作上很是麻烦，但是对于查找操作跟二叉排序树是一模一样的，因为红黑树不过是加了平衡算法的二叉排序树而已，二叉排序树最基本的父节点与左、右子节点之间的大小关系肯定是满足的，所以时间复杂度是O(log N)。

只看表达式的可能感觉不强烈，那我们假设N=1000000。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>二叉树</th> 
   <th>二叉排序树</th> 
   <th>红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>查找</td> 
   <td>1000000</td> 
   <td>1000000</td> 
   <td>1000000</td> 
   <td>20~1000000</td> 
   <td>20</td> 
  </tr> 
 </tbody> 
</table>

注意：有人可能会说，二叉排序树这个跨度也太大了吧，嗯嗯，这也是为什么要用红黑树的原因。

# 二、查找方式颠覆者 #

看了比较查找方式的时间复杂度之后，哈希查找方式绝对称得上是颠覆者，因为他彻底跟N说拜拜~~~~ 使时间复杂度降到O(1)。

我们以存储英语单词dog、cat、pig、sheep为例看看哈希表的工作机制。

## 数据结构 ##

哈希表听上去没上面那些数据结构那么直白，它其实是以数组为基础的。那我们就新建一个长度为58的字符串数组。

## 存入 ##

（1）计算下标：我们以a对应1，z对应26的编码方式，计算上面四个单词的下标，分别为  
dog = 4 + 15 + 7 = 26  
cat = 3 + 1 + 20 = 24  
sheet = 19 + 8 + 5 + 5 + 20 = 57  
pig = 16 + 9 + 7 = 32

（2）存储：之后我们就把单词dog存入到数组下标为26的单元中，其他三个单词同理分别存储到数组下标为24、32、57的单元中。

## 取出 ##

（1）计算下标：如果我们要取出cat，那就再用上面的算法，计算出在数组下标为24的单元中，这样就可以得到单词cat了。

## 鸡肋？ ##

看了取出操作可能会有人有这样的疑问，既然我都知道cat了，还计算cat在数组中的存储下标，再取出cat？这什么操作？？？？  
![在这里插入图片描述][20191220115535437.png]

既然说到这里那就再提出两个问题，（1）为什么HashSet没有get方法？；（2）为什么HashMap有get方法？

这两种集合类都是基于hash表的。（1）HashSet没有取出指定元素的方法，就是因为它只有存入的操作，不会有取出的操作。不论你要取set集合中的哪个元素，你都**必须**把这个元素给我，我计算下标把这个元素找到，再返回给你。既然我都知道这个元素了，我还有你给我干嘛？所以HashSet中不会有取出指定元素的方法，只能整体遍历。

（2）HashMap则不同，它存储的是键值对。在存入的时候根据**键**计算得到存储下标，存入键值对；取出的时候把**键**给我，我计算下标找到对应的位置，把**值**返回给你。

# 三、改良hash函数 #

**什么是哈希函数？**  
就是上面我们用来计算存储下标的算式。但上面这种哈希函数明显不及格，因为非常浪费存储空间，我们创建了一个长度为58的哈希表却只存了四个元素。

那我们改良一下，把相加得到的结果再取余  
dog = 4 + 15 + 7 = 26  
cat = 3 + 1 + 20 = 24  
sheet = 19 + 8 + 5 + 5 + 20 = 57  
pig = 16 + 9 + 7 = 32

dog = 26 % 4 = 2  
cat = 24 % 4 = 0  
sheet = 57 % 4 = 1  
pig = 32 % 4 = 0

这样只用创建一个长度为3的哈希表就可以存储下这四个元素了。（上面再取余后得到两个0，这是**哈希冲突**，暂时不管，刻意地安排，为了引入相关内容。）

**哈希函数深入研究**  
不讨论深入研究。哈希函数的算法设计是哈希表的精髓，既要不浪费存储空间，又要避免哈希冲突，真的好难哦，我们难道真的要殚精竭力整起算法？参考一下JDK源码就行了呗。下面取自 JDK1.8版本HashMap的源码。

if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);

tab是一个数组，其中“(n - 1) & hash”就是计算存储下标的哈希函数。&运算符相当于取余运算，具体参考这篇文章[使用与运算符代替求余运算符的技巧][Link 1]

# 四、哈希冲突 #

从上面的伏笔说起。在取余后得到了两个0，cat和pig都想存到下标为0的单元格中，这就是哈希冲突。既然发生了冲突，那肯定有解决的办法，主要有两个，一是链地址法、二是开发寻址法。

## 1.链地址法 ##

因为**HashMap中采用这种方式** ，所以我们重点介绍。

还是上面的例子我们有：  
dog = 26 % 4 = 2  
cat = 24 % 4 = 0  
sheet = 57 % 4 = 1  
pig = 32 % 4 = 0

链地址法解决冲突的方式就是在哈希表的每个单元格中设置链表，当有多个元素经过哈希函数计算后得到同一个存储位置，只需要加到链表中即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70_pic_center]  
第一步在哈希表中找到存储位置的操作是常数级的，即时间复杂度是O(1)，但是之后在链表中的相关操作却是O(N)的，所以在JDK1.8之后版本的HashMap中引入了红黑树，当链表中的节点个数大于等于8个的时候，就将该链表转换成红黑树以提高效率。

所以实际中的HashMap底层数据结构是这样的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70_pic_center 1]

## 2.开放寻址法 ##

开放寻址法又包括三种解决冲突的方式：线性探测、二次探测、再哈希。

### 线性探测 ###

还是上面的例子  
dog = 26 % 4 = 2  
cat = 24 % 4 = 0  
sheet = 57 % 4 = 1  
pig = 32 % 4 = 0

0是pig要存入的位置，它已经被cat占用了，那就使用1，之后是2，依次类推，数组下标一直递增，直到找到空位。这就叫做线性探测。

### 二次探测 ###

在线性探测中，如果哈希函数计算的原始下标是x，线性探测就是x+1，x+2，x+3，依次类推。而在二次探测中，探测的过程是x+1，x+2的平方，x+3的平法，x+4的平法，依次类推。

### 再哈希 ###

即用另一个哈希函数再计算一遍，并以这个值作为探测的长度。

[Java]: https://blog.csdn.net/dabusiGin/article/details/102785510
[20191220115535437.png]: https://img-blog.csdnimg.cn/20191220115535437.png
[Link 1]: https://www.cnblogs.com/encode/p/7155147.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20191222165621727.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20191223143137484.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg==,size_16,color_FFFFFF,t_70#pic_center