基于JDK1.8的HashMap分析
HashMap的强大功能,相信大家都了解一二。之前看过HashMap的源代码,都是基于JDK1.6的,并且知其然不知其所以然,现在趁着寒假有时间,温故而知新。文章大概有以下几个方面:
- HashMap的数据结构
- put方法
- get方法
- 其他注意点
(一)HashMap的底层数据结构
1 static class Node<K,V> implements Map.Entry<K,V> { 2 final int hash; 3 final K key; 4 V value; 5 Node<K,V> next; 6 7 Node(int hash, K key, V value, Node<K,V> next) { 8 this.hash = hash; 9 this.key = key; 10 this.value = value; 11 this.next = next; 12 } 13 14 public final K getKey() { return key; } 15 public final V getValue() { return value; } 16 public final String toString() { return key + "=" + value; } 17 18 //hashCode等其他代码 19 }
首先,HashMap 是 Map 的一个实现类,它代表的是一种键值对的数据存储形式。Key 不允许重复出现,Value 随意。jdk 8 之前,其内部是由数组+链表来实现的,而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。
底层数据结构就是 数组 + 链表 + 红黑树(长度>8),其中有一个静态内部类
1 static class Node<K,V> implements Map.Entry<K,V>
这个静态内部类就是一个小的方块,在jdk1.8之前只在构造方法里面初始化的,现在是在第一次put的时候初始化的。
(一)HashMap的put方法
put 方法的源码分析是本篇的一个重点,因为通过该方法我们可以窥探到 HashMap 在内部是如何进行数据存储的,所谓的数组+链表+红黑树的存储结构是如何形成的,又是在何种情况下将链表转换成红黑树来优化性能的。带着一系列的疑问,我们看这个 put 方法:
1 public V put(K key, V value) { 2 return putVal(hash(key), key, value, false, true); 3 }
也就是put方法调用了putVal方法,其中传入一个参数位hash(key),我们首先来看看hash这个方法。
1 static final int hash(Object key) { 2 int h; 3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 4 }
是一个静态final方法。这是为什么key可以位null的原因了,当插入的key值为null,他会自动把他当作0进行处理
并且调用了key的hashcode,这就是为什么map的key一定要重写hashcode和equals方法。
并且与h右移16位异或。我们来详细看看这里为什么这样做。
我们知道,按位异或就是把两个数按二进制,相同就取0,不同就取1。
比如:0101 ^ 1110 的结果为 1011。异或的速度是非常快的。
把一个数右移16位即丢弃低16为,就是任何小于2^16的数,右移16后结果都为0(2的16次方再右移刚好就是1)。
任何一个数,与0按位异或的结果都是这个数本身(很好验证)。
所以这个hash()函数对于非null的hash值,仅在其大于等于2^16的时候才会重新调整其值,小于2^16不做调整直接取他的hashcode值。
至于为什么右移16位异或,这是知乎上面的一幅图片
看到没有,变得“松散”了很多,至于为什么,我也不是很清楚。我们继续往下看putVal这个方法。
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { 2 Node<K,V>[] tab; Node<K,V> p; int n, i; 3 //如果 table 还未被初始化,那么初始化它 4 if ((tab = table) == null || (n = tab.length) == 0) 5 n = (tab = resize()).length; 6 //根据键的 hash 值找到该键对应到数组中存储的索引 7 //如果为 null,那么说明此索引位置并没有被占用 8 if ((p = tab[i = (n - 1) & hash]) == null) 9 tab[i] = newNode(hash, key, value, null); 10 //不为 null,说明此处已经被占用,只需要将构建一个节点插入到这个链表的尾部即可 11 else { 12 Node<K,V> e; K k; 13 //当前结点和将要插入的结点的 hash 和 key 相同,说明这是一次修改操作 14 if (p.hash == hash && 15 ((k = p.key) == key || (key != null && key.equals(k)))) 16 e = p; 17 //如果 p 这个头结点是红黑树结点的话,以红黑树的插入形式进行插入 18 else if (p instanceof TreeNode) 19 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 20 //遍历此条链表,将构建一个节点插入到该链表的尾部 21 else { 22 for (int binCount = 0; ; ++binCount) { 23 if ((e = p.next) == null) { 24 p.next = newNode(hash, key, value, null); 25 //如果插入后链表长度大于等于 8 ,将链表裂变成红黑树 26 if (binCount >= TREEIFY_THRESHOLD - 1) 27 treeifyBin(tab, hash); 28 break; 29 } 30 //遍历的过程中,如果发现与某个结点的 hash和key,这依然是一次修改操作 31 if (e.hash == hash && 32 ((k = e.key) == key || (key != null && key.equals(k)))) 33 break; 34 p = e; 35 } 36 } 37 //e 不是 null,说明当前的 put 操作是一次修改操作并且e指向的就是需要被修改的结点 38 if (e != null) { 39 V oldValue = e.value; 40 if (!onlyIfAbsent || oldValue == null) 41 e.value = value; 42 afterNodeAccess(e); 43 return oldValue; 44 } 45 } 46 ++modCount; 47 //如果添加后,数组容量达到阈值,进行扩容 48 if (++size > threshold) 49 resize(); 50 afterNodeInsertion(evict); 51 return null; 52 }
注释已经很清楚了,我想说下这个初始化的问题
//如果 table 还未被初始化,那么初始化它 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
这个resize()方法既可以初始化,也可以扩容,都是这个函数完成的。并且在多线程下,不会出现之前的死锁导致cpu飙升至100%,只会出现数据丢失的问题。
//这部分我后续在补,有点多。
推荐阅读