Java1.8-HashMap源码分析入门（上）
引入:HashMap是什么？最直白的印象就是key-value键值对，那么，当我们put()一个值到HashMap中之后，这个数据到底是怎么存储的呢？又是以怎样的数据结构形式呢？
假如我们现在执行了hashmap.put(1,"joy");,我们看下源码执行了什么：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
调用了putVal()=====>
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; //Node数组
Node<K,V> p; //Node
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，一个是数组Node[],这时我们可以猜测HashMap是使用数组存储信息的！
那么，Node又是什么呢？，我存入的是key=1,value="joy";这个int型key和String型value是怎么变成Node的呢？我们看下Node的结构:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;//敲黑板，敲黑板
......现在我们清楚了，我们的key-value被对应的存在了Node的key-value中了。此时我们注意到Node自己还保存了一个名为next的Node对象，我们想到了什么？没错，链表，也就是说，Node与Node之间是以链表的形式联系的，当前的Node会记住下一个Node。这样的话，HasnMap的结构就清晰了----数组+链表，看下图:
既然HashMap就是数组和链表组成的，那么我们会有两个疑问：
- 这个数组默认长度是多少？
- 我们put(1，"joy");并没有指定这个Node放在数组的第几位以及对应链表的第几位，那么这个存放的规则是什么呢？
针对第一个问题，我们再来看下HashMap初始化的时候执行了哪些默认操作。
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//朋友们，这个构造函数很干净有没有！只有一个 this.loadFactor = DEFAULT_LOAD_FACTOR;
//而这个DEFAULT_LOAD_FACTOR常量又是谁呢？继续找到它：
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//根据上面的官方注释我们看的出来，这个是默认的负载因子（load factor），什么是负载因子，
//我们后面再讨论，但我们知道，这个和数组默认的长度好像并没有关系。既然构造HashMap的时候没有指定数组的长度，那我们在put的时候怎么往数组里添加数据呢？继续看下刚刚put的代码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
调用了putVal()=====>
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; //Node数组
Node<K,V> p; //Node
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 {
........从源码上看出来，当我们向HashMap里put数据的时候，首先，判断了当前Node数组(也就是table)是不是空，或者长度是不是0；如果是，则执行resize()方法，并把执行结果重新返回给Node数组，看来resize()很有可能具有初始化的功能。我们刚刚知道，前面并未对Node数组进行设置，所以此时会执行resize()方法，我们再看下resize()方法:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//取出Node数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;//取出Node数组的length
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
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
}
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语句，我们看下if的条件：Node数组lenth(oldCap )大于0吗？显然，前面说了，Node数组还没有设置，所以这里一定是==0，所以直接跳到else里:newCap = DEFAULT_INITIAL_CAPACITY;果然这里赋值了一个静态常量，看下这个常量：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16没错,16！(1左移4位，相当于1*2的4次方=16),到这里我们知道了，HashMap默认的数组长度是16个单位！
第一个问题解决了，那么，第二个问题（时刻记得上面的HashMap结构图：数组+链表），这里的Node数组有默认16个单位，每个单位又是一条长长的Node链表，我们只是执行了put(1,"joy")；那这个“快乐”被存到了什么位置？又是按照什么策略存放的呢？
这里我先引用网上的描述：我们把HashMap的Node数组想象为16个桶，当我们put数据进来的时候，先对key进行hash，比如得到2564842,然后执行%16取余(实际并非%16而是位运算)，这样取到的余数(0-15)就是对应的桶的索引了，然后将该数据添加到对应桶的索引的链表的最后面。如此put的过程就完成了。
对应到代码里，可以分为两步：
- 对key执行hash；
- 新建Node,并将Node拼接在对应的链表的后面：
//第一步
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);
}
//第二步
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;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); //敲黑板，敲黑板
//将新建的Node添加到对应的位置
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;
}
如此，put进去的值就被放在的对应的Node里了。
以上两个问题解决了。本节先到这里，下一节我们讨论这样几个问题：
- HashMap 为什么默认数组长度是16？
- 16个单位真的够用吗？如果不够用该怎么办？
- 如果多线程执行put数据，get数据，是否是安全的？如何解决安全的问题？