HashMap源码分析（一）
在jdk8以前，HashMap的存储结构有两种：顺序结构和链表结构。在jdk8之后，对HashMap进行了优化（主要体现在结构和扩容算法）,添加了红黑树结构来优化对HashMap的管理。本文着重分析HashMap在树化前的逻辑。
1. 存储结构
在jdk8以前，HashMap的存储结构有两种：顺序结构和链表结构，如下图所示：
结构图.png
在HashMap中，维护着一个数组（之后称table）作为数据存储的基本结构，而table的每一项是一个Node<K,V>的类型，作为链表结构的头节点。调用put()方法存储（key值未存储过，替换的情况下文详细介绍）时，会先通过key值计算其HashCode码，然后将其进行一些运算（具体计算过程在下文中介绍），获得其对应的index，之后判断table的index位是否有数据，若有数据的话，就通过位于该位置的头节点开始遍历链表，并将其放在链表的下一个空位。
2. 原理
2.1 属性
HashMap没有从父类（AbstractMap）继承任何属性值，所有用到的属性均为其自己的属性。下面我们来看一下他们：
/**
*这个属性是HashMap的默认存储容量，为16，HashMap的容量通常为2的n次幂，有关这个规定，有人解释为是计算机进
*行2次幂的计算非常高效。但是我认为主要原因还是与HashMap的存储结构和存储方式有关（下文解释）。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**这个属性是HashMap的最大容量，为2的30次幂。*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的负载因子，当未设置负载因子时，默认为0.75。意思是每当HashMap里的item数超过（总容量/负载因子）
* 时，就进行扩容。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**hashmap中存储数值的数组，在第一次使用的时候才会初始化,并且在达到阀值的时候扩容。*/
transient Node<K,V>[] table;
/**本map中存储的键值对个数*/
transient int size;
/**hashMap被结构性修改的次数*/
transient int modCount;
/**阀值，当HashMap中的键值对数达到该值时进行扩容*/
int threshold;
/**加载因子*/
final float loadFactor;
2.2 构造函数
HashMap总共有四个构造函数：
/**
* 默认的构造函数，所有值使用默认值
*
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 指定容量大小的构造函数（注意此处的容量大小必须大于等于0，在之后会使用大于该数字的第一个2的n次幂作为最终容
* 量）
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 指定容积大小和加载因子的构造函数（注意此处的容量大小必须大于等于0，在之后会使用大于该数字的第一个2的n次幂
* 作为最终容量）
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
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);//扩容阀值（就是当容量超过这个值时进行扩容，讲道理这里本应该是 this.threshold = tableSizeFor(initialCapacity) * this.loadFactor; 但是看之后代码发现阀值在table实例化的时候（resize()方法内）进行的重新赋值。
}
/**
* 包含子map的构造函数
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
我们接下来就详细看一下tableSizeFor()这个方法，看看它是怎么通过我们给它的容量，决定扩容的阀值的：
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
这个方法，其实是返回大于（或等于）cap（传入参数）且最近的2的n次幂的数。可能有些难以理解，接下来我们可以看 HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四） ，博主通过图文很详细地说明了这个算法是如何进行的。
2.3 put实现
我们来看put方法的实现：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
我们先看一下hash()的算法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从这里我们发现最后算出的hash码又让他的高16位和低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;//tab:当前table p:指定index的Node n:tab长度 i:index
if ((tab = table) == null || (n = tab.length) == 0)//若table为空，则通过resize()初始化，并拿到tab长度
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//若index位置的链表为空，则创建新链表头节点放入
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;//e:链表的当前node k:node的当前key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//若链表头节点的hash值、key都与放置的键值对的key相等，则获取该头节点
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//转换treenode（先记住，下文分析）
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//若链表子节点的hash值、key都与放置的键值对的key相等，则获取该子节点（获取方法写在该循环第一个if中）
break;
p = e;
}
}
if (e != null) { // existing mapping for key
//若有key相同，则修改其中的value即可
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//给子类扩展的方法，此类中为空方法
return oldValue;
}
}
++modCount;
if (++size > threshold)//若map中的键值对数量超过阀值，则扩容
resize();
afterNodeInsertion(evict);//给子类扩展的方法，此类中为空方法
return null;
}
从代码中我们可以知道，HashMap计算index的算法为：
i = (n - 1) & hash
那么它又是如何保证我们得到的index在table的范围内呢？
n是table的大小，要求其必须满足2的n次幂，所以，将其转化成二进制数为“0…10…0”，从右到左数第i位为1(i>=0)，其余的位置为0，对其进行-1的操作后，就会变成“0…1…”，从第(i-1)位开始，右边全为1，这就是说任何数和它做与运算时，都不考虑这个数高于i的位上的数，所得出的结果一定是小于n的数。
2.4 get实现
我们接着看get()方法的实现：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
再往下看：
final Node<K,V> getNode(int hash, Object key) {//前面我们可以知道，这个hash是通过key计算出hashCode并进行高16位和低16位异或后的产物
//tab:table first:链表的头节点 e:遍历用的节点 n:table长度 k: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) {//若table已初始化并且index位的头节点不为空
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))//找value的判断有三个，hash值是否相等(必须)，key的引用地址是否相等和key值是否相等(满足任意一个)
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;
}
2.5 HashMap的扩容
接下来，我们进入最重要的一个环节，也是许多面试官喜欢问的问题，HashMap的扩容。话不多说，我们直接上源码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//获取扩容前的table
int oldCap = (oldTab == null) ? 0 : oldTab.length;//获取之前table的容量
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)//新的容量等于double oldCap，若小于最大容量并且旧容量大于等于默认容量的话，double threshold。这么计算的原因是：oldThr = oldCap * threshold, newThr = newCap * threshold = oldCap * 2 * threshold = oldThr * 2
newThr = oldThr << 1; // double threshold
}//接下来两个else都是初始化table的操作
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;//若之前的threshold不为空，则是因为实例化HashMap时传入了初始容量（详见构造函数），这时拿到传入后经过计算的容量
else { // zero initial threshold signifies using defaults
//使用默认容量和默认阀值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//当table为空时的初始化阀值
float ft = (float)newCap * loadFactor;//计算出理论上的阀值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);//判断最大容量相关逻辑
}
threshold = newThr;//这是最后获得到的阀值
@SuppressWarnings({"rawtypes","unchecked"})//屏蔽掉IDE可能报的警报
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//new一个新的table
table = newTab;//再把table指向新table，为什么不直接 table = (Node<K,V>[])new Node[newCap]?
if (oldTab != null) {//遍历赋值
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//将旧的table空间释放
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//重新计算index
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;//next节点
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//这里也是一个重点，因为oldCap是2的n次幂，所以这个式子只拿了扩容后最高位的数，若为0，则说明扩容后通过计算得出的index不变，不需要移位，若为1，则将该位移动到其该去的位置上
//若为0，则说明该节点不用移位，将其放到不用移位的链表下
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {//若为1，则说明该节点需要移位，将其放到需要移位的链表下
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;
}
网友评论