前言
HashMap属于陈词滥调的话题，离上一次浏览源码曾经很久了，为了避免我又双叒遗记一些实现细节决定写篇文章，温故而知新
首先从结构HashMap说起，
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }loadFactor为负载系数默认0.75，用于计算Map扩容的阈值
我画了一下HashMap大抵的数据结构， 图中右边红色即为HashMap的table表，实际上就是一个Node的数组
Node<K,V>[] table;Node的构造很简略，罕用的表白单项链表的数据结构
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next;插入 put
一次插入操作实际上就是计算插入key的hash值并落到具体的table数组的某个下标， 在通过下标找到table上的head，在通过链表(或者红黑树)进行插入，如果该链表(或者树)已存在则对链表尾端进行插入操作，上面开始具体阐明具体的实现细节
以一次一般put操作为例
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }put操作并没有间接应用key自带的hash，而是通过hash()做一层转换
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }hash
key为空则将hash设置为0, 也意味着所有key为null的数据最初都固定寄存在table[0]中(多说一句，table[0]并不是只寄存key为null的node)
h = key.hashCode()) ^ (h >>> 16) //计算hashcode这里将key的hashcode码与本人的右移16位(行将32位中的高16位偏移到低16位)做按位异或运算。
为什么要这么做呢? 次要是减小后续取模的碰撞概率而做的优化
能够参考这篇文章，大抵意思就是因为取模运算只关注低位，如果hash低位同一性高会增大碰撞概率, 所以将高位做右移并做异或减少低位的随机性。
下图示意在掩码为9位应用HashMap.hash(table长度512)时比hashCode碰撞次数小百分之10
另外你会常常看到通过 (n - 1) & hash 这种形式获取以后hash值对应table数组下标的操作，其中n为table数组
其实原理很简略，首先hashmap会保障table的长度肯定为2的整数幂，上面以一个table长度为128的数组为例
当对table的长度n减1时，因为只有高位一个1所以其余全副置为1
所以当减1后的table与hash做与操作时，后果必然是table数组下某个下标，并保障其散布。
插入
查看table为空则扩容(扩容上面会讲到)，新的值没有对应的槽时创立新的Node，否则便插入已存在的链表(树)中，细节能够看下我为源码做的注解
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; //p即为table上头节点 if ((p = tab[i = (n - 1) & hash]) == null) //未找到槽则创立新的node作为头节点 tab[i] = newNode(hash, key, value, null); else { //插入已存在的链表中 ... } //记录批改次数，用于迭代校验 ++modCount; //size超出阈值则扩容 if (++size > threshold) resize(); //用于linked类型map，hashmap未实现 afterNodeInsertion(evict); return null;插入已存在的链表(树)中，当呈现hash碰撞(collision)时，即以后key的hash所对应的table中的node已存在时，hashmap会依据key的状况(有无反复)来抉择是插入链表尾部还是替换链表中某个node的值
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) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //p为table上的头节点 //如果雷同key，将p赋值给e， e示意已存在值为key的node //独自校验头节点是为了不便间接替换，防止判断是否为红黑树或链表 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //头节点node为红黑树时 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { //遍历至链表的尾端 e为被标记的反复key的node if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //链表长度超过8个转换为树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //当链表长度大于等于8并且tab长度大于64时才会转为红黑树 treeifyBin(tab, hash); break; } //发现雷同的key则标记 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; //onlyIfAbsent为False则替换 if (!onlyIfAbsent || oldValue == null) e.value = value; //用于预留给其余Map预留的刷新拜访程序接口，例如LinkedHashMap assessOrder指定为true时会将最新插入的node移至链表尾部 afterNodeAccess(e); return oldValue; } } ++modCount; //超出阈值resize if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }须要留神的几点
- 判断key是否反复须要满足对象地址雷同(==)或者equals是否相等(equals())
- 并不时说链表长度超出阈值(阈值为8)就会转为红黑树，同时还要满足以后hashmap的table长度大于64，否则只会做一次resize操作
resize
在hashap初始化时，或者table长度超过阈值等状况时，会对hashmap做resize操作， 个别会对table*2，table指定为2的倍数是为了不便做求模的计算，非凡状况比方table长度超过2^30时，则将阈值固定为2^31-1并间接返回
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//旧的table长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold;~~~~ int newCap, newThr = 0; //oldCap大于0调整threshold阈值 if (oldCap > 0) { //超过2^30 threshold阈值设为2^31 //设置为2^30是为了避免后续扩容操作溢出 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //这里对newCap扩容一倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //容量为0时newCap大小取决于阈值threshold的设置 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //阈值threshold以及capacity都为初始状态是启用默认设置 else { // zero initial threshold signifies using defaults //阈值未设置并cap为0的状况(初始化状态) newCap = DEFAULT_INITIAL_CAPACITY;//默认16 //初始化阈值12 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //依据newCap调配newThr 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; if (oldTab != null) { //遍历旧talble上的每个node for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) //e.hash & (newCap-1) -1 当newCap保障为2的n次幂时等同取模操作 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;//loHead代表旧的索引地位 Node<K,V> hiHead = null, hiTail = null;//hiHead代表扩容后新的索引地位 Node<K,V> next; do { next = e.next; //索引地位为cap & hashcode 扩容后索引是否有变动取决于hashcode&cap的位是否为1 概率上有一半的entry须要挪动 if ((e.hash & oldCap) == 0) {//为0示意该node不须要挪动table索引地位 if (loTail == null) loHead = e;//首次增加设置链表头 else loTail.next = e; loTail = e; } else {//e.hash & oldCap 为 1 搁置到新的链表上 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; //设置扩容后须要挪动的索引，新链表搁置到j+oldCap newTab[j + oldCap] = hiHead; } } } } } return newTab; }扩容后的调配：创立扩容后newTab后，接下来是重新分配原有的Node至newTable上，过程并不简单，首先是遍历原先的oldTable数组
if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { ... }~~~~首先获取每个数组元素下(bins)的头节点，如果头节点node的next为空间接将该node调配至新的newTable下，如果该元素下的链表由多个组成的话则遍历该链表，依据以后Node的hash值与原有数组长度oldCap的与运算后果来决定调配是否调配到新的bins下。比方上面的示例，同一个bins下的hashcode只能保障oldCap-1的&雷同，所以链表中的node被重新分配的概率为1/2， 即链表中有一半的node将会重新分配。
1111 0000 0010 1001 0101 1101 1011 1011 hashcode
0000 0000 0000 0000 0000 0000 0001 0000 16为oldCap
0000 0000 0000 0000 0000 0000 0010 0000 32为newCap
Map.get
get绝对就比较简单了，get(key)外部调用了getNode并传递了key的hashcode，做法也很简略，获取到该key所对应再table中的第一个node，如果是链表就遍历链表获取value，红黑树则做树的查找操作
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //满足三个条件 1. table不为空 2. table长度大于0 3. 以后hash的对应的索引node不为空 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)))) return first; 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; }//红黑树
LinkdedHashMap
LinkedHashMap继承于HashMap，其大部分实现是统一的，那么它是通过什么形式保障有序的呢？
首先LinkedHashMap重写了HashMap的newNode办法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { //LinkedHashMap.Entry继承Node类 LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); //将新增的node增加至链表尾部 linkNodeLast(p); return p; }LinkedHashMap.Entry继承Node类
static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }Entry相比Node多保护了向前和向后的援用，也就是LinkedHashMap相比HashMap多保护了一个双向链表来满足依照程序迭代的需要，每次插入会将Node插入链表尾部。
前面的就很好了解了，Map的遍历是基于迭代器的设计模式，LinkedHashMap从新实现了Iterator接口
final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } }不言而喻，nextNode理论就是获取链表中的下一个节点
final LinkedHashMap.Entry<K,V> nextNode() { LinkedHashMap.Entry<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); current = e; next = e.after; return e; }另外LinkedHashMap能够通过assessOrder指定新增Node移至尾部，感兴趣的能够看看源码实现比较简单。