散列表|HashTable - 哈希表 - 细节狂魔数据结构|哈希算法

文章目录

哈希表 / 散列表的概念
实践理解哈希表的运行原理
由上面实践，我们得知了哈希表存在哈希冲突的概念，下面我们讲讲哈希冲突的概念和解决办法。
- 冲突 - 概念
- 冲突 - 避免
- - 冲突 - 避免 - 哈希函数的设计
  - 常见的哈希函数
  - - 1、直接定制法 - （常用）
    - - 相关面试题 - [LeetCode - 387. 字符串中的第一个唯一字符](https://leetcode-cn.com/problems/first-unique-character-in-a-string/)
      - 题目分析与解题思路
        
        代码如下
      - 拓展: HashMap 思维
      - 代码如下
    - 2、除留余数法 - （常用）
    - 3、平方取中法 - （了解）
    - 4、折叠法 - （了解）
    - 5、随机数法 - （了解）
    - 数学分析法 - （了解）
- 冲突-避免-负载因子调节（重点掌握）
- - 负载因子和冲突率的关系粗略演示
- 冲突 - 解决
- - 冲突 - 解决 - 闭散列
  - - 1、线性探测
    - 插入操作
    - 为了能够均匀的分布冲突元素，二次探测由此而生。
  - 冲突-解决-开散列/哈希桶（重点掌握)
- 哈希表的性能分析
- 冲突严重时的解决办法
模拟实现简易的HashMap - 简单数据类型。
- 准备工作 - 程序框架
- put 功能
- - 第一步：找 key 的存储位置
  - 第二步：插入节点。
  - - 代码如下
    - - resize函数 - 扩容函数
      - 代码如下
- get功能
- 总程序
- - 效果图
模拟实现简易的HashMap - 引用数据类型。
- 有了这个，我们再去写》》程序框架
- put 方法
- get 方法
- 总程序
hash表和 java 类集的关系

哈希表 / 散列表的概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度（log2 N），搜索的效率取决于搜索过程中元素比较的次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到搜索的元素。如果构造一种存储结构，通过某种函数（hashFunc）使元素的存储位置与它的关键码之间能够建立一一映射的关系【怎么放的，怎么取出来】，那么在查找时通过该函数可以很快找到该元素【O(1)】。
?
当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功.
?
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

?
实践理解哈希表的运行原理

文章图片

?
由上面实践，我们得知了哈希表存在哈希冲突的概念，下面我们讲讲哈希冲突的概念和解决办法。冲突 - 概念

对于两个数据元素的关键字 K1 和 K2（互不相等），但有：哈希函数：Hash(k1) == Hash(K2) ,即：不同的关键字通过相同的哈希函数计算出了相同的哈希地址，这种现象成为哈希冲突或哈希碰撞。
把具有不同关键码，但却具有相同的哈希地址的数据元素称为 “同义词”。

?
冲突 - 避免

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量。这就导致一个问题，冲突的发生时必然的，我们能做的就是尽量的降低哈希冲突的概率。

文章图片

?
冲突 - 避免 - 哈希函数的设计

引起哈希冲突的一个原因可能是：哈希函数的设计不够合理。
哈希函数的设计原则：
1、哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值必须在 0到 m -1之间。【比如：数组容量为10，下标为 0~9】
?
2、哈希函数计算出来的地址能均匀分布在整个空间。
简单来说：就是优化，或者重新设计一个更好的哈希函数。来降低哈希冲突发生率。
此时，认清楚一个事实：哈希冲突是无法避免的！我们只是说让哈希冲突发生的概率，保持在一个“健康”的度【负载因子】。
?
3、哈希函数的设计不能太复杂，尽量简单。

?
常见的哈希函数
1、直接定制法 - （常用）

取关键字的某个线性函数为哈希（散列）地址：类似数学中直线方程：Hash(Key) = A * (Key) + B。
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

?
相关面试题 - LeetCode - 387. 字符串中的第一个唯一字符

文章图片

?
题目分析与解题思路

文章图片

?
代码如下

class Solution { public int firstUniqChar(String s) { int[] array = new int[26]; for(int i = 0; i < s.length(); i++){ array[s.charAt(i) - 'a']++; } for(int i = 0; i < s.length(); i++){ if(array[s.charAt(i) - 'a'] == 1){ return i; } } return -1; } }

文章图片

?
拓展: HashMap 思维

不了解的HashMap 或者 HashSet，可以参考这篇文章Map && Set，带你进入Java最常用到的两个接口。
利用 HashMap【Key = 字符，Value - 出现次数】去统计字符串每个字符的出现次数，之后也是去遍历字符串，通过 Key 去获取 Value 值，如果等于1,返回遍历的字符串的变量/索引。

