JDK 源码分析之HashMap之一
本源码研究是基于JDK1.8的，JDK版本不同，会有略微的差别。
1 什么是HashMap
HashMap是一种以key-value形式存储数据，数据存储结构以数组与链表为结构存储数据的，其中以hash算法得到数据的存储位置，高效管理存取的一种数据结构。
2 HashMap的基本原理图
3 下面我们以断点调试的方式进行源码分析
public static void main ( String[] arg ) {
HashMap<String,Object> hashMap = new HashMap<>(); hashMap.put( "1","50" ); hashMap.put( "2","lisi" ); hashMap.put( "3","50" ); hashMap.put( "4","lisi" ); hashMap.put( "5","50" ); hashMap.put( "6","lisi" ); hashMap.put( "7","50" ); hashMap.put( "8","50" ); hashMap.put( "9","lisi" ); hashMap.put( "10","50" ); hashMap.put( "11","50" ); hashMap.put( "12","50" ); hashMap.put( "price","50" );
}
通过断点调试，首先会进入
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这个方法，这个方法hash(key)函数为注入对象，紧接着就会进入这个方法之中
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); （1）}
在方法（1）中key.hashCode()直接调用了string类的hashCode()的值，其中的原理，请看String有关的源码解读，会返回h=3373707，然后拿3373707的二进制与它的二进制数右移16位得到的结果进行异或运算 得到h=3373752。紧接着会进入
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i; （2）
if ((tab = table) == null || (n = tab.length) == 0) （3）
n = (tab = resize()).length; （4）
if ((p = tab[i = (n - 1) & hash]) == null) （5）
tab[i] = newNode(hash, key, value, null); （6）
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) （7）
e = p;
else if (p instanceof TreeNode) （8）
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); （9）
else {
for (int binCount = 0; ; ++binCount) { （10）
if ((e = p.next) == null) { （11）
p.next = newNode(hash, key, value, null); （12）
if (binCount >= TREEIFY_THRESHOLD - 1) （13）
treeifyBin(tab, hash); （14）
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) （15）
break;
p = e;
}
}
if (e != null) { （16）
V oldValue = e.value; （17）
if (!onlyIfAbsent || oldValue == null) （18）
e.value = value; （19）
afterNodeAccess(e); （20）
return oldValue;
}
}
++modCount; （21）
if (++size > threshold) （22）
resize(); （23）
afterNodeInsertion(evict); （24）
return null; （25）
}的核心方法之中，在（3）中首先会判断 table是否为空，因为是首次进入，一定为空，就会通过（4）的方法创建一个大小为16，扩容阀值为12的table数组，并且将数据赋值给tab，通过（5）即可得到下标值为8（h&15）即可得到。然后在通过方法（6）就可以得到一个Node，key是“name”，value是“zhangshan”，然后判断一下是否超过了阀值，是否进行扩容。
当hashMap.put( "name","zhangshan" )；运行这个方法的时候，putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)我们同理，分析下过程，在（5）中，由于已经有值了，所以会直接进入到（7）中，通过（7）的判断，会讲key的值赋值给e，通过（17）-（19）将新的值付给e,将原来的值付给oldValue中间变量，将原来的值返回，当然，通过 String info = ( String ) hashMap.put( "name","wangwu" );可以得来原来的值。
当运行hashMap.put( "price","50" ); 的时候，正好到了HashMap扩容的界限，那么，就会在（23）进入resize()的方法，
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; （30）
int oldCap = (oldTab == null) ? 0 : oldTab.length; （31）
int oldThr = threshold; （32）
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { （33）
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) （34）
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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]; （35）
table = newTab;
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; （36）
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;
}通过（30）-（32），创建一个oldTab 将原有的table保存，并且保存了阀值和大小 oldCap和oldThr，然后在（34）将oldCap和oldThr扩容2倍，并且分给新的中间变量newThr、newCap，
然后在（35）新创建一个扩容后的大小的table，在（36）的地方会将原来的table里面的值重新取出hash然后进行新的位置计算，然后把原来的值直接赋值给新的table数组的具体下标的位置，将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。