HashMap实现原理

前言

今天去面试,之前也没有做什么准备,拿到面试题中有一题感觉很熟悉但是我不会,HashMap实现原理,回来后在网上看了一些文章,讲的还是比较详细的。

Hash表

Hash表可以看作是一个综合考量的结果,我们知道数组是连续空间储存,是可以根据下标来找到相关的元素的,而链表是通过指针来指向其他的元素,对于一个元素来说只会知道相邻的元素是什么,在Java里面代表就是ArrayList和LinkedList,Hash表即横向为数组纵向为链表的形式,综合考量了查询以及插入和删除的速度。

HashMap

Node

HashMap是存储键值对的集合,看了HashMap源码可以知道,事实上它是存储元素Node的数组,而Node实现了Map.Entry<K, V>接口,也就是说他可以看作是一个Entry数组。Node的构造分别由key、value、hash、和next而来

key和value分别是Node的键值

hash是有静态方法生成(见下方代码),若key是null,hash为0,不为null,hash是对h(key的hashcode值)和h移位16进行异或运算获得,原因后文解释

next是该索引下下一个Node的引用,指向下一个Node,next可以为null值,表示该索引下只有一个元素。

构造

JDK的API表示HashMap可以指定初始容量 initialCapacity 和负载因子loadFactory,不指定则默认分别为16和0.75,初始容量制定了初始Node的数组大小,负载因子表示数组容量达到满溢的比例,当数组装满就会触发resize,扩容数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//静态内部类Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
1
2
3
4
5
6
7
8
//hash的获取
int hash = hash(key);
static final int hash(Object key) {
int h;
//按位操作符,异或表示两者有一个是1,但不全为1,即为1,其他为0
//移位操作符,无符号右移16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

补充一下移位操作符

1
2
3
4
5
6
7
8
9
10
<<	左移运算符	相当于整个二进制数相对于小数点左移,即乘以2的次幂
>> 右移运算符 相当于整个二进制数相对于小数点右移,即除以2的次幂的商
>>> 无符号右移 忽略符号位,空位都以0补齐

对于正数来说<<<和<<是一样的,但是对于负数来说,右移后的高位,<<是补上1,<<<补上0
举个栗子:
-23在byte下的二进制表示为11101001,由23(00010111)取反加一得来
-23>>2 = 11111010 = -122
-23>>>2 = 58
可见区别无符号右移变味了正数

HashMap实现

KEY的索引生成策略
  1. 对key取hashcode,得到h
  2. 对h和h右移16位进行异或运算,得到hash
  3. hash对Node数组长度取模,得到索引
1
2
3
4
5
6
7
  /**
* 获取key的索引
* JDK1.7的源码,1.8的没找到。。。
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
put/get过程

无论是put还是get,都需要先计算索引,获取到索引后,put先查看该索引下是否为null,如果是则直接插入,如果不为null,继续判断该Node是否存在现插入的key,存在则直接覆盖,不存在则先判断是链表还是红黑树,开始遍历,同样判定Node是否存在现插入的key,有则覆盖,无则插入到头部,期间一旦元素个数超过8个,都会转换为红黑树结构。

get先检查Node数组状态,到了到索引位置后,先判定第一个元素hash值是否相等,有直接取出,没有判定数据结构遍历一一比对,这里用到了逻辑操作符的短路特点,若hash不一致也没必要继续判定了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
两个问题
  1. 为什么要对h进行右移16位的异或运算,不能直接以hashcode作为key来使用?

  2. 为什么取模是h & (length-1),不应该直接是h%length ?

    首先第一个问题,hashcode这个是通过hashcode()获取的,其结果是一个int型整数,而int的取值为-2^31-2^31,接近40亿,内存很难放下,设计者还认为这样的hashcode值还不足以分布均匀,(h = key.hashCode()) ^ (h >>> 16)是为了让低位区和高位区异或来融合各自的随机特性(16正好是32的一半),让hash变得更加的散
    第二的取模问题是因为容量一直2的次幂,length-1转换为一定是类似于0000000000001111的n个0和根号length个1,二者进行按位与运算后就获得了低位hash,而这恰恰是取模的余数,这样计算更加快捷

RESIZE

当数组充满时就会触发扩容,数组长度变为之前的两倍,这个时候原来的索引就要重新计算,但是在HashMap这里同样有了小小的优化。

先说结论:重排后的索引要么时原位置,要么是原索引+原数组长度

原因:由于它的数组长度为2的次幂,计算到hash都是没有变化的,假设length = 2^k,取模时,之前的(2^k - 1)&hash变成了(2^(k+1) - 1 )&length,这里可以看出后者比前者大了2^k,那么都减一后后者会比前者多一个1,和hash进行按位与运算时,若hash该位置是1,那最后该位就是1,hash为0,最后就为0,转换为十进制就是一个原数组长度的区别。

相关

  1. HashMap 实现原理
  2. HashMap实现原理及源码分析
  3. HashMap实现原理