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
最后：
第一次看源码，有不足之处可以在下方或留言板给博主留言，多多指教
看源码一定要有求知欲和耐心，强烈的求知欲是最核心的驱动力，因为这是一个很枯燥的过程，当了解完其中的原理，我们在日常开发过程中，可以让我们写出高质量的代码。
人生充满着期待，梦想连接着未来。
发表评论