概述
HashMap是Java的一个集合类，是我们在开发中经常使用的。本文记录个人阅读源码的一些步骤和理解。阅读步骤大致为：变量-->构造方法-->常用方法。
在JDK7中，HashMap的底层数据结构为：数组+链表的形式。
image
在JDK8中，HashMap的底层数据结构为：数组+链表+红黑树（TreeNode），增加红黑树的结构。
image
变量
- loadFactor 加载因子
默认加载因子为0.75f,为何是0.75而不是其他的值呢？
首先理解一下，什么是加载因子。
加载因子是表示Hsah表中元素的填满的程度。如果加载因子越大,填满的元素越多，所以空间利用率提高，但是冲突的机会加大了。反之亦然
冲突的机会越大，查找所需要的成本增加，查找时间也相应的增加 了。反之亦然。
结合前面两条，我们必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷。这种平衡与折衷本质上是数据结构中有名的"时间复杂度-空间复杂度"矛盾的平衡与折衷。
加载因子的值是可以大于1的。 - threshold
threshold表示当HashMap的size大于threshold时会执行resize操作。 - size
记录数组的长度 - modCount
modCount是记录HashMap发送结构性变化的次数，比如扩容、rehash。
另外大概了解一下HashMap的最大容量 1<<30也就是2的30次方，初始化容量为16。
构造方法
HashMap(int, float)
为了方便阅读，注释直接写在了代码里面。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始化容量必须在 1<<30 以内
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 调用了tableSizeFor方法，该方法是返回给定的`initialCapacity`值的向上取最近的2的幂。比如传递的值为12，返回16。
this.threshold = tableSizeFor(initialCapacity);
}
HashMap(int)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
该构造方法，只是指定了初始化容量，使用默认的加载因子，调用`HashMap(int, float)`方法。
常用方法
put 插入
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;
if ((tab = table) == null || (n = tab.length) == 0)
// 如果table为空，调用resize()方法，初始化一个table。
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) // 如果是p节点是红黑树节点，调用红黑树的put方法。
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);
// 如果binCount的大小大于等于TREEIFY_THRESHOLD-1（TREEIFY_THRESHOLD默认为8），调用treeifyBin方法，后面单独介绍该方法。
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;
// 根据oblyIfAbsent是否更新值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 修改 modCount
++modCount;
// 如果table大小大于了阈值，则需要扩容。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上面已经介绍了put方法的主流程，接下来分析一下该方法中留下的几个问题。
- treeifyBin方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 判断是否需要扩容，MIN_TREEIFY_CAPACITY的值：64,也就是说在大小为16、 32 的时候，不要进行结构转换
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 将节点转为树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p; // 将p树节点指向hd树节点
else {
p.prev = tl; // 当前p树节点指向 p树节点的前一树节点
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
treeifyBin方法主要是把容器里的元素变成树结构。当HashMap的内部元素数组中某个位置上存在多个hash值相同的键值对，这些Node已经形成了一个链表，当该链表的长度大于等于7的时候，会调用该方法来进行一个特殊处理。
get 取值
源码中get方法代码如下，为了方便阅读，在代码中会写上相应的注释。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
这段代码比较简单，调用了getNode()方法，并传入hash(key)和key，所以说取值的过程在getNode中，下面看看该方法的具体实现：
final Node<K,V> getNode(int hash, Object key) {
// 定义一个新的table数组、首节点
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断table数组是否为空，并且根据hash值算出 tab[(n - 1) & hash]是否为空，其中一个条件为空，说明key没有对应的value值。
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断首节点的hash和key是否都相等，如果都等，直接返回首节点
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)
// 调用 红黑树的getTreeNode方法
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;
}
getNode方法的过程相对而言是比较简单的，上面注释基本上比较易懂的，在整个流程中，红黑树的取值方法，没有说到，接下来看看getTreeNode方法中主要流程。
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
getTreeNode方法的实现过程如下：
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
// ph: p节点的hash值，pk:p节点的key值
int ph, dir; K pk;
// pl: p节点的左节点， pr：p节点的右节点
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
// p节点的hash值大于了 h（h是待get值的hash值），将左节点赋值给p节点
p = pl;
else if (ph < h)
// p节点的hash值小于了 h（h是待get值的hash值），将右节点赋值给p节点
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
// 走到了这儿，说明p.hash==h,只需要匹配key是否相等就好了。
return p;
else if (pl == null)
// 左节点为空，将右节点赋值给p节点
p = pr;
else if (pr == null)
// 右节点为空，将左节点赋值给p节点
p = pl;
// kc参数在首次使用比较键时缓存equivalentClassFor（key）。
// comparableClassFor方法：只有当传入对象的运行时类型符合“class C implements Cormparable <C>”，则返回k的Class，否则返回null。
// compareComparables方法: 如果pk匹配kc（k的筛选可比类），则返回k.compareTo（pk），否则返回0。
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
在本文中，主要是对常用的方法get、put做了一个学习了解。
文章来源：JDK8:HashMap源码学习
网友评论