【数据结构】关于哈希表内部原理，你到底了解多少？？？（超详解）

前言：

🌟🌟本期讲解关于哈希表的内部实现原理，希望能帮到屏幕前的你。

🌈上期博客在这里：http://t.csdnimg.cn/7D225

🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客

📚️1.哈希表的概念

📚️2.哈希-冲突

2.1冲突-概念

2.2冲突-避免

1.冲突-避免-哈希函数设计

2.冲突-避免-冲突因子

2.3冲突-解决

1.冲突-解决-闭散列

2.冲突-解决-开散列

2.4性能分析

2.5与Java类集的关系

📚️3.总结

📚️1.哈希表的概念

顺序结构以及平衡树中在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)；

平衡树中为树的高度，即O(logN )，搜索的效率取决于搜索过程中元素的比较次数。例如上期的treeMap.

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

• 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

图解：

注意：这里和计数排序差不多，但是如果我们加入11，会发现11的位置将直接把1给覆盖掉，那么此时就叫作哈希-冲突。

📚️2.哈希-冲突

2.1冲突-概念

对于两个数据元素的关键字ki 和kj (i != j)，有ki !=kj ，但有：Hash(ki ) == Hash(kj )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞

2.2冲突-避免

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

1.冲突-避免-哈希函数设计

哈希函数设计原理：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

• 哈希函数计算出来的地址能均匀分布在整个空间中

• 哈希函数应该比较简单

小编这里介绍两个比较常用的两个方法：

1. 直接定制法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况。

例如：字符串中第一个只出现一次字符

代码实例如下：

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

思路：就是创建一个26个空间大小的数组，在遍历字符串时，将字符对应的位置加一，最后再次遍历谁为1，就返回第一个不重复的字符。

注意：这种方法只适合要求范围小的数值内进行操作，如果范围过大，则会造成数组空间的浪费。

2. 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

2.冲突-避免-冲突因子

负载因子与冲突率图片演示：

已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。（我们不可能在源头上限制我们的需求）

2.3冲突-解决

1.冲突-解决-闭散列

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

线性探测：

这里就是，当我们先插入了一个1后，然后想插入11，此时发现取余地址冲突了，此时我们就要往后寻空位置，发现后进行插入。

图片演示：

注意：

不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。

产生冲突的数据堆积在一块

二次探测

找下一个空位置的方法为：Hi = (H0 +i^2 )% m, 或者：Hi= (H0 -i^2 )% m。其中：i = 1,2,3…，是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的置，m是表的大小。

图片演示：

当然这是一个极端的例子~~~

注意：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

2.冲突-解决-开散列

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

图解如下：

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

开散列的代码实现模拟：

public class HashBucket {//结点链表的初始化static class Node{public int key;public int val;public Node next;public Node(int key,int val){this.key=key;this.val=val;}}//数组的初始化public Node[] array=new Node[10];public int usedSize;//插入元素public void put(int key,int value){/* int index=key% array.length;//遍历链表//头插法Node cur=array[index];while (cur!=null){if(cur.key==key){cur.val=value;return;}cur=cur.next;}Node node=new Node(key,value);node.next=array[index];array[index]=node;usedSize++;*///尾插Node node=new Node(key,value);int index=key% array.length;if(array[index]==null){array[index]=node;return;}Node cur=array[index];Node prev=null;while (cur!=null){if(cur.key==key){cur.val=value;return;}prev=cur;cur=cur.next;}prev.next=node;usedSize++;//负载因子是否大于0.75if(loadFactor()>0.75){resize();}}public int loadFactor(){return usedSize/ array.length;}//进行扩容public void resize(){Node[] tmpArray=new Node[array.length*2];for (int i = 0; i < array.length; i++) {Node cur=array[i];while (cur!=null){Node newCur=cur.next;int newIndex=cur.key% tmpArray.length;//进行头插法cur.next=tmpArray[newIndex];tmpArray[newIndex]=cur;cur=newCur;}}array=tmpArray;}//进行取出public int get(int key){//判断k在哪里int index=key%array.length;Node cur=array[index];while (cur!=null){if(cur.key==key){return cur.val;}cur=cur.next;}return -1;}

这里小编模拟了哈希表开散列的放入数据的两种插入方式，即链表的头插法以及链表的尾插法。

注意扩容：

1.进行原来数值的项管部位置的插入，因为扩容后的数组容量大小进行变化，必须进行重新取余。

2.在进行在新的扩容数组后，使用的cur要进行保留，否则进行新的数组插入后，cur无法回到原来数组进行遍历剩余的数值遍历。

2.4性能分析

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

1.每个桶中的链表的长度是一个常数，并且可以进行调整。

2.负载因子的存在，使得在遍历时可以进数值过多的扩容。

2.5与Java类集的关系

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set

2. java 中使用的是哈希桶方式解决冲突的

3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）

4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法。