文章目录
- 一、概念
- 二、冲突
-
- 1.冲突的概念
- 2.冲突的避免
- 三、冲突避免的方法
-
- 1.哈希表的设计
- 2.负载因子的调节
- 四、冲突解决
-
- 1.闭散列
-
- 1.1.线性探测
- 2.1.二次探测
- 2.开散列
-
- 2.1.冲突严重时的解决方法
- 2.2.代码实现
- 2.3.完整代码
- 2.4.性能分析
- 最后
一、概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2N )，搜索的效率取决于搜索过程中元素的比较次数。
那么有没有一种方法：可以不经过任何比较，直接通过关键字key，得到要查找的记录的内存位置？
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
举个例子：
你爸到学校找你，门卫处可能需要慢慢地查找学生表，看看你在哪里，而你的同学撞到你爸，不用找就直接把你爸带到了你所在的位置。
在这里你门卫通过的是表格查找，依赖的是关键字，而你的同学则直接带你爸去到你的位置，没有遍历，没有比较。也就是说，你的位置跟某个东西存在以下关系：
位置 = f（关键字）
这样我们就可以通过关键字而又不需要比较就可获得需要记录的存储位置了。我们管这东西叫做，散列技术。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key).
我们把上面的这种对应关系f称为散列函数，又称哈希函数。
采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表。关键字对应的记录存储位置我们称为散列地址。
我们举一种最常用的例子：
【说明】哈希函数一般由我们自己设计的
我们这里哈希函数设置为：
hash(key) = key%capacity
capacity为存储元素底层总的空间。
二、冲突
大家有没想过，假如我们在上面的表里插入一个16，会怎么样？
这也是我们接下来需要讨论的问题——冲突
1.冲突的概念
对于两个数据元素的关键字ki 和kj，有ki != kj，但有：Hash(ki ) == Hash( kj)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
如下图：6与16两个元素就冲突了。
因此，不同的关键字，通过相同的哈希函数，有可能找到相同的位置，此时的情况就是哈希冲突或者说哈希碰撞。
2.冲突的避免
首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。
三、冲突避免的方法
1.哈希表的设计
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间.
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见的哈希函数设计方法：
- 直接定址法
取关键字的某个线性函数为散列址：Hash（Key）=A*Key + B （有没感觉像：y=kx+b 哈哈哈，也就是取数据元素关键字k本身或它的线性函数作为它的哈希地址。
按照这种方式将数据保存起来。
这种方法优缺点都很明显：
1.优点：简单、均匀 缺点：需要事先知道关键字的分布情况
2.使用场景：适合查找比较小且连续的情况.
这里有一道相关的力扣题目：387. 字符串中的第一个唯一字符
其中的一种解法就运用了这种思想。
class Solution {
public int firstUniqChar(String s) {
if(s == null || s.length() == 0) return -1;
int[] arr = new int[26];
for(int i = 0;i< s.length(); i++){
char ch = s.charAt(i);
arr[ch - 'a']++;
}
for(int i =0;i < s.length();i++){
char ch = s.charAt(i);
if(arr[ch - 'a'] == 1){
return i ;
}
}
return -1;
}
}
- 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key%p(p<=m),将关键码转换成哈希地址。
这个就是我们一开始讲的那个例子：
- 平方取中法
取关键字的平方数值的中间几位作为哈希地址。
假设关键字为1111，它的平方就是1234321，抽取中间的3位343作为哈希地址；
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
- 折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是9876543210，散列表表长为三位，我们将它分为四组,987|654|321[0，然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列地址为962。有时可能这还不能够保证分布均匀,不妨从一端向另一端来回折叠后对齐相加。比如我们将987和321反转，再与654和0相加，变成789+654+123+0=1566,此时散列地址为566。
折叠法事先不需要知道关键字的分布,适合关键字位数较多的情况。
还有一些不怎么常用的就不一一介绍了。
在现实中，我们应该视不同情况采取不同的散列函数，一般考虑以下因素：
- 计算散列地址所需的时间。
- 关键字的长度。
- 散列表的大小。
- 关键字的分布情况。
- 记录查找的频率。
综合这些因素，才能决策选择哪种散列函数更合适。
2.负载因子的调节
散列表的载荷因子定义为:α =填入表中的元素个数/散列表的长度。
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，表明填入表中的元素越多，产生冲突的可能性就越大，反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cachemissing)按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。
负载因子与冲突率的关系粗略图：
所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。
不过如果已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。
四、冲突解决
我们设计得再好的散列函数也不可能完全避免冲突，这就像我们再健康也只能尽量预防疾病，但却无法保证永远不得病一样,既然冲突不能避免，就要考虑如何处理它。
解决哈希冲突两种常见的方法是：闭散列和开散列
1.闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以
把key存放到冲突位置中的“下一个” 空位置中去。
1.1.线性探测
所以这里最大的问题是：我们如何寻找到下一个空位置？
比如我们一开始的那个问题：假如我们在下面表里插入一个16，会怎么样？
答案就是：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。 这也被称为线性探测法。
过程如下：
- 通过哈希函数获取待插入元素在哈希表中的位置
- 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
【注意】
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素6，如果直接删除掉，16查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
从这个例子我们也看到，我们在解决冲突的时候，还会碰到如7和16这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。
很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低
我们观察刚刚这个图的时候，会发现它后面几乎都填满了元素，而前面还有很多空位，那么我们在继续插入元素的时候，虽然可以通过不断求余来进行填充，但是这样的效率很差。所以这里有一个改进方法，我们称之为二次探测。
2.1.二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，
因此，二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i )% m, 其中：12, -12, 22, -22, 32,……，，H0 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
对于刚刚的例子中如果要插入16，产生冲突，使用解决后的情况为：
2.开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
比如说刚刚的例子：
16这个元素就被尾插到下标为6的元素后面了。 假如再插入26，则再添加在后面。
链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。
2.1.冲突严重时的解决方法
哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：
- 每个桶的背后是另一个哈希表
- 每个桶的背后是一棵搜索树
2.2.代码实现
这里我们代码实现一下开散列的方法：
- 第一步，需要先定义一个散列表结构，以及一些相关的常数。
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;//定义一个Node类型的数组
public int usedSize;//定义一个范围值
public static final double DOUBLE_LOAD_FATOR = 0.75;//定义一个负载因子，超过这个就扩容
public HashBuck(){
this.array = new Node[10];
}
- 定义一个put方法
public void put(int key,int val){
//1.通过哈希函数，找到key所在的位置
int index = key % this.array.length;
//2.遍历这个index下标的链表，检查有没有相同的key，若有，则更新里面的val值
Node cur = array[index];
while(cur !=null){
if(cur.key == key){
cur.val = val;//更新val
return;
}
cur = cur.next;
}
//3.如果没有这个key元素，则用头插法插入，（用尾插法也行）
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
//4.插入元素成功后，检查当前散列表的负载因子,如果大于0.75，则扩容
if(loadFactor() > DOUBLE_LOAD_FATOR){
resize();
}
}
private void resize(){
Node[] newArray = new Node[array.length*2];//扩容
//重新计算元素的哈希值
for (int i = 0;i<array.length;i++){
Node cur = array[i];
while (cur != null){
int index = cur.key % newArray.length;//获取新的下标
//把cur这个结点重新头插到新的数组对应的下标中
Node curNext = cur.next;
cur.next = newArray[index];
newArray[index] = cur;
cur = curNext;
}
}
array = newArray;//把array指向newArray,原来的数组就被jvm给回收掉了
}
private double loadFactor(){
return 1.0*usedSize / array.length;
}
- 定义一个get函数
public int get(int key){
//1.找到key所在的位置
int index = key % this.array.length;
//2.遍历这个下标的列表，看是不是有相同的key，有则更新value值，
Node cur = array[index];
while (cur != null){
if(cur.key == key){
return cur.val;
}
cur = cur.next;
}
return -1;//没有找到结点
}
2.3.完整代码
public class HashBuck {
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;//定义一个Node类型的数组
public int usedSize;//定义一个范围值
public static final double DOUBLE_LOAD_FATOR = 0.75;//定义一个负载因子，超过这个就扩容
public HashBuck(){
this.array = new Node[10];
}
public void put(int key,int val){
//1.通过哈希函数，找到key所在的位置
int index = key % this.array.length;
//2.遍历这个index下标的链表，检查有没有相同的key，若有，则更新里面的val值
Node cur = array[index];
while(cur !=null){
if(cur.key == key){
cur.val = val;//更新val
return;
}
cur = cur.next;
}
//3.如果没有这个key元素，则用头插法插入，（用尾插法也行）
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
//4.插入元素成功后，检查当前散列表的负载因子,如果大于0.75，则扩容
if(loadFactor() > DOUBLE_LOAD_FATOR){
resize();
}
}
private void resize(){
Node[] newArray = new Node[array.length*2];//扩容
//重新计算元素的哈希值
for (int i = 0;i<array.length;i++){
Node cur = array[i];
while (cur != null){
int index = cur.key % newArray.length;//获取新的下标
//把cur这个结点重新头插到新的数组对应的下标中
Node curNext = cur.next;
cur.next = newArray[index];
newArray[index] = cur;
cur = curNext;
}
}
array = newArray;//把array指向newArray,原来的数组就被jvm给回收掉了
}
private double loadFactor(){
return 1.0*usedSize / array.length;
}
public int get(int key){
//1.找到key所在的位置
int index = key % this.array.length;
//2.遍历这个下标的列表，看是不是有相同的key，有则更新value值，
Node cur = array[index];
while (cur != null){
if(cur.key == key){
return cur.val;
}
cur = cur.next;
}
return -1;
}
//测试代码
public static void main(String[] args) {
HashBuck hashBuck = new HashBuck();
hashBuck.put(12,12);
hashBuck.put(3,3);
hashBuck.put(6,6);
hashBuck.put(2,2);
hashBuck.put(8,8);
System.out.println(hashBuck.get(8));
}
2.4.性能分析
虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，
也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是
O(1) 。
散列查找的平均查找长度取决于哪些因素呢？
- 散列函数是否均匀
- 处理冲突的方法
- 散列表的负载因子
最后
以上就是本次文章的所有内容，这次文章断断续续都搞了3天了，有时候不禁会想，其实搞这些东西究竟有没有什么意义？一方面，是为了基础知识的牢固，可是另一方面，自己代码能力却迟迟不见增长，刷的题还是太少，能力不见增长，时间也不允许自己犯错了。
不知道路在何方…
相关文章