?
代码如下

class Solution { public int firstUniqChar(String s) { Map map =new HashMap<>(); for(int i = 0; i < s.length(); i++){ char ch = s.charAt(i); map.put(ch,map.getOrDefault(ch,0)+1); // if(map.containsKey(ch)){ //int val = map.get(ch); //map.put(ch,val+1); // }else{ //map.put(ch,1); // } } for(int i = 0; i < s.length(); i++){ char ch = s.charAt(i); if(map.get(ch) == 1){ return i; } } return -1; } }

文章图片

?
2、除留余数法 - （常用）

设哈希（散列）表中允许的地址数为m，取一个不大于m，但最接近或等于 m 的质数****p作为除数。【质数又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数】
按照哈希函数 Hash（key） = key % p（p <= m）,将关键码转换成哈希地址。
缺点：假设 m = 10，我们取一个7，这也就意味着 7后面的三个空间将会被浪费。
所以，还是要少用。

?
3、平方取中法 - （了解）

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671（或710）作为哈希地址，平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。

?
4、折叠法 - （了解）

折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希（散列）表的长度，取后几位作为哈希（散列）地址。
折叠法适合事先不需要知道关键字的分布，适合关键字比较多的情况。

?
5、随机数法 - （了解）

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即：H(key) = random(key),其中random 为随机值函数。

?
数学分析法 - （了解）

设有n个d位数，每一位可能有 r 种不同的符号，这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现，可根据哈希（散列）表的大小，选择其中各种符号分布均匀的若干位作为哈希（散列）地址。

文章图片

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
?
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况.
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

?
冲突-避免-负载因子调节（重点掌握）

哈希（散列）表的载荷/负载因子定义为：α = 填入表中的元素个数 / 散列表的长度
α 是哈希（散列）表装满程度的标志因子。由于表长是定值，α 与 “填入表中的元素个数” 成正比，所以，α 越大，表明的填入表中的元素越多，产生冲突的可能性就越大；反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，哈希（散列）表的平均查找长度是载荷因子α的函数，只是处理冲突的方法是不同的【不同的函数】。
?
对于开放定址法，负载因子是特别重要因素，应严格限制在 0.7 ~ 0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如java的系统库限制了荷载因子为0.75，超过此值将重新 resize 哈希（散列）表。【resize - 扩容，重新哈希】

?
负载因子和冲突率的关系粗略演示

文章图片

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。
已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小

?
冲突 - 解决

解决哈希冲突两种常见的方法是：闭散列和开散列。

?
冲突 - 解决 - 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去。
那么，问题来了：如何寻找下一个空位置呢？

?
1、线性探测

比如下述场景中，需要插入元素44，先通过哈希函数计算哈希地址，下标为 4，因此 44 理论上应该插在4下标位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

文章图片

?
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
?

?
插入操作

通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

文章图片

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他
元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

文章图片

?
为了能够均匀的分布冲突元素，二次探测由此而生。

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：H(i) = (H0 + i^2 ) % m, 或者：H(i)= (H0 - i^2) % m。其中：i = 1,2,3…，是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，
m是表的大小。对于插入44，产生冲突，使用解决后的情况为

文章图片

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

【散列表|HashTable - 哈希表 - 细节狂魔】?
冲突-解决-开散列/哈希桶（重点掌握)

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

文章图片

此时，哈希表底层数组的每个下标的空间就像一个个有着自己“独特编号”的的“桶”，去装符合自己的“条件”的数据。
也就是说：此时的数组，是一个节点数组。
【提示：在jdk1.8版本，用的是尾插。这个知道就行】
?
有的朋友可能会有疑问：如果输入的数据越多，链表的越长。在寻找元素的时候，时间复杂度不还是有可能达到O(N) 吗？
答案：不会达到O(N)的，因为有负载因子的存在（存储的元素达到一定的数目，就会进行扩容），链表的长度不会很长，控制在常数范围内。
另外，当链表越来越长，下面不会是一个链表了！
从jdk1.8开始：当链表的长度超过8，且数组长度超过64，这个链表才会变成红黑树。
而红黑树又是一种对于查找来说：特别高效的一种树。再加上还有负载因子的介入[链表没机会达到O(n),就会去扩容了]，所以请放心，它的时间复杂度是不会达到O(N)的。
?
开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。
将数据根据函数，分别存入不同的“桶”里，要什么数据，再去根据函数，找到对应的“桶”进行相应的操作。
这也是我们 HashMap 底层的处理方式。

?
哈希表的性能分析

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是O(1) 。

?
冲突严重时的解决办法

刚才我们提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：
1、每个桶的背后是另一个哈希表
2、每个桶的背后是一棵搜索树【红黑树】

?
模拟实现简易的HashMap - 简单数据类型。

只实现重要的功能：put 和 get

准备工作 - 程序框架

文章图片

文章图片

?
put 功能第一步：找 key 的存储位置

文章图片

?
第二步：插入节点。

在 jdk1.8版本之后，采用的是尾插法，但是具体是尾插还是头插不重要，不影响操作。
这里我采用的是头插法。
但是在插入节点之前，我们需要判断一下。
1、插入节点的位置，可能已经有其他元素了。

文章图片

2、如果我们插入的数据，在它的存储位置中已经存在，根据HashMap的特性：将我们插入的数据中 value值赋予已经存在链表中节点的value（更新）。

文章图片

?
代码如下

文章图片

?
resize函数 - 扩容函数

注意！这并不是普通的扩容！
如果你想这将数组容量由10变成20，那你就想的太简单了！
来看下面的图

文章图片

所以在扩容之后，需要重新哈希每个下标的链表节点。确保扩容之后，能通过哈希函数获得下标中的链表找到我们想要的值。
另外重新哈希的时候，还需要注意一点，来看下面

文章图片

?
代码如下

private void resize(){ Node[] newArray = new Node[this.array.length*2]; for (int i = 0; i < this.array.length; i++) { Node cur = this.array[i]; while(cur!=null){ // 获取在新数组中的存储位置。 int index = cur.key % newArray.length; // 头插到新数组中 Node curNext = cur.next; // 记录下一个节点的位置 cur.next = newArray[index]; newArray[index] =cur; cur = curNext; // 接着下一个节点。 } // while循环执行完之后，for循环i++，继续下一个下标的哈希 } // 最后更新引用 array 的指向 this.array = newArray; }

?
get功能

怎么放的，怎么取。通过自定义的哈希函数： int index = key % 数组长度

文章图片

?
总程序

/* * 实现一个统计整数数据的出现次数 * key - 整形数据 * value - key 元素的出现次数 * */public class HashTable { // 节点类 - 静态内部类 static class Node{ public int key; public int val; public Node next; public Node(int key,int val){ this.val = val; this.key = key; } }public Node[] array; // 底层数组 public int usedSize; // 元素个数 publicstatic final double DEFAULT_LOAD_FACTOR = 0.75; // 负载因子 public HashTable(){ // 数组初始容量为 10 this.array = new Node[10]; }/* * 根据 key 获取 val 值 * */ public int get(int key){ // 1、找到 key 所在的位置。 int index = key % this.array.length; // 2、遍历数组，寻找 key Node cur = this.array[index]; while(cur!=null){ if(cur.key == key){ return cur.val; } cur = cur.next; } // 返回-1,表示没有找到符号条件的节点 return -1; }/* * 将 key ，value 值存入 * 此时的代码是有缺陷的，key 不能为负数 * */ public void put(int key,int val){ // 1、找到 key 所在的位置。 int index = key % this.array.length; // 2、遍历这个下标的链表 Node cur = array[index]; // 获取头节点地址 while(cur!=null){ //判断是否有相同的key，有，则更新value值 if(cur.key == key){ cur.val = val; return; } cur = cur.next; } // 没有相同的key，就直接头插节点 Node node = new Node(key,val); node.next = array[index]; array[index] = node; this.usedSize++; // 检查当前的负载因子 if(loadFactor() > DEFAULT_LOAD_FACTOR){ resize(); // 扩容 }} private double loadFactor(){ return 1.0 * this.usedSize / this.array.length ; //乘以1.0为了结果是小数。 } private void resize(){ Node[] newArray = new Node[this.array.length*2]; for (int i = 0; i < this.array.length; i++) { Node cur = this.array[i]; while(cur!=null){ // 获取在新数组中的存储位置。 int index = cur.key % newArray.length; // 头插到新数组中 Node curNext = cur.next; // 记录下一个节点的位置 cur.next = newArray[index]; newArray[index] =cur; cur = curNext; // 接着下一个节点。 } // while循环执行完之后，for循环i++，继续下一个下标的哈希 } // 最后更新 array 的引用大的指向 this.array = newArray; }public static void main(String[] args) { HashTable hashTable = new HashTable(); hashTable.put(1,1); hashTable.put(3,3); hashTable.put(12,12); hashTable.put(2,2); // 冲突元素 hashTable.put(11,11); // 冲突元素 // 5个元素，此时的负载因子为0.5 System.out.println(hashTable.get(11)); } }

?
效果图

文章图片

?
模拟实现简易的HashMap - 引用数据类型。

在实现这个代码之前，我需要先给你们介绍一个函数：hashCode：
hashCode：将一个引用类型的数据转换一个整数、

文章图片

?
有了这个，我们再去写》》程序框架

这我们用的泛型来写。为了突出引用类型的数据

文章图片

?
put 方法

和上面的 put方法一模一样，但是需要注意的是哈希函数 int index = key % 数组长度。这个 key 不能直接与整数数据运算。
需要通过hashCode方法先转换一下，再去进行运算获取存储位置。

public void put(K key,V val){ //int index = key % array.length; // 错误写法，引用类型无法与整形数据进行运算 // 需要借助hashCode方法，将引用类型数据转换成整形数据 int hash = key.hashCode(); int index = hash % array.length; // 2、遍历这个下标的链表 Node cur = array[index]; // 获取头节点地址 while(cur!=null){ //注意的 key 是引用类型的数据，所以需要用 equals 比较 // 而这个在我们重写 hashCode方法的时候，就已经捆绑重写了 if(cur.key.equals(key)){ cur.val = val; return; } //简单来说：hashCode 用来确定 key 存储位置， equals 用来比较 key 是否相等。 cur = cur.next; } // 没有相同的key，就直接头插节点 Node node = new Node<>(key,val); node.next = array[index]; array[index] = node; this.usedSize++; //扩容就不写，跟前面的代码一模一样，稍微改一下就行了。 }

代码注释说到：hashCode 用来确定 key 存储位置， equals 用来比较 key 是否相等。
那么，hashCode 一样，equals 能一样吗？
答案：可能不一样，hashCode一样，只能证明这两个元素存储的下标位置是一样的。具体这两个元素是否相等，还需要equals 一个个去比较。
?
equals 一样，hashCode能一样吗？
答案：一定是的！ equals都一样了，说明是同一个数据，同一个数据肯定是在同一个位置。
所以 hashCode 肯定是一样的！

?
get 方法

文章图片

?
总程序

import java.util.Objects; class Person{ public String ID; public Person(String ID){ this.ID = ID; }@Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; return Objects.equals(ID, person.ID); }@Override public int hashCode() { return Objects.hash(ID); }@Override public String toString() { return "Person{" + "ID='" + ID + '\'' + '}'; } }public class HashBucket{ static class Node{ public K key; public V val; public Node next; public Node(K key,V val){ this.val = val; this.key = key; } }public Node[] array = (Node[]) new Node[10]; public int usedSize; public void put(K key,V val){ //int index = key % array.length; // 错误写法，引用类型无法与整形数据进行运算 // 需要借助hashCode方法，将引用类型数据转换成整形数据 int hash = key.hashCode(); int index = hash % array.length; // 2、遍历这个下标的链表 Node cur = array[index]; // 获取头节点地址 while(cur!=null){ //注意的 key 是引用类型的数据，所以需要用 equals 比较 // 而这个在我们重写 hashCode方法的时候，就已经捆绑重写了 if(cur.key.equals(key)){ cur.val = val; return; } //简单来说：hashCode 用来确定 key 存储位置， equals 用来比较 key 是否相等。 cur = cur.next; } // 没有相同的key，就直接头插节点 Node node = new Node<>(key,val); node.next = array[index]; array[index] = node; this.usedSize++; //扩容就不写，跟前面的代码一模一样}public V get(K key){ // 1、找到 key 所在的位置。 int hash = key.hashCode(); int index = hash % this.array.length; // 2、遍历数组，寻找 key Node cur = this.array[index]; while(cur!=null){ if(cur.key.equals(key)){ return cur.val; } cur = cur.next; } return null; }public static void main(String[] args) { Person person1 = new Person("123"); Person person2 = new Person("123"); HashBucket hashBucket = new HashBucket<>(); // 放入 person1, 那 person2 去取 // 因为我们重写了 hashCode 方法 // 所以在程序看来person1 和 person2 是一样的。 // 所以 person2 可以拿到person1 的 value值 aaa 的。 hashBucket.put(person1,"aaa"); System.out.println(hashBucket.get(person2)); }}

文章图片

?
hash表和 java 类集的关系

1、HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
2、 java 中使用的是哈希桶方式解决冲突的
3、java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
4、 java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 或者 HashSet 的key 值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。
?
想要进一步HashMap 和 HashSet的功能，可以看这一篇文章Map && Set，带你进入Java最常用到的两个接口