HashMap浅析

1. 几个概念

1.1、哈希表

哈希表主干用的是数组:将当前元素的关键字通过哈希函数运算得到存储的位置,通过数组的下标一次定位即可完成数据操作。对于哈希表来说无论是新增、删除、查找的性能都很高,用时间复杂度来说就是o(1)。

1.2、哈希冲突

虽然哈希表的各项元素操作性能都很高,但是也存在一个问题,比如两个不同的元素,通过哈希函数得出实际存储地址却相同,这时候就没办法直接去存储了,这也就是哈希冲突,哈希冲突时无可避免的,再好的哈希函数也会存在冲突的,那么对于哈希冲突该怎样解决呢?方法有很多,比较好的就是链地址法(数组+链表),而Jdk1.7版本下的HashMap就是采用了这种方法。
来直观的看看链地址法,直接上图:

Alt text

上图中的M4-0、M4-1、M4-2、M4-3是由于通过哈希函数计算后,得到的地址相同、于是就通过链表的方式追加、覆盖元素。若直接定位到的数组位置不包含链表,那么查找、添加就非常快,若包含,则链表元素越多,越慢

2. 源码分析

2.1、jdk1.7以下 HashMap集合put方法

Alt text

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
41
42
43
44
45
46
public V put(K key, V value) { 
//1.若数组为空,则新建一个数组
  if (table == EMPTY_TABLE) {
  inflateTable(threshold);
}
//2.key为空时,则遍历数组,若存在key==null的位置,则将value覆盖掉,返回之前的value,否则调用addEntry()保存到table[0]位置
if (key == null)
return putForNullKey(value);
//3.key不为空时,计算key的hashCode
int hash = hash(key);
//4.遍历数组,并计算出hashCode对应元素的下标
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//5.遍历table数组,若数组中存在hashCode与当前key对应的hashCode相等且key也相同,就覆盖掉value的值,并返回之前的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//6.若数组中不存在与当前添加元素hashCode相等、key相同的元素,就调用addEntry()方法
addEntry(hash, key, value, i);
return null;
}

private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; //长度必须是2的非零幂
return h & (length-1); //table数组的下标计算:hashCode与(table数组长度减一)做与(&)运算
}

2.2、jdk1.8以上 HashMap集合put方法

虽然jdk1.7以下中数组+链表方式解决了哈希冲突问题,但是在性能上还是存在明显的瓶颈,上面也分析了,当某个链表中元素达到一定数量时候,遍历查找非常慢,于是在jdk1.8的时候,当某个链表元素大于等于8的时候就改用红黑树进行存储。
Alt text
整个过程归结为:
(1)、通过Key计算HashCode 与或 key本身右移16位得到 hash值
(2)、如果hash值不相等没有发生碰撞,直接放入bucket桶中
(3)、如果hash值发生碰撞了,以链表的方式链接到后面
(4)、如果链表长度超过阀值( TREEIFY THRESHOLD==8),就把链表转成二叉树(红黑树),链表长度低于6,就把红黑树转回链表
(5)、如果hash值相等并且key也相等,则节点已经存在就替换并返回旧值
(6)、如果bucket满了(容量16*加载因子0.75 = 12),就需要 resize(扩容2倍后重新排序)

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
41
42
43
44
 public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) // 如果数组是null或者数组为空,就调用resize()进行初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //(n-1)&hash 算出下表,这个和1.7是一样的
