HashMap源码分析篇(JDK1.8)
摘要:
突然发现对源码的阅读较少,所以近段时间静下心来耐心好好研究一些源码,看看大神的设计思想,多学习。
为何要阅读源码?阅读源码的目的是什么?如何阅读源码?
源码分析的目的并不是单纯的为了肢解代码, 这只是过程, 它的目的是为了让自己能够对代码的理解更加深刻, 培养自己的直观理解力, 增强自己的代码输出能力, 同时也增加自己对复杂代码的理解能力. 所谓的源码分析, 其实是对一个复杂的源码进行降维分析, 降到自己的能力所能理解的程度, 这样, 随着源码分析能力的增进, 个人的理解能力也会上升.
HashMap概述
首先,看一下HashMap的继承结构:
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
在JDK1.8之前,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。
而JDK1.8中,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。
下图是JDK1.8之前的HashMap结构,左边部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。稍后会好好聊一下如何映射。
JDK1.8之前的HashMap都采用上图的结构,都是基于一个数组和多个单链表,hash值冲突的时候,就将对应节点以链表的形式存储。如果在一个链表中查找其中一个节点时,将会花费O(n)的查找时间,会有很大的性能损失。到了JDK1.8,当同一个hash值的节点数不小于8时,不再采用单链表形式存储,而是采用红黑树,如下图所示。
简而言之,JDK1.8后,HashMap是由于数组+链表+红黑树实现,当链表个数大于8,当前链表重组,由Node转换为TreeNode,由链表转换成红黑树。
HashMap常用操作
HashMap的构造方法
HashMap有4个构造方法,分别是:
1 2 3 |
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } |
1 2 3 |
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } |
1 2 3 4 5 6 7 8 9 10 11 12 |
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } |
1 2 3 4 |
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } |
这里面有一个方法:tableSizeFor,很重要,这是HashMap扩充的算法。
在了解这个方法之前先来看一下HashMap的一些变量:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 默认的初始容量是16,大小必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量,也就是说2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树,太小或太大都会转换频繁都可能从而影响性能下降
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表,该值应该比上面的8小
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组,总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数,注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
int threshold;
// 填充因子
final float loadFactor;
HashMap的扩容机制
然后我们继续回来说tableSizeFor方法,先看一下源码:
1 2 3 4 5 6 7 8 9 |
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } |
这个算法的含义是:求得大于或等于传入值cap的最小2的幂次方,举几个例子:
传入10,返回16;
传入20,返回32;
传入100,返回128;
传入1024,返回1024;
分析原理如下:
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 |
/** * 返回给定目标容量的两个大小的幂。进行 无符号右移 + 或运算 * 举个两个例子 =============================例子1============================= cap=10 00000000 00000000 00000000 00001010 int n = cap - 1 = 9; 00000000 00000000 00000000 00001001 n |= n >>> 1; 00000000 00000000 00000000 00001001 00000000 00000000 00000000 00000100 结果: 00000000 00000000 00000000 00001100 n |= n >>> 2; 00000000 00000000 00000000 00001100 00000000 00000000 00000000 00000011 结果: 00000000 00000000 00000000 00001111 n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; n最后结果为: 00000000 00000000 00000000 00001111 15 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 此时n为15,n不小于0,也不大于最大容量,所以n+1 = 16 =============================例子2============================= cap= 00100000 00000000 00000000 00100000 (随便举的例子,边界) int n = cap - 1; 00100000 00000000 00000000 00011111 n |= n >>> 1; 00100000 00000000 00000000 00011111 00010000 00000000 00000000 00001111 结果: 00110000 00000000 00000000 00011111 n |= n >>> 2; 00110000 00000000 00000000 00011111 00001100 00000000 00000000 00000111 结果: 00111100 00000000 00000000 00011111 n |= n >>> 4; 00111100 00000000 00000000 00011111 00000011 11000000 00000000 00000001 结果: 00111111 11000000 00000000 00011111 n |= n >>> 8; 00111111 11000000 00000000 00011111 00000000 00111111 11000000 00000000 结果: 00111111 11111111 11000000 00011111 n |= n >>> 16; 00111111 11111111 11000000 00011111 00000000 00000000 00111111 11111111 结果: 00111111 11111111 11111111 11111111 n最后结果为: 00111111 11111111 11111111 11111111 这个值为2的30次方-1 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 此时n为2的30次方-1,n不小于0,也不大于最大容量(最大值为2的31次方),所以n+1 = 2的30次方 结束。 说明: 其实说白了,这个扩充方法,就是你传入一个值,hashMap会计算大于等于这个值的最小2的幂次方 如果我这么说还没明白的话,那我再说一遍 其实说白了,这个扩充方法,就是你传入一个值,hashMap会返回一个值,这个值是2的幂次方,也是大于等于入参的最小2的幂次方的值 举个例子, 传入10,返回16 传入200,返回256 传入1000,返回1024 传入2048,返回2048 算法:传入一个值,计算大于等于此值的最小2的幂次方。 */ |
该算法设计之巧妙,话不多说,继续。
put方法
首先要说一下为什么大多数人都选择用String类型作为key,因为在HashMap中key的key是要计算hash值的,而String类覆写了Object的equals方法和hashCode方法,所以我们可以愉快的使用String类型作为我们的key。
先看一下put方法的源码吧:
1 2 3 |
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } |
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 |
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) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) // 当i = (n - 1) & hash的链表没有任何节点时,创建第一个节点 tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // key的hash相等,key相等,说明之前有完全同等的key存在,在后续会将新的value替换掉old value,并返回old value // 此时,e代表此链表第一个node e = p; else if (p instanceof TreeNode) // 此时为红黑树,在红黑树上添加节点 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 遍历链表 // 如果key和节点的key完全相等,在后续新的value会覆盖此node的value,并返回old value // 如果遍历结束还是没有发现相等的key,则创建一个新的node,并检查当前链表的个数,如果大于链表的桶阀值,则会将单链表转换为红黑树 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } |
keySet方法
keySet()方法可以获取包含key的集合,调用该集合的迭代器可以对key进行遍历
1 2 3 4 5 6 7 8 |
public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } |
KeySet是HashMap的内部类,继承AbstractSet,KeySet中获取迭代器为keyIterator
1 2 3 4 5 |
final class KeySet extends AbstractSet<K> { ... public final Iterator<K> iterator() { return new KeyIterator(); } ... } |
而KeyIterator继承HashIterator
1 2 3 4 |
final class KeyIterator extends HashIterator implements Iterator<K> { public final K next() { return nextNode().key; } } |
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 |
abstract class HashIterator { Node<K,V> next; // next entry to return Node<K,V> current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); } return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } |
get方法
先看一下源码:
1 2 3 4 |
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } |
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 |
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first; Node<K,V> 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)))) // 已经找到key对应的链表或者红黑树,如果头结点符合条件则返回头结点 return first; // 接下来则是遍历链表节点的每一个key,如果有符合的,则返回该节点,如果没有符合的,则返回null 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; } |
源码中的注释已经写得很明了了,就不再继续阐述了。
entrySet方法
entrySet跟keySet有点类似,具体先看源码:
1 2 3 4 |
public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; } |
EntrySet是HashMap的内部类,继承AbstractSet,EntrySet获取的迭代器为EntryIterator
1 2 3 4 5 6 |
final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator(); } ...... } |
EntryIterator是HashMap的内部类,继承HashIterator
1 2 3 4 |
final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } } |
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 |
abstract class HashIterator { Node<K,V> next; // next entry to return Node<K,V> current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); } return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } |
forEach方法
java8的lambda表达式,其实就是调用该类的forEach方法,还是看源码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
@Override public void forEach(BiConsumer<? super K, ? super V> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e.key, e.value); } if (modCount != mc) throw new ConcurrentModificationException(); } } |
remove方法
remove方法是从list或map中筛除该元素,可以是根据key,也可以是根据下标(list)。
1 2 3 4 5 |
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } |
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 |
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { // p目前是该链表或红黑树的头结点 Node<K,V> node = null, e; K k; V v; // 先检查头结点是否符合要remove的条件 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; // 找到符合元素,暂且标记,后续还要做一些操作 // 如果头结点不存在,则需要遍历该链表或红黑树, // 如果存在,继续标记, // 如果不存在,循环结束,标记为null,视为未找到符合元素 else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) // 如果该节点属于红黑树,则需要做更多的事情,如自旋、是否需要转换链表等。 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) // 如果是头结点,则把第二个节点放到头结点位置 tab[index] = node.next; else // 如果不是头结点,则把该节点的上一个的next指向该节点的下一个,从而删除该节点 p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; } |
remove方法的逻辑已经在源码里阐述了,就不在过多解释了。
全局逻辑视图
总结
HashMap结合了数组和链表的优点,使用Hash算法加快访问速度,使用散列表解决碰撞冲突的问题,其中数组的每个元素是单链表的头结点,链表是用来解决冲突的
HashMap有两个重要的参数:初始容量和加载因子。这两个参数极大的影响了HashMap的性能。初始容量是hash数组的长度,当前加载因子=当前hash数组元素/hash数组长度,最大加载因子为最大能容纳的数组元素个数(默认最大加载因子为0.75),当hash数组中的元素个数超出了最大加载因子和容量的乘积时,要对hashMap进行扩容,扩容过程存在于hashmap的put方法中,扩容过程始终以2次方增长。最大为2的30次方。
HashMap是泛型类,key和value可以为任何类型,包括null类型。key为null的键值对永远都放在以table[0]为头结点的链表中,当然不一定是存放在头结点table[0]中。对于是否能存放key或者value能否存放null类型,可以参考《阿里巴巴开发手册》-(五)集合处理-11
最后:
第一次看源码,有不足之处可以在下方或留言板给博主留言,多多指教
看源码一定要有求知欲和耐心,强烈的求知欲是最核心的驱动力,因为这是一个很枯燥的过程,当了解完其中的原理,我们在日常开发过程中,可以让我们写出高质量的代码。
人生充满着期待,梦想连接着未来。
发表评论