带你揭开JDK8哈希源码面纱
1. 开场白
顺序结构以及平衡树中, 元素关键码与其存储位置之间没有对应的关系, 想要查找某一个元素必须要经过关键码的多次比较, 顺序查找时间复杂度为O(N), 平衡树的查找是O(logN), 搜索的效率取决于比较的次数.因此为了提高搜索效率, 理想的搜索方式是不经过比较直接取值的方式查找到某个元素. 因此哈希表（散列表）这种数据结构就因此诞生, 可以通过某个函数使得元素关键码合存储位置关联起来形成映射关系, 即可快速取出元素.
先介绍一下最为简便理解的哈希结构
用该方法进行搜索不必多次关键吗比较, 因此搜索的速度会很快, 但是如果插入44该怎么办呢?
2. 冲突
如果是上述一样设置哈希表底成, 那么数组的容量会很大, 但实际中哈希表底层的数组容量是远小于要存储的关键字的数据量, 这就会导致像上述一样存储 44 的话, 不同的关键字通过哈希函数计算出了相同的哈希地址, 这种现象就是哈希冲突或者哈希碰撞
3. 冲突避免–哈希函数设计
引起哈希冲突的一个重要原因是哈希函数设计不合理
常见哈希函数 简介
直接定制法(常用) Hash(Key)= A*Key + B. 优点是简单, 均匀缺点是需要事先知道关键字分布情况, 适合小且连续的情况
除留余数法(常用) 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数: Hash(key) = key% p(p<=m),将关键码转换成哈希地址
平方取中法(了解) 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址; 再比如关键字为4321，对 它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分 布，而位数又不是很大的情况
折叠法(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。【折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
】
随机数法(了解) 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数 函数
数学分析法(了解) 设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某 些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据 散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址
4. 负载因子调节
散列表负载因子定义为a: 填入表中的元素个数/散列表的长度
a越大, 说明数组中元素过多, 发生冲突可能性更大
对于开放定址法, 荷载因子是特别重要因素, 应严格限制在0. 7-0. 8以下. 超过0. 8, 查表时的CPU缓存不命中(cachemissing)按照指数曲线上升. 因此, 一些采用开放定址法的hash库, 如Java的系统库限制了荷载因子为0.75, 超过此值将resize散列表
所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。
5. 冲突解决
5.1 闭散列
闭散列: 也叫开放地址法, 当发生哈希冲突的时候, 如果哈希表没满, 说明哈希表中还有位置, 那么可以把key存储到下一个空位置去, 那么该如何找呢?
5.1.1 线性探测
如上述, 如果插入 44, 则会发生计算出相同的地址下标为 4, 因此 44 理论上应该插入此位置, 但是此位置上已经被使用, 即发生了哈希冲突.
我们从发生冲突的位置开始, 向后遍历哈希表, 直到遇到一个空位置在插入.
上图就是发生哈系统冲突时44 就插入到 6 之后的空位置
缺点是当哈希表删除元素的时候, 会影响后续某些元素的查找. 比如删除元素 4 的时候, 如果直接删掉, 则 44 查找起来可能会受影响. 因此线性探测, 只是用探测采用标记的伪删除法来删除一个元素.
5.1.2 二次探测
二次探测会把数据堆积在一块, 线性探测会挨个往后一个一个找, 因此二次探测为了避免该问题将找下一个空位置的方法定位：Hi=(H0 + i2)%m, 其中 i=1,2,3,4… m/2, m为数组长度.
研究表明:当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
因此:比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
5.2 开散列
开散列又叫链地址法(开链法), 首先对关键码集合用散列函数计算散列地址, 具有相同地址的关键码归为一个集合, 每个子集合称为一个桶, 每个桶通过一个单链表连接起来, 各链表的头节点存储在哈希表中.
正如上图所示那样, 操作哈希这种结构就是数组挂着链表, 由于这里只是简单的介绍就简介了数组如何挂载链表。JDK8源码中为了进一步提高搜索效率还有把链表转换为搜索树(红黑树).
如图所示就是一个挂载着红黑树和链表的哈希桶
6. 手动实现一个简单的哈希表
public class MyHashMap {
private static class Node {
public Integer key;
public int val;
public Node next;
public Node(Integer key, int val) {
this.key = key;
this.val = val;
}
}
private Node[] array;
public int usedSize;
private MyHashMap() {
this.array = new Node[8];
}
// 通过key值查找
private Integer get(int key) {
int index = key % array.length;
// 遍历当前index下标的链表
for (Node cur = array[index]; cur != null; cur = cur.next) {
if (cur.key == key) {
return cur.val;
}
}
return null;
}
// JDK1.7之前是头插, JDK1.8之后是尾插[这里演示的是尾***r /> private void put(int key, int value) {
// 1.有值就替换
int index = key % array.length;
Node cur = this.array[index];
while (cur != null) {
if (cur.key == key) {
cur.val = value;
return;
}
cur = cur.next;
}
// 2.没有就添加
cur = this.array[index];
Node newNode = new Node(key, value);
if (cur == null) {
array[index] = newNode;
} else {
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
++this.usedSize;
if (loadFactor() >= 0.75) {
resize();
}
}
private double loadFactor() {
return 1.0 * this.usedSize / array.length;
}
private void resize() {
Node[] newArray = new Node[array.length * 2];
// 1.遍历旧哈希表
for (int i = 0; i < array.length; i++) {
Node cur = array[i];
while (cur != null) {
Node curNext = cur.next;
// 2.计算当前key在新数组当中的下标
int index = cur.key % newArray.length;
Node curN = newArray[index];
// 找新数组当前下标的尾巴
if (curN == null) {
newArray[index] = cur;
} else {
while (curN.next != null) {
curN = curN.next;
}
curN.next = cur;
}
// 每个节点都是尾插法, 这里既然插入了, 这个节点就应该是null, 否则会陷入死循环
cur.next = null;
cur = curNext;
}
}
array = newArray
相比于尾插, JDK7之前的头插也很方便
以下是头插代码的核心实现
/*
哈希表的核心: 有一个数组, 数组上的每个元素又是一个链表
*/
HashNode[] array = new HashNode[16];
private int size = 0;
// 核心方法
// 通过这个方法, 希望把 key 映射成数组下标
private int hashCode(int key) {
// 此处是简单求余, 实际上可以根据情况选取更复杂的计算方式: 根据 key 计算 md5 值再求余
return key % array.length;
}
private double loadFactor() {
return (double) size / array.length;
}
private void resize() {
HashNode[] newArray = new HashNode[array.length * 2];
// 遍历旧 hash 表, 进行搬运
for (int i = 0; i < array.length; i++) {
HashNode next = null;
for (HashNode cur = array[i]; cur != null; cur = next) {
next = cur.next;
int newIndex = cur.key % newArray.length;
// 把当前 cur 对应的节点头插到新的数组上
cur.next = newArray[newIndex];
newArray[newIndex] = cur;
}
}
array = newArray;
}
private void put(int key, int value) {
// 1. 先根据 key, 计算出下标位置
int index = hashCode(key);
/*
2. 看看 key 在 hash 表中是否存在
存在: 直接修改
不存在: 直接插入新节点
*/
for (HashNode cur = array[index]; cur != null; cur = cur.next) {
if (cur.key == key) {
// 找到了相同的 key 的元素, 直接修改 value
cur.value = value;
return;
}
}
//3. 经过上面的循环, 该 key 不存在, 就需要创建新的节点, 插入到链表(头***r /> HashNode newNode = new HashNode(key, value);
newNode.next = array[index];
array[index] = newNode;
++size;
/*
4. 如果持续插入, 就可能导致冲突概率越来越大, 链表越来越长, 就会影响到后续操作的效率: 解决方案就是扩容
为了衡量什么时候扩容, 引入一个概念 "负载因子"
计算: 元素个数/数组长度
*/
if (loadFactor() > 10) {
/*
10: 经过很多数据测试的得出 10 最合理
最好是根据实际的业务场景, 做实验(性能测试)
选取不同的负载因子, 在运行效率和占用空间上找到一个平衡点
负载因子:
越大: 可能影响效率(链表长度更长)
越小: 浪费的空间就越多
认为比较拥挤了, 就要进行扩容了
*/
resize();
}
}
7. 和Java类集的关系
HashMap 和 HashSet 中Java通过哈希表来实现 Map 和 Set
Java 中使用哈希桶的的方式进行解决冲突的
Java 会在冲突到达一定阈值的时候转换为搜索树(红黑树)
Java 中计算哈希值实际上调用的事 hashCode() 方法, 进行 key 的相等性比较是通过 equals 方法. 所以如果要自定义一个类作为 HashMap 或者 HashSet 则需要重写 equals 和 hashCode 方法, 保证相等的 equals 对象的 hashCode 相等.
import java.util.Objects;
class Person{
String id;
public Person(String id) {
this.id = id;
}
// 重写 hashCode 和 equals 方法
@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);
}
}
public class HashBuck<K, V> {
static class Node<K, V> {
K key;
V value;
Node next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
private Node<K, V>[] array = new Node[8];
private int usedSize;
private void put(K key, V value) {
int index = key.hashCode() % array.length;// 需要使用hashCode函数计算哈希地址
Node<K, V> cur = this.array[index];
while (cur != null) {
if (cur.key.equals(key)) {
cur.value = value;
return;
}
cur = cur.next;
}
cur = this.array[index];
Node<K, V> newNode = new Node<>(key, value);
if (cur == null) {
this.array[index] = newNode;
} else {
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
++this.usedSize;
if (loadFactor() >= 0.75) {
resize();
}
}
private void resize() {
Node<K, V>[] newArray = new Node[this.array.length << 1];
for (Node<K, V> cur : this.array) {
while (cur != null) {
int index = cur.key.hashCode() % newArray.length;
Node<K, V> curN = newArray[index];
Node<K, V> curNext = cur.next;
if (curN == null) {
newArray[index] = cur;
} else {
while (curN.next != null) {
curN = curN.next;
}
curN.next = cur;
}
cur.next = null;
cur = curNext;
}
}
}
private double loadFactor() {
return 1.0 * this.array.length / this.usedSize;
}
private V get(K key){
int index = key.hashCode()%this.array.length;
Node<K,V> cur = this.array[index];
while (cur != null){
if (cur.key.equals(key)){// 利用 equals 进行比较关键码是否相等
return cur.value;
}
cur = cur.next;
}
return null;
}
public static void main(String[] args) {
HashBuck hashBuck = new HashBuck();
hashBuck.put(1,11);
hashBuck.put(2,22);
hashBuck.put(3,33);
hashBuck.put(17,177);
hashBuck.put(24,244);
hashBuck.put(15,155);
Person person1 = new Person("123");
Person person2 = new Person("123");
hashBuck.put(person1, "张三");
hashBuck.put(person2, "李四");
System.out.println(hashBuck.get(person1));
System.out.println(hashBuck.get(17));
System.out.println(hashBuck.get(1));
}
}
输出结果：
李四
