java数据结构_Map和Set（一文理解哈希表）_9.3

目录

5. 哈希表

5.1 概念

5.2 冲突-概念

5.3 冲突-避免

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

5.5 冲突-避免-负载因子调节

5.6 冲突-解决

5.7 冲突-解决-闭散列

5.8 冲突-解决-开散列 / 哈希桶

5.9 冲突严重时的解决办法

---

5. 哈希表

5.1 概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素的时候，关键码之间的多次比较是不可缺少的。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

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

向该结构中：

        插入元素：根据插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

        搜索元素：对元素的关键码进行同样的计算，把求得的函数值当作元素的存储位置，在结构

中按此位置取元素进行比较，若关键码相同，则搜索成功

该方法称为哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（HashTable） / 散列表。

例如：数据集合{1，7，6，4，5，9}，哈希函数可以设置为：hash(key) = key % capacity capacitty为存储元素底层空间总的大小

用该方法进行搜索不必进行多次关键码的比较，效率会大大加快，但是，如果按照上述哈希方法，向集合中插入元素44，会出现什么问题？

5.2 冲突-概念

对于两个数据元素的关键字，数据元素的关键字并不相同，但是通过哈希函数计算出来的结果是相同的，即：不同关键字，通过哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或者哈希碰撞。

把具有不同关键码 但是 具有相同哈希地址的数据元素称为“同义词”。

5.3 冲突-避免

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

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

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

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

        2. 哈希函数计算出来的地址能均匀分布在整个空间中（降低冲突）

        3. 哈希函数应该比较简单

常见的哈希函数

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

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

        其他方法不作介绍

5.5 冲突-避免-负载因子调节

散列表的载荷因子定义为：α = 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。由于散列表的长度是定值，α与“填入表中的元素的个数”成正比，所以，α越大，表明填入表中元素越多，产生冲突的可能性就越大。反之，α越小，表明填入表中的元素越少，产生冲突的可能性就越小，实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。

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

当冲突率达到一个无法忍受的高度时候，需要通过降低负载因子来变相的降低冲突率。

已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

5.6 冲突-解决

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

5.7 冲突-解决-闭散列

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

        1.线性探测

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

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

但是采取线性探测的缺陷是，数据会堆积到一起，更会增加了发生哈希冲突的可能性

        2.二次探测

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

研究表明：当表的长度为质数且表装载因子α不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

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

5.8 冲突-解决-开散列 / 哈希桶

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

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

代码实现：

首先还是需要定义一个内部类Node，然后创建一个类型为Node[]的数组，定义usedSize

接下来是put方法，参数为要插入的数据的key，val，然后根据val值计算出对应的下标，index = key % array.length，定义cur，Node cur = array[index]，然后用cur遍历该索引下的链表，检查是否存在当前的key（key是不能重复的），如果没有key，则使用头插法/尾插法插入（此处使用头插法）

添加完成之后，可以判断一下负载因子，如果负载因子大于0.75，则对散列表进行扩容

loadFactor方法：

在resize方法中，要将散列表的容量进行扩容，在扩容后，就要对整个散列再进行 ！！！重新哈希！！！例如之前 4 和 14 都在散列表索引为4的位置，扩容后，14可能就不再索引为4的位置了，要进行重新哈希！！！

resize方法如下：

接下来是get方法，和put一样，得到对应的index，然后检查key值是否相同，如果找到就返回对应的val，如果没有找到就返回-1，下面是get方法的代码：

下面是全部代码：

/*** @author : zzr* @description :* @date :*/
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;public int usedSize;public HashBuck() {array = new Node[10];}public void put(int key, int val) {int index = key % array.length;Node cur = array[index];//遍历该索引下的链表，看一下是否存在的当前key（不重复）while (cur != null) {if(key == cur.key) {cur.val = val;return;}cur = cur.next;}//没有这个key//头插法插入单链表中Node node = new Node(key, val);node.next = array[index];array[index] = node;usedSize++;//如果负载因子大于等于0.75 就进行扩容 --> 重新哈希if(loadFactor() >= 0.75) {resize();}}private void resize() {//在扩容的时候 要对整个哈希表都重新哈希//例如之前 4 和 14都在索引为4的位置时候，扩容后，14 可能就不在索引为4的位置了Node[] tmpArr = new Node[array.length * 2];//遍历原来的数组 将所有的元素 ！！！重新哈希！！！ 到新的数组当中for (int i = 0; i < array.length; i++) {Node cur = array[i];while(cur != null) {Node curNext = cur.next;//记录cur的next位置int newIndex = cur.key % tmpArr.length;//头插法：cur.next = tmpArr[newIndex];tmpArr[newIndex] = cur;//cur继续向后走cur = curNext;}}}private double loadFactor() {return usedSize * 1.0 / array.length;}public int get(int key) {int index = key % array.length;Node cur = array[index];while (cur != null) {if(key == cur.key) {return cur.val;}cur = cur.next;}return -1;}
}

测试符合预期：

这样实现的方法，在散列表中对数据进行增删改查的时间复杂度就都是O(1)了，这里可能会有疑问，因为我们的实现相当于是在数组中的每一个位置添加了一个单链表，我们在操作数据的时候，还是需要在单链表中对数据进行查找，才能进行操作，其时间复杂度不可能仅仅为O(1)。这里需要解释的是，我们在put方法中是由resize方法和loadFactor方法的，因为由负载因子的出现，是不会使得单链表的长度十分长的，单链表的长度一定会保持在一个常数级的大小，所以可以将该方法的时间复杂度记为O(1)。虽然时间复杂度降低为O(1)，但是空间复杂度会上升，哈希表就是一个典型的浪费空间，节省时间的例子。

但上面的方法中，我们默认key和val都是int类型的数据，才能在计算index中直接index = key % array.length，但是在实际使用中，key，val类型通常是引用类型，则无法计算index了，那该怎么办呢？

如下：如果有一个类是Person类呢，其成员变量为String类型的id

这时候就要提出hashCode方法了，hasCode方法在JDK中底层是使用C++实现的，无法显示源码，我们只需要直到hashCode可以将引用类型转换成一个int类型并且返回。

在Person类中，我们并没有实现hashCode方法，则hashCode是其默认父类Object中的方法。我们在定义Person中id则代表一个人的身份证号，如果person1和person2的id相同，就说明他们是同一个人，但我们在直接打印person1和person2的hasCode的时候，发现其结果并不相同：

但是当我们在Person类中自动重写hashCode方法之后，再进行打印就发现其值相同了

这样就可以重写刚刚的put和get方法啦！

与之前的方法对比：

put方法：

get方法：

完整代码如下：

import java.util.Objects;/*** @author : zzr* @description :* @date :*/
class Person{String id;public Person(String id) {this.id = id;}@Overridepublic 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);}@Overridepublic int hashCode() {return Objects.hashCode(id);}
}public class HashBuck2<K,V> {static class Node<K, V> {public K key;public V val;public Node next;public Node(K key, V val) {this.key = key;this.val = val;}}public Node<K,V>[] array;public int usedSize;public HashBuck2() {array = (Node<K, V>[]) new Node[10];}public void put(K key, V val) {int hash = key.hashCode();int index = hash % array.length;Node cur = array[index];while(cur != null) {if(key.equals(cur.key)) { //只能用equals方法而不是==cur.val = val;return;}cur = cur.next;}Node node = new Node<>(key, val);node.next = array[index];array[index] = node;usedSize++;}public V get(K key) {int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];while(cur != null) {if(key.equals(cur.key)) {return cur.val;}cur = cur.next;}return null;}}

5.9 冲突严重时的解决办法

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

完！！！