本文基于java8
HashMap使我们在开发过程中经常用到的数据结构，在面试过程中也会经常问到，本篇博文就基于jdk1.8具体分析一下HashMap的实现。
首先看一下HashMap中的静态变量和一些类变量，(本篇只看链表结构用到的一些变量，树形结构接下来会分析)：
// 默认最大容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子：
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转换为树型结构的临界值：
static final int TREEIFY_THRESHOLD = 8;
// Node数组，保存着链表或者树的头结点，每个Index位置称为一个桶
transient Node<K,V>[] table;
// Node的Set
transient Set<Map.Entry<K,V>> entrySet;
// HashMap的size
transient int size;
// 修改次数
transient int modCount;
// 扩容的阈值
int threshold;
// 加载因子
final float loadFactor;
接下来看一下table中的元素，也就是Node类：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
....
}
节点构成了HashMap的存储单元，每个节点都保存有该节点的key, key的hash值，value和next节点。
我们来回顾一下日常开发中经常用到的HashMap的方法：
- put();
- get(Object key)
- entrySet()
- remove(Object key)
首先从无参构造方法说起
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
默认构造方法很简单，知识初始花了一个loadFactor的值，这个值就是HashMap的负载因子，默认为0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
具体这个值怎么用，我们接下来再讲
接下来看往HashMap里放数据的put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put()方法又调用了putVal方法，我们继续跟踪下去：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab: Node数组 i：根据hash值计算的要put的数据所在的桶的位置 p: talbe[i]桶上的头结点 n: table的长度
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果table为null的话，调用resize()方法进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果table[i]的值为空，直接new出来一个节点传入key和value并赋给table[i],put操作完成
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))))
// 如果p不为空并且p与要put的数据hash值和key值都相同，使用节点e来保存p，此时e不为空
e = p;
else if (p instanceof TreeNode)
// 如果p是树节点，调用putTreeVal()方法向树中put数据
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果p不是树节点，则向链表中put数据
for (int binCount = 0; ; ++binCount) {
// 遍历至链表的尾结点，此时e为空
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表中node超过 TREEIFY_THRESHOLD 个，则将该链表转化为树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 遍历过程中遇到hash值和key均和要put的数据相同的情况，直接跳出循环，此时e不为空
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e不为空时将e节点的value替换为新值，并返回旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent参数为false或者e的当前value为空时进行替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//只有 e为空，也就是产生新的节点情况下size才会++，如果size > threshold 则对HashMap进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
通过分析putVal()方法我们可以得到如下结论：
1.HashMap的数组创建是在我们put第一个元素时调用resize()方法完成的
2.HashMap只有在put一个新key的情况下才会增加节点，否则的话只是替换key所在节点的value
3.HashMap的数组中，一开始是链表结构，在大于某个临界值时，会转化为树结构
那么 node在table数组中的下标是怎么确定的呢？
我们可以想一个最简单的方案，也就是key的hash值对table的length取余 即 hash % n，而在HashMap的实现实际上更精妙，它的做法是(n - 1) & hash, 这个值运算后的结果就是 hash % n
举个例子，假设n = 8 hash = 11,那么hash转化为二进制是1011，n - 1转化为二进制是0111 两者 进行&操作后值为0011，就是十进制的3
而 11 % 8的值也是3，这里用位运算其实是为了更高的执行效率。
细心的同学会发现，在putVal()末尾执行了afterNodeInsertion()方法， 这个是干什么用的呢？这里先不讨论，我们后面讲LinkedHashMap时再讨论。
接下来看resize()方法：
final Node<K,V>[] resize() {
// 旧table
Node<K,V>[] oldTab = table;
// 旧tab的length
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧的 临界值
int oldThr = threshold;
// 新的最大容量，临界值
int newCap, newThr = 0;
if (oldCap > 0) {
// 超出HashMap设置的最大容量，直接设置为int的最大值
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 {
//无参构造HashMap时会走到这里，newCap的值为16 newThr的值为16 * 0.75
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 以上几个判断条件都没有对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数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;// 将oldTab[j]的值赋给e 并将oldTab[j]位置置为null
if (e.next == null)
//如果e只有单一一个节点，直接找到e在newTab的下标并赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 遍历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;
}
其他地方都好理解，但是我们看代码的54 和 55行，
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
这里有点绕，它定义了两个head和两个tail，这是干什么用的呢，我们来分析一下，假设旧数组的size为8，而扩容都是双倍扩容，那么新的容量就是16，而从上面put()方法的分析可知，Node寻找下标位置都是通过hash对size取余，那么我们再假设旧数组下标在0位置上的几个Node他们的Hash值分别为0、8、16、24、32、40，那么对新的size 16取余后分别为0、0、8、0、8，因此可以得出如下结论：
数组扩容后，旧数组nidex上的链表只会出现在新数组的index位置和index+oldCap位置。所以定义两个头尾节点，分别管理低位和高位的链表。理解了这一部分之后，下面的这部分就好理解了。
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
接下来我们分析HashMap的遍历
一般情况下我们遍历HashMap都是用这种方式：
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
我们就一步步分析，首先看entrySet()方法：
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
这个就比较简单了，返回了一个EntrySet的对象，我们在生成迭代器时，就是调用的这个对象的迭代器方法，那么我们就看一下EntrySet这个类：
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
。。。
}
内容有点多，我们先把其他的忽略掉，看一下iterator()方法，也很简单，返回了一个EntryIterator对象，我们继续跟到EntryIterator类：
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
好吧，我们在遍历时是用的next()方法找到了，调用了父类HashIterator的nextNode()方法，继续跟下去：
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
这里也比较简单，就是返回了next这个节点，那么这个节点在哪里初始化的呢？我们看一下HashIterator的构造方法：
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
我们可以看到，next这个节点的值，在初始化的时候，指向了HashMap的第一个不为空的节点，在外部调用next时，nextNode()方法会找寻下一个不为空的节点并返回。
接下来我们分析remove()方法：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
remove方法调用了removeNode方法并返回要删除节点的vaule,那么就继续跟踪removeNode方法：
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//tab: table n: table长度 index:删除节点的数组下标 p:要删除的节点
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 找到了key 和 hash均相同的节点
node = p;
//否则继续往下一个节点找
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 找到的节点刚好是某个桶的头结点，则将头节点赋给下一个节点
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
这个方法逻辑不太复杂，注释已经说的比较清楚了，这里不多做说明。
get(Object key)方法：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
接下来看getNode(hash(key), key))方法：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
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;
}
同样这个方法比较简单，只是找到要查找的key所在的桶，遍历并寻找元素即可。
至此，HashMap的CURD和遍历都已分析完毕，下一章我们继续分析HashMap的树形结构和转换的实现。
网友评论