tab[i] = newNode(hash, key, value, null); // 如果当前计算出来的位置为null,就新建一个节点
else {
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 若计算出来的位置上不为null,它和传入的key相比,hashCode相等并且key也相等
e = p; // 那么将p赋给e
else if (p instanceof TreeNode) // 如果p是树类型
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 则按照红黑树的结构存入进去
else {
for (int binCount = 0; ; ++binCount) { // 遍历p,p是链表
if ((e = p.next) == null) { // 如果p的下一个节点是尾节点(尾节点.next=null)
p.next = newNode(hash, key, value, null); // 在p的后面创建一个节点,存放key/value(尾插法,多线程并发不会形成循环链表)
if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD = 8,即当binCount达到7时转换成红黑树数据结构,
                      // 因为binCount是从0开始的,达到7时p链表上就有8个节点了,所以是链表上达到8个节点时会转变成红黑树。
treeifyBin(tab, hash); // 这里先就不展开了,红黑树不会,有时间再研究
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 若上面两个条件都不满足,此时e = p.next,也就是将p的下一个节点赋给p,进入下一次循环
}
}
if (e != null) { // existing mapping for key,jdk这段注释意思是存在key的映射,我的理解是传入的key在p位置找到它自己的坑被别人占了
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) // 下面就是将value存入被占的位置,并将旧的value返回
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount; // 修改次数加一
if (++size > threshold) // 若已有的键值对数大于阈值,就扩容
resize();
afterNodeInsertion(evict);
return null;
}

2.3、哈希的生成

jdk1.8中的源码:

1
2
3
4
5
6
7
8
9
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//节选的一部分代码
n = (tab = resize()).length;
p = tab[i = (n - 1) & hash]
}

主要有三步:
(1)取hashcode值:h = key.hashCode()
(2)高位参与运算 h>>>16(右移16位,空位用0补齐),”^”号 按位异或
(3)取模运算:(n-1)&hash

2.4、jdk1.8中新加数据结构(红黑树)

在jdk1.8中有两处操作与红黑树有关联,e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 以及 treeifyBin(tab, hash);
putTreeVal与 treeifyBin两种方法的实现相类似,前者是向树种插入节点,后者是树化的操作。
上treeifyBin源码吧

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//该方法是将链表结构转化为红黑树结构
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//若数组为空或者长度小于最小树化的值,则扩容而不进行树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//找到数组中bucket位置,第一个节点记为e
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//Node转化为TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
//若当前链表为空,则赋值头指针为p
if (tl == null)
hd = p;
//否则将p添加到链尾
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//链表头节点放入table的index位置
if ((tab[index] = hd) != null)
//通过treeify方法将链表树化
hd.treeify(tab);
}
}


// TreeNode类的实例方法
final void treeify(Node<K,V>[] tab) {
//根节点
TreeNode<K,V> root = null;
//循环遍历节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//链表中的下一个节点
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//根节点为空,根节点为黑色,并将当前节点x作为根节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
//否则插入到原有的树种
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//第二层循环,从根节点开始寻找合适x的位置插入
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
//若x的hash值(Node类中有hash属性)小于节点p的,则往p的左子树中继续寻找
if ((ph = p.hash) > h)
dir = -1;
//否则在右子树中寻找
else if (ph < h)
dir = 1;
//若hash值相等,并且key不可比,则使用System.identityHashCode进行比较来决定左右树
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
//根据上面计算出的dir值决定p是左子树下移还是右子树下移,若为空,则为合适的位置,否则继续循环
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
//根据dir决定x是作为xp的左孩子还是右孩子
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//红黑树的平衡
root = balanceInsertion(root, x);
break;
}
}
}
}
//由于插入后的平衡调整可能会更换整棵树的根节点,需要通过moveRootToFront方法确保table[index]中的节点与插入前相同
moveRootToFront(tab, root);
}

2.5、扩容机制

在jdk1.7中,数据量达到(容量16*加载因子0.75 = 12)时,首先会创建一个大容量的数组,然后依次重新计算原集合中所有元素的索引,然后重新赋值,若某个元素的hash值发生了冲突,使用单链表的头插入方法,同一位置的新元素总是放在链表的头部,与元集合链表对比,扩容后的可能就是倒序的链表。
jdk1.8中扩容部分有改动,这里放上1.7的源码,容易理解

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
41
42
43
44
45
46
47
48
49
void resize(int newCapacity) {
//扩容前的Entry数组记为oldTable
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//若扩容前的数组大小达到最大(2^30)了
if (oldCapacity == MAXIMUM_CAPACITY) {
//修改阈值为int的最大值(2^31-1),并不再进行扩容
threshold = Integer.MAX_VALUE;
return;
}
//初始化一个新的Entry数组
Entry[] newTable = new Entry[newCapacity];
//将数据转移到新的Entry数组里
transfer(newTable);
//HashMap的table属性引用新的Entry数组
table = newTable;
//修改阈值
threshold = (int) (newCapacity * loadFactor);
}


