前言
JDK1.8的HashMap和之前版本已经存在不少差异,并且引入了红黑树和扩容的优化,所以有必要分析一下,加深理解。
结构介绍
要分析HashMap,首先要知道它能做什么,是个什么结构,然后由浅到深的进行分析(成员变量、方法、扩容等)。主要按照这个思路进行展开。
HashMap成员变量
//HashMap默认初始化容量: 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//超过这个临界值,就转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
//小于这个临界值,就从红黑树转成原来的结构
static final int UNTREEIFY_THRESHOLD = 6;
//红黑树结构最小的容量
static final int MIN_TREEIFY_CAPACITY = 64;
//Node数组来存储元素
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
final float loadFactor;
从成员变量可以看出JDK1.8针对某个临界变量做了红黑树的转换,为了满足红黑树结构则是需要有最小容量要求的。HashMap的初始容量是2的n次幂,方便利用移位运算进行定位角标。
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {}
public final V setValue(V newValue) {}
public final boolean equals(Object o) {}
}
Node是HashMap的基本数据结构.每个节点有自己对应的hash值和存储的key-value,由于HashMap的Node是基于链表的,所以持有下一个元素的引用next.
TreeNode结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 获取根节点
*/
final TreeNode<K,V> root() {}
/**
* 使根节点作为第一个节点
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {}
/**
*查找对应节点
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}
/**
* 获取节点数据
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {}
static int tieBreakOrder(Object a, Object b) {}
final void treeify(Node<K,V>[] tab) {}
final Node<K,V> untreeify(HashMap<K,V> map) {}
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {}
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {}
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {}
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) {}
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {}
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) {}
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {}
}
TreeNode是红黑树的基本结构,它有一个父节点parent,和左右叶子节点left,right,以及持有指向前一个节点的引用prev，节点的颜色标识red。以及它还提供了查找节点、返回根节点、红黑树的翻转、put等方法。
看一下TreeNode的继承体系:
TreeNode.png
可知
TreeNode继承自LinkedHashMap.Entry,而LinkedHashMap.Entry又继承自HashMap.Node.所以TreeNode是Node的子类型,方法中涉及到Node->TreeNode的强转。
源码剖析
1.构造函数剖析
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
如果采用无参的构造函数,则loadFactor为默认的0.75,初始化容量和threshold都为0.如果是有参的构造函数,则会根据tableSizeFor方法计算临界值`threshold :
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次幂。那到底是怎么计算出来的呢？我们知道Integer.MAX_VALUE转换成二进制是1111111111111111111111111111111,长度为31,要想求出最小2的n次幂的值,只需拼装出2进制位全为1的数值即可,有效位长度保持不变.如果一个数值二进制数为01101110101,则变为11111111111即可。那到底怎么移位能确保最终结果是全1呢？答案是按2的倍数递增。第一次移动一位然后进行或运算,则二进制数有效位的最高位的下一位肯定是1,例如0001000000000000000000000000000,向右移动一位求或,结果是0001100000000000000000000000000,此时有两个1,下一次移动两位,结果是0001111000000000000000000000000,此时有四个1,以此类推,直到移动16位,结果是0001111111111111111111111111111.再来看最后一行代码,如果n大于0,则判断n是否大于最大容量值,这里很显然没有超过最大容量,则进行n+1,得到结果0010000000000000000000000000000,即最小的2的n次幂的值。
2.put方法分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在put方法之前,先利用hash方法计算出key的hash值.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在JDK1.7中是利用indexFor()方法来计算角标的,如果length的长度为2的n次幂,任何一个数与length取模都可以转换成二进制 &的格式:h & (length-1),而&的效率要比%高.
static int indexFor(int h, int length) {
return h & (length-1);
}
但是JDK1.8并没有采用JDK1.7的这种方式,而是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在Node数组length比较小的时候，能使高低位都参与到Hash运算中。
移位
跟进去
putVal看一下:
//onlyIfAbsent true:当key不存在时才put进去,false:直接覆盖
//evict没有用到,只是提供了一个扩展afterNodeInsertion(evict)供子类覆盖
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table为空,或者长度为0,则调用resize方法进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//这里n为2的n次幂,根据hash值计算角标,如果该角标对应的节点为空,则创建一个新节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//该节点不为空
Node<K,V> e; K k;
//如果key和hash值都相等,则直接跳到最后if(e!=null),根据onlyIfAbsent参数来判断是否覆盖节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//如果节点是TreeNode，则按照红黑树进行添加
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果链表上未存在相同的key,则一直往下移动直到p.next=null,然后将新节点做为p的next节点。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 如果迭代次数大于等于红黑树的临界值,则转成红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//即p = p.next,一直往下迭代
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//超过容量进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3.resize扩容机制
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {//如果table容量超过最大容量值,则直接设置int的最大值作为临界值
threshold = Integer.MAX_VALUE;
return oldTab;
}
//table扩大为原来的两倍,如果扩容后的table长度>=16且小于MAXIMUM_CAPACITY,则临界值也扩大到原来的两倍.
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 如果老的临界值大于0,则将容量设置为和临界值一样(第一次扩容)
newCap = oldThr;
else { //针对没有设置初始化值的情况(第一次调用put),设置初始容量和临界值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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<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;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
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;
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;
}
真正的核心在下面的for循环，循环oldCap次。依次获取table的角标,如果角标不为空,则判读e.next是否为空,如果为空,则直接设置newTab[e.hash & (newCap - 1)] = e.如果节点是TreeNode,则按照红黑树进行扩容.如果不是红黑树,则通过下面的do while赋值到新的Node数组上去。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//获取e的next节点
next = e.next;
//hash为0或者容量为0
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不为空,则直接拼接到尾部
hiTail = e;
}
} while ((e = next) != null);//循环迭代取下一个节点
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
f (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
4.get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
根据key计算出hash值,再通过getNode获取节点内容.
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;
}
根据(n - 1) & hash计算角标值,根据角标值获取Node,判断该节点的hash值、key和传入的key,hash是否相等,如果相等则直接返回该节点。否则就通过first.next获取下一个节点,如果下一个节点是TreeNode，则通过getTreeNode获取红黑树节点信息。如果不是红黑树节点,则通过do while循环获取下一个节点直到key和hash值和传入的key,hash相等为止,如果存在这样的节点,则返回该,否则返回null.
结束语
今天只是分析了一下JDK1.8 HashMap的put和get方法,以及基本的扩容机制,下次再分析它的红黑树机制。
网友评论