1 HashMap总结
HashMap 是 Map 接口的实现，允许key的值为null，但是是一个非线程安全的容器，如果想构造线程安全的 Map 使用 ConcurrentHashMap。 也可以用
Collections.synchronizedMap(new HashMap)
来创建一个线程安全的Map。
HashMap 无法保证内部存储的键值对的有序性所以是无序的。
HashMap 的底层数据结构是数组（又称桶） + 链表。遍历 HashMap 需要的时间损耗由桶的数量 和 键值对数量决定。因此，如果遍历元素很重要的话，不要把初始容量设置的太高或者负载因子设置的太低。
HashMap 有两个重要参数：初始容量、负载因子，初始容量指的就是 hash 表桶的数量，负载因子是一种衡量哈希表填充程度的标准，当哈希表中存在足够数量的键值对时，哈希表会进行扩容。
HashMap 尽量要用迭代器自己的 remove 方法，外部 remove 方法都可能会导致 fail-fast 机制。如果在迭代器创建的过程中修改了 map 的结构，会抛出异常
ConcurrentModificationException
2 HashMap底层实现
HashMap的继承 / 实现结构如下：
2.1 AbstractMap类
AbstractMap抽象类实现了一些简单且通用的方法，为了实现不可修改的 map，仅需要继承这个类并且提供 entrySet 方法的实现即可。它将会返回一组 map 映射的某一段，返回的集合是 Set 类型，不应该支持 add 或者 remove 方法，并且它的迭代器也不支持 remove 方法。
为了实现可修改的 map，必须额外重写这个类的 put 方法，entrySet.iterator() 返回的 迭代器 必须实现 remove() 方法。
2.2 重要内部类 / 接口
2.2.1 Entry接口和Node类
Map中定义了内部接口Entry，如下：
map的entry就是一个键值对
interface Entry<K,V> { K getKey(); V getValue(); V setValue(V value); boolean equals(Object o); int hashCode(); }
HashMap中定义了静态内部类？Node 实现了Map中的Entry接口，Node 节点会存储四个属性，hash值，key，value，指向下一个Node节点的引用，并且也要实现上述五个方法：
final int hash; final K key; V value; Node<K,V> next;
2.2.2 KeySet 类
KeySet 类继承于 AbstractSet 抽象类，是由 HashMap 中的 keySet()方法来创建实例的，旨在对HashMap 中的键进行操作。
KeySet() 在 Map 接口中进行定义的，在 HashMap 中将其操作进行了实现。
// 返回一个Set集合，包含了map中的key。 public Set<K> keySet() { // 这里 keySet 是 AbstractMap 中的 Set<K> ks = keySet; if (ks == null) { // 如果 ks 为空，就创建一个 KeySet 对象 ks = new KeySet(); keySet = ks; } return ks; }
相应的类：
final class KeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<K> iterator() { return new KeyIterator(); } public final boolean contains(Object o) { return containsKey(o); } public final boolean remove(Object key) { return removeNode(hash(key), key, null, false, true) != null; } public final Spliterator<K> spliterator() { return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super K> 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); } if (modCount != mc) throw new ConcurrentModificationException(); } } }
2.2.3 Values类
和 KeySet 类很相似，是由 HashMap 中的 values() 方法来创建实例的，只是 Values 旨在对键值对中的 value 值进行操作。
public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; } return vs; }
相应的类：
final class Values extends AbstractCollection<V> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<V> iterator() { return new ValueIterator(); } public final boolean contains(Object o) { return containsValue(o); } public final Spliterator<V> spliterator() { return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? 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.value); } if (modCount != mc) throw new ConcurrentModificationException(); } } }
其实和 key 的操作差不多
2.2.4 EntrySet类
HashMap中还有直接对键值对进行操作的内部类 EntrySet，同样的是由 entrySet() 方法进行创建的，也是HashMap实现的Map接口的方法：
// 返回一个 Set 集合，此集合包含了 map 中的键值对 public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; // 如果 es 为空创建一个新的 EntrySet 实例 return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; }
相应的类：
final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super Map.Entry<K,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); } if (modCount != mc) throw new ConcurrentModificationException(); } } }
2.3 HashMap 1.7 底层结构
JDK1.7 中，HashMap 采用数组 + 链表的实现，链表被用来处理冲突。当位于一个桶中的元素较多时，即 hash 值相等的元素较多时，通过 key 依次查找的效率较低
HashMap的桶其实就是一个 Node 数组，链表的每一个节点都是 Node 的一个具体对象，存储了hash，key，value，next属性
所以 HashMap 的整体结构如下：
2.4 HashMap 1.8 底层结构
与 JDK 1.7 相比，1.8 在底层结构方面做了一些改变，当每个桶中元素大于 8 的时候，会转变为红黑树，目的就是优化查询效率，JDK 1.8 重写了 resize() 方法，将在多线程访问下头插法可能导致环的问题修改为使用尾插法。
2.4.1 jdk1.8 的其他改进
优化hash()方法
采用高16位异或低16位，避免低位相同高位不同的哈希值产生严重的碰撞。
扩容时插入顺序的改进
其他
函数方法：forEach, compute系列
Map的新API：merge, replace
2.5 HashMap 重要属性
2.5.1 初始容量
HashMap 的默认初始容量是由 DEFAULT_INITIAL_CAPACITY 属性确定的。默认值是16。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
2.5.2 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
由于桶的容量要求是2的n次幂（具体原因放在下面讲），int型的数据最大是2^31 - 1不满足需求，所以就取了个2的30次幂。
2.5.3 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
扩容机制的原则是：当
HashMap 中存储的数量 > HashMap 容量 * 负载因子
时，就会把 HashMap 的容量扩大为原来的二倍。扩容的时机：1.7在添加数据之前进行扩容判断，1.8在添加数据之后或判断树化时会进行扩容判断。
2.5.4 树化阈值
static final int TREEIFY_THRESHOLD = 8;
在进行添加元素时，当一个桶中存储元素的数量 > 8 时，会自动转换为红黑树。
2.5.5 链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
在进行删除元素时，如果一个桶中存储元素数量小于该阈值，则会自动转换为链表
2.5.6 扩容临界值
static final int MIN_TREEIFY_CAPACITY = 64;
当桶数组容量小于该值时，优先进行扩容，而不是树化。
2.5.7 扩容阈值
在 HashMap 中，使用 threshold 表示扩容的阈值，也就是 初始容量 * 负载因子的值。
其中通过 tableSizeFor 方法来计算扩容之后的容量。
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 ^ 29，这段代码的实现过程如下：
由上图可知 2^29 次方的数组经过一系列的或操作后，会算出来结果是 2^30 次方。所以扩容后的数组长度是原来的 2 倍。
2.6 HashMap构造函数
传入初始容量 initialCapacity 和负载因子 loadFactor 的构造方法
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); }
只带有 initialCapacity 的构造函数
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } 最终
也会调用到上面的构造函数，不过这个默认的负载因子就是 HashMap 的默认负载因子，即0.75
无参构造函数
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; }
初始化默认负载因子0.75
带有map的构造函数
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
直接把外部元素批量放入 HashMap 中。
2.7 put全过程
以1.8为基准。为了更直观的查看，将put方法提取出来流程图如下：
具体的源代码如下，可以结合注释以及上面的示意图来看
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果table 为null 或者没有为 table 分配内存，就resize一次 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 指定hash值节点为空则直接插入，这个(n - 1) & hash才是表中真正的哈希 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 如果不为空 else { Node<K,V> e; K k; // 计算表中的这个真正的哈希值与要插入的key.hash相比 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 若不同的话，并且当前节点已经在 TreeNode 上了 else if (p instanceof TreeNode) // 采用红黑树存储方式 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // key.hash 不同并且也不再 TreeNode 上，在链表上找到 p.next==null else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 在表尾插入 p.next = newNode(hash, key, value, null); // 新增节点后如果节点个数到达阈值，则进入 treeifyBin() 进行再次判断 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果找到了同 hash、key 的节点，那么直接退出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 更新 p 指向下一节点 p = e; } } // map中含有旧值，返回旧值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } // map调整次数 + 1 ++modCount; // 键值对的数量达到阈值，需要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
这个方法涉及五个参数
hash : put 放在桶中的位置，在 put 之前，会进行 hash 函数的计算。
key : 参数的 key 值
value : 参数的 value 值
onlyIfAbsent : 是否改变已经存在的值，也就是是否进行 value 值的替换标志
evict : 是否是刚创建 HashMap 的标志
2.8 扩容机制
HashMap 中的扩容机制是由 resize() 方法来实现的，程序流程图大致如下：
对应的源码如下，大家可以结合示意图与注释来理解。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // 存储old table 的大小 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 存储扩容阈值 int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 如果old table数据已达最大，那么threshold也被设置成最大 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 左移扩大二倍, else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 扩容成原来二倍 newThr = oldThr << 1; // double threshold } // 如果oldThr > 0 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 如果old table <= 0 并且 存储的阈值 <= 0 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果扩充阈值为0 if (newThr == 0) { // 扩容阈值为 初始容量*负载因子 float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 重新给负载因子赋值 threshold = newThr; // 获取扩容后的数组 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 如果第一次进行table 初始化不会走下面的代码 // 扩容之后需要重新把节点放在新扩容的数组中 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 重新映射时，需要对红黑树进行拆分 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 遍历链表，并将链表节点按原顺序进行分组 do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 将分组后的链表映射到新桶中 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
上面代码主要做了这几个事情：
1. 判断 HashMap 中的数组的长度，也就是 (Node<K,V>[])oldTab.length() ，再判断数组的长度是否比最大的的长度也就是 2^30 次幂要大，大的话直接取最大长度，否则利用位运算扩容为原来的两倍
if (oldCap > 0) { // 如果old table数据已达最大，那么threshold也被设置成最大 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 左移扩大二倍, else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 扩容成原来二倍 newThr = oldThr << 1; // double threshold }
2. 如果数组长度不大于0 ，再判断扩容阈值 threshold 是否大于 0 ，也就是看有无外部指定的扩容阈值，若有则使用，因为 HashMap 中的每个构造方法都会调用 HashMap(initCapacity,loadFactor) 这个构造方法，所以如果没有外部指定 initialCapacity时，初始容量是 16，然后根据 this.threshold = tableSizeFor(initialCapacity); 求得 threshold 的值。
// 如果oldThr > 0 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr;
3. 否则，直接使用默认的初始容量和扩容阈值（在 table 刚刚初始化的时候执行）
// 如果old table <= 0 并且 存储的阈值 <= 0 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }
然后会判断 newThr 是否为 0，为0的情况在于上面逻辑判断中的扩容操作，可能会导致位溢出。
在扩容后需要把节点放在新扩容的数组中，这里也涉及到三个步骤：
1.循环桶中的每个 Node 节点，判断 Node[i] 是否为空，为空直接返回，不为空则遍历桶数组，并将键值对映射到新的桶数组中。
2.如果不为空，再判断是否是树形结构，如果是树形结构则按照树形结构进行拆分，拆分方法在 split 方法中。
3.如果不是树形结构，则遍历链表，并将链表节点按原顺序进行分组。
if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 重新映射时，需要对红黑树进行拆分 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 遍历链表，并将链表节点按原顺序进行分组 do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 将分组后的链表映射到新桶中 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } }
2.9 get全过程
对应的源码如下，大家可以结合示意图与注释来理解。
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } 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) { // 总是会check 一下第一个元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 如果不是第一个元素，并且下一个元素不是空的 if ((e = first.next) != null) { // 判断是否属于 TreeNode，如果是 TreeNode 实例，直接从 TreeNode.getTreeNode 取 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 如果还不是 TreeNode 实例，就直接循环数组元素，直到找到指定元素位置 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
