哈希表以及哈希冲突

目录

哈希表

哈希冲突

1. 冲突发生

2. 比较常见的哈希函数

3. 负载因子调节(重点)

散列表的载荷因子概念 

负载因子和冲突率的关系

冲突-解决-闭散列

线性探测

二次探测

冲突-解决-开散列

结尾

---

我们在前面讲解了TerrMap（Set）的底层是一个搜索二叉树，同时Set和Map还存在HashSet（Map）类，但是HahsMap（Set）到底是什么呢？本章来详细介绍以下。

首先来了解以下什么叫做哈希表：

哈希表

在学过的诸多数据结构中如果存在一种删除和插入的结构，不经过任何比较，一次直接从表中搜索到数据，其时间复杂度能够达到O(1)，那么这将非常恐怖，其他数据结构在它面前都不值一提。不错，哈希表这种结构就是能够达到O(1)的恐怖结构，但是如果它真的那么好用，不就说明不用学习其他的结构吗？那么它一定存在它的问题。

当向该结构中：
插入元素：
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素：
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)。

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

 当然如果我们再次插入14呢?结果为4啊，又该插入在哪里呢？

这个就是我们本章的重点，哈希冲突，4%10 = 4；14%10 = 4，此时发生了哈希冲突。

哈希冲突

1. 冲突发生

首先我们得知道，哈希冲突是必然的，无论怎么插入，插入多少都无法杜绝，哪怕就插入两个元素4，14都发生了哈希冲突，我们能做的就是尽量避免哈希冲突的发生。

这也就是我们哈希表这种结构存在的问题。

哈希冲突的概念：两个不同关键字key通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

引起哈希冲突的一个原因可能是：哈希函数设计不够合理；那我们来看看哈希函数设计原则：

1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
2. 哈希函数计算出来的地址能均匀分布在整个空间中
3. 哈希函数应该比较简单

2. 比较常见的哈希函数

常见哈希函数

直接定制法--(常用)

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

除留余数法--(常用)

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

平方取中法--(了解)

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

等等.......

3. 负载因子调节(重点)

散列表的载荷因子概念 

负载因子和冲突率的关系

例如：

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

冲突-解决-闭散列

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

线性探测

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

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入
·通过哈希函数获取待插入元素在哈希表中的位置
·如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
 

这样插入没问题，但是我们利用哈希表不只是插入元素，我们还有其他操作；例如删除：

 我们第一次删除了4，根据我们之前查找的原则，我第二次怎么去找到44呢？我们是根据4存在才能找到44，这时就发生问题了，第二次删除时哈希表就认为不存在44这个元素。

那么我们有什么办法解决呢？

这时就需要我们标记一下。

 这就涉及到了二次探测。

二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法：

 

其中： i = 1，2，3.....，是通过散列函数Hash（x）对元素的关键码key进行计算得到的位置m是表的大小。

那么我们就按照该方法插入进数组中：

无论如何，二次探测的空间利用率是不高的，假设负载因子时0.75，那么插入第八个数据时就需要扩容了。

哈希还有一种解决方法：开散列。

冲突-解决-开散列

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

例如：

开散列中每个桶中放的都是发生哈希冲突的元素。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

 当数据非常大的时候，那么这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，也就是再对其进行树化，将其转化为红黑树，这个后面再讲。

所以我们的哈希桶也就是由 数组 + 链表 + 红黑树 组成的。

上述所有的一切都是为了引出HashSet(Map)的实现逻辑，原理就是 数组 + 链表 + 红黑树 ，我们接下来用数组 + 链表简单模拟实现哈希桶。

模拟实现代码：

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 int usedSize;//存放的数据的个数public static final double DEFAULT_LOAD_FACTOR = 0.75;//默认的负载因子public HashBuck () {array  = new Node[10];}public static final double LOAD_FACTOR = 0.75;/**** @param key* @param val* @return 代表你插入的元素的val*/public void put(int key,int val) {int index = key % array.length;Node cur = array[index];while (cur != null) {if(cur.key == key) {cur.val = val;return;}cur = cur.next;}//采用头插法进行插入Node node = new Node(key,val);node.next = array[index];array[index] = node;usedSize++;if(calculateLoadFactor() >= LOAD_FACTOR) {//扩容resize();}}private void resize() {Node[] newArray = new Node[2* array.length];for (Node node : array) {Node cur = node;while (cur != null) {Node curNext = cur.next;int index = cur.key % newArray.length;//找到了在新的数组当中的位置cur.next = newArray[index];newArray[index] = cur;cur = curNext;}}array = newArray;}//计算负载因子private double calculateLoadFactor() {return usedSize*1.0 / array.length;}public int get(int key) {int index = key % array.length;Node cur = array[index];while (cur != null) {if(cur.key == key) {return cur.val;}cur = cur.next;}return -1;}
}

由于在扩容过程中地址映射不在原来的位置了，所以要对其进行重新哈希：

 我们上面代码给的都是数字，很好去比较，加入我们有其他引用类型怎么比较？

例如给一个老师类：

class Teacher {public String id;public Teacher() {}public Teacher(String id) {this.id = id;}
}

jdk提供了一个方法名叫hashCode（），我们来简单看看：

 根据这个方法，计算得到一个哈希码值；点进去看看

 hashCode继承Object类；通过这样的一个方法我们就可以把一个引用类型转换为一个整数，进而进行比较。

假设还有一个老师id也是“1234”，我们认为他们是同一个人，但是从系统的角度来看，他们又是两个对象：

 所以我们要对其进行重写hashCode方法，通过他们的id去计算哈希码值。

通过快捷键，我们重写了两个方法，hashCode 和 equals  ，equals是用于两个对象的比较。

 再次运行结果如下：

 简单写一个泛型类型的：

public class HashBuck1<K,V> {static class Node<K,V> {public K key;public V value;public Node<K,V> next;public Node(K key,V value) {this.key = key;this.value = value;}}public Node<K,V>[] array = (Node<K,V>[])new Node[10];public int usedSize;public void put(K key,V value) {int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];while (cur != null) {if(cur.key.equals(key)) {cur.value = value;return;}cur = cur.next;}Node<K,V> node = new Node<>(key, value);node.next = array[index];array[index] = node;usedSize++;}
}

可以对照上面的那段代码。

结尾

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