JDK1.8源码分析之HashMap JDK1.8源码分析之HashMap

前言 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[] table; transient Set> entrySet; transient int size; transient int modCount; final float loadFactor;

从成员变量可以看出JDK1.8针对某个临界变量做了红黑树的转换,为了满足红黑树结构则是需要有最小容量要求的。HashMap的初始容量是2的n次幂,方便利用移位运算进行定位角标。
Node结构

static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = https://www.it610.com/article/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 extends LinkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); }/** * 获取根节点 */ final TreeNode root() {}/** * 使根节点作为第一个节点 */ static void moveRootToFront(Node[] tab, TreeNode root) {}/** *查找对应节点 */ final TreeNode find(int h, Object k, Class kc) {}/** * 获取节点数据 */ final TreeNode getTreeNode(int h, Object k) {}static int tieBreakOrder(Object a, Object b) {}final void treeify(Node[] tab) {}final Node untreeify(HashMap map) {}final TreeNode putTreeVal(HashMap map, Node[] tab, int h, K k, V v) {}final void removeTreeNode(HashMap map, Node[] tab, boolean movable) {}final void split(HashMap map, Node[] tab, int index, int bit) {}static TreeNode rotateLeft(TreeNode root,TreeNode p) {}static TreeNode rotateRight(TreeNode root,TreeNode p) {}static TreeNode balanceInsertion(TreeNode root,TreeNode x) {}static TreeNode balanceDeletion(TreeNode root,TreeNode x) {}static boolean checkInvariants(TreeNode 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源码分析之HashMap】但是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[] tab; Node 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 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)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 = https://www.it610.com/article/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[] resize() { Node[] 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[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node 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)e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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 loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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 e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

根据key计算出hash值,再通过getNode获取节点内容.

final Node getNode(int hash, Object key) { Node[] tab; Node 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)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方法,以及基本的扩容机制,下次再分析它的红黑树机制。