Java8 HashMap源码的简单分析（1）
首先在阅读HashMap源码前，我们需要知道的：
一.数组：连续的存储结构，存储相同类型的数据。对于指定下标的查找，时间复杂度为o(1)；对于定值的查找，需要遍历数组，时 间复杂度为o(n)，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)。
二.单链表：离散的存储结构。单链表是由结点组成，而每个结点是由数据域和指针组成。单链表查询的时间复杂度最大为o(n);插入和删除仅需处理相邻结点之间的引用，时间复杂度为o(1)。
三.红黑树：红黑树是一种平衡二叉树，查询，修改，删除的时间复杂度均为o(lgn)。在jdk1.8后，主要适用于HashMap和TreeMap，TreeSet。HashMap中当链表长度超过8后转化为红黑树，提高查询和修改效率。
一.HashMap的数据结构
二.HashMap的初始化
/**
* 默认情况下，HashMap初始容量大小为16.即1<<4=16(10000=16)
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* HashMap的最大容量即2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认加载因子，即使用空间达到总空间的0.75时，需要扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表长度的最大值，链表长度大于 8 时，转换成红黑树处理
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 在转变成树之前，还会有一次判断，只有键值对数量大于 64
*才会发生转换。这是为了避免在哈希表建立初期，
*多个键值对恰好被放入了同一个链表中而导致不必要的转化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 声明存放链表的数组（哈希桶数组）
*/
transient Node[] table;
/**
* 将数据转换成set的另一种存储形式，这个变量主要用于迭代功能
*/
transient Set<Map.Entry> entrySet;
/**
* 实际存放的链表长度
*/
transient int size;
/**
* HashMap的数据被修改的次数，
*这个变量用于迭代过程中的Fail-Fast机制，
* 其存在的意义在于保证发生了线程安全问题时，
* 能及时的发现（操作前备份的count和当前modCount不相等）并抛出异常终止操作
*/
transient int modCount;
/**
* HashMap的扩容阈值，在HashMap中存储的Node键值对超过这个数量时，
*自动扩容容量为原来的二倍
*/
int threshold;
/**
* HashMap的负载因子，可计算出当前table长度下的扩容阈值：
*threshold = loadFactor * table.length
*/
final float loadFactor;
/**
*
* @param initialCapacity 初始容量
* @param loadFactor 负载因子
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
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);
}
tableSizeFor方法的使用及介绍：
Java HashMap之tableSizeFor方法
二.HashMap的put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* @param onlyIfAbsent //表示只有在该key对应原来的value为null的时候才插入，
* //如果value之前存在了，就不会被新put的元素覆盖
* @param evict evict参数用于LinkedHashMap中的尾部操作，这里没有实际意义
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定义存储Node的数组tab,p表示tab上的某Node节点，n为tab的长度，i为tab的下标
Node[] tab; Node p; int n, i;
//判断当table为null或tab的长度为0时，即table尚未初始化，通过resize()得到初始化的
table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过(n-1) & hash 计算出的值作为tab的下标i，并把tab[i]的引用指向p，如果p为null,则调
//用NewNode()创建该链表的第一个节点并赋值给tab[i]
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//定义即将插入的节点e
Node e; K k;
//若判断e节点key的hash值与p节点相等且key值相等或符合equals方法，则
// 判断两者key相同，将p的引用指向e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果p是红黑树节点，那么插入后仍是红黑树节点，所以我们直
//接强制转型p后调用TreeNode.putTreeVal方法返回的引用赋给e
//(putTreeVal内部进行了遍历，存在相同hash时返回被覆盖的TreeNode，否则返回null)
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
//定义一个计数器来计算当前链表的元素个数，并遍历链表
for (int binCount = 0; ; ++binCount) {
//遍历过程中若p.next为null时，说明链表到头了，直接在p的后面插入新的节点
if ((e = p.next) == null) {
//把新节点的引用赋给p.next
p.next = newNode(hash, key, value, null);
//如果链表长度超过转换为红黑树的最大长度，即调用treeifyBin()转换成红
//黑树，若未超过，则break退出
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;
//e是当前遍历的节点p的下一个节点，p = e 就是依次遍历链
//表，每次循环时p都是下一个node节点
p = e;
}
}
if (e != null) { // existing mapping for key(针对已存在key进行的处理)
//oldValue，即原存在的节点e的value值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//覆盖操作，将插入节点的value值设置为已存在节点的value
e.value = value;
//在hashmap中没有任何操作，是个空函数，他存在主要是为了linkedHashMap的一些后
//续处理工作
afterNodeAccess(e);
//HashMap返回的是被覆盖的oldValue，已经return不会执行下一步操作
return oldValue;
}
}
//数据被修改次数(但并没有那么简单哦)
++modCount;
//当HashMap中存在的node节点大于threshold时，HashMap进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
二.HashMap的get()方法
public V get(Object key) {
Node e;
//根据传入的key，算出其hash值，调用getNode()返回节点e，若e节点为空，则返回null，反
//之，返回其value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
//通过(n - 1) & hash运算，得出该节点所在的tab下标，若其与tab都不为空，即继续判断,若为
//空则返回空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断key相等，需判断hash值相等并符合equals()方法，若key相等则返回第一个节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//遍历链表直到next为空
if ((e = first.next) != null) {
//当这个table节点上存储的是红黑树结构时，在根节点first上调用getTreeNode方
//法，在内部遍历红黑树节点，返回TreeNode
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
//只要e.next不为空，即一直比较key,若key相等则返回e
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
在读完put()源码后，get()就很好理解了。这些牛P的代码我们不一定要会写，但我们要懂那些大佬们的目的，尽量跟着他们的思路，想想自己和他们的解决方式的不同，以及自己能否写出漂亮的代码，甚至去优化他们的，那你就很牛P了(ps:当然我是不行，我能知道它每一步是要干啥就不错了)。好啦，先就讲这两个方法，其他方法在日后的学习中，会陆续推出，大家一起加油，源码路漫漫，不要放弃哦。
作者：hmi_java