void transfer(Entry[] newTable) {
//src引用了旧的Entry数组
Entry[] src = table;
int newCapacity = newTable.length;
//遍历旧的Entry数组
for (int j = 0; j < src.length; j++) {
//取得旧Entry数组的每个元素
Entry<K, V> e = src[j];
if (e != null) {
//for循环后,旧的Entry数组不再引用任何对象
src[j] = null;
do {
Entry<K, V> next = e.next;
//重新计算每个元素在数组中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
//元素放到数组上
newTable[i] = e;
//访问下一个Entry链上的元素
e = next;
} while (e != null);
}
}
}

static int indexFor(int h, int length) {
return h & (length - 1);
}

3、关于HashMap的一些问题(摘自网络一些博客以及个人总结)

3.1、为什么用HashMap?

HashMap是一个散列桶(数组和链表),它存储的内容是键值对(key-value)映射
HashMap采用了数组和链表的数据结构,能在查询和修改方便继承了数组的线性查找和链表的寻址修改
HashMap是非synchronized,所以HashMap很快
HashMap可以接受null键和值,而Hashtable则不能(原因就是equlas()方法需要对象,因为HashMap是后出的API经过处理才可以)

3.2、HashMap的工作原理是什么?

HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Node
Node[] table=new Node[16] 散列桶初始化,table
class Node {
hash;//hash值
key;//键
value;//值
node next;//用于指向链表的下一层(产生冲突,用拉链法)
}

3.3、有什么方法可以减少碰撞?

(1)、扰动函数可以减少碰撞,原理是如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这就意味着存链表结构减小,这样取值的话就不会频繁调用equal方法,这样就能提高HashMap的性能。(扰动即Hash方法内部的算法实现,目的是让不同对象返回不同hashcode。)
(2)、使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。为什么String, Interger这样的wrapper类适合作为键?因为String是final的,而且已经重写了equals()和hashCode()方法了。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。

3.4、拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?

之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。

3.5、说说你对红黑树的见解?

每个节点非红即黑
根节点总是黑色的
如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
每个叶子节点都是黑色的空节点(NIL节点)
从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)

3.6、HashTable

数组 + 链表方式存储
默认容量: 11(质数 为宜)
put:
索引计算 : (key.hashCode() & 0x7FFFFFFF)% table.length
若在链表中找到了,则替换旧值,若未找到则继续
当总元素个数超过容量*加载因子时,扩容为原来 2 倍并重新散列。
将新元素加到链表头部
对修改 Hashtable 内部共享数据的方法添加了 synchronized,保证线程安全。

3.7、HashMap ,HashTable 区别

默认容量不同。扩容不同; 线程安全性,HashTable 安全; 效率不同 HashTable 要慢因为加锁;

3.8、ConcurrentHashMap 原理

HashTable和HashMap的实现原理几乎一样,差别无非是1.HashTable不允许key和value为null;2.HashTable是线程安全的。但是HashTable线程安全的策略实现代价却太大了,简单粗暴,get/put所有相关操作都是synchronized的,这相当于给整个哈希表加了一把大锁,多线程访问时候,只要有一个线程访问或操作该对象,那其他线程只能阻塞,相当于将所有的操作串行化,在竞争激烈的并发场景中性能就会非常差。

3.9、我们可以使用CocurrentHashMap来代替Hashtable吗?

我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。它们都可以用于多线程的环境,但是当Hashtable的大小增加到一定的时候,性能会急剧下降,因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation),不论它变得多么大,仅仅需要锁定map的某个部分,而其它的线程不需要等到迭代完成才能访问map。简而言之,在迭代的过程中,ConcurrentHashMap仅仅锁定map的某个部分,而Hashtable则会锁定整个map。