java源码赏析--java.util.HashMap java源码赏析--java.util.HashMap

我们都知道Java最基本的数据结构有数组和链表。
数组的特点：空间连续、寻址快、插入和删除时需要移动元素会很慢。
链表的特点：动态增加或减少空间以适应新增和删除元素，但查找时只能顺着一个个节点查找。
而哈希表却能将两者的优点相综合。
JDK1.6 中 HashMap 采用的是位桶+链表的方式，即我们常说的散列链表的方式；JDK1.8中采用的是位桶+链表/红黑树的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。
如果对红黑树不是很了解的同学，请先移步熟悉红黑树。
1. 数据结构 HashMap的底层是哈希数组，通过key的hashCode来计算hash值，当hashCode冲突时，通过“拉链法”解决冲突：

文章图片
如果当冲突很多时，链表长度变长，会造成搜索时间变长，因此JDK1.8之后，当链表长度大于阈值8之后，会将链表变成红黑树。
链表结构：

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() { return Objects.hashCode(key) ^ Objects.hashCode(value); }public final V setValue(V newValue) { V oldValue = https://www.it610.com/article/value; value = newValue; return oldValue; }public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

红黑树结构：

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); } }

2. 各常量、成员变量作用

//创建 HashMap 时未指定初始容量情况下的默认容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//HashMap 的最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //装载因子，当 HashMap 中元素数量超过容量*装载因子时，进行　resize()　操作 static final float DEFAULT_LOAD_FACTOR = 0.75f; //用来确定何时将解决 hash 冲突的链表转变为红黑树 static final int TREEIFY_THRESHOLD = 8; // 用来确定何时将解决 hash 冲突的红黑树转变为链表 static final int UNTREEIFY_THRESHOLD = 6; /* 当需要将解决 hash 冲突的链表转变为红黑树时，需要判断下此时数组容量，若是由于数组容量太小（小于　MIN_TREEIFY_CAPACITY　）导致的 hash 冲突太多，则不进行链表转变为红黑树操作，转为利用　resize() 函数对　hashMap 扩容　*/ static final int MIN_TREEIFY_CAPACITY = 64;

// 存储元素(位桶)的数组 transient Node[] table; // 记录 hashMap 当前存储的元素的数量 transient int size; // 结构改变次数，fast-fail机制 transient int modCount; // 新的扩容resize临界值,当实际大小(容量*装载因子)大于临界值时，会进行扩容 int threshold; // hashMap 装载因子 final float loadFactor;

这里着重说一下装载因子，默认值为0.75，如果实际元素所占容量占分配容量的75%时就要扩容了。如果装载因子很大，说明利用的空间很多，但是查找的效率很低，因为链表的长度很大（当然最新版本使用了红黑树后会改进很多），HashMap本来是以空间换时间，所以装载因子没必要太大。但是装载因子太小又会导致空间浪费。如果关注内存，填充比可以稍大，如果主要关注查找性能，填充比可以稍小。
3. 构造方法 HashMap一共有4个构造方法，主要区别在于设置初始容量与装载因子上。

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 }public HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

我们看一下tableSizeFor方法，是用来计算下次需要调整大小的扩容resize临界值 thresold。
此方法将返回(>=cap)的最小2的自然数幂，非常精妙的通过无符号右移的策略来完成，可以值得借鉴。
但是，为什么必须是2的幂呢？我们留下悬念。

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; }

4. 主要方法 4.1 V get(Object key)

public V get(Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

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; }

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

用 key 通过hash方法算出来对应的hash值。
元素所在位桶的位置为 tab[(n - 1) & hash] ，即求余运算。
首先判断位桶位置的 Node 第一个元素，如果hash值相等并且 key相等(或都等于null)，则直接返回。
hash值相等，但 key 不相等，说明出现冲突。需要判断 Node 是链表还是红黑树，并从中取值。

hash方法为何如此计算，我们继续留下悬念！
4.2 V put(K key, V value)

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)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); 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 = 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; }

如果位桶为空，则通过resize()方法生成。
根据hash获取位桶对应位置的 Node 元素，如果为空，则创建并设置到位桶中。
如果hash与Node的相等，且key值也与Node的相等，即找到元素。
否则说明有冲突，需要往链表或者红黑树中寻找插值。
如果向链表中插值时，链表长度 >= TREEIFY_THRESHOLD，则需要通过treeifyBin方法将链表转红黑树。
【java源码赏析--java.util.HashMap】最后检查容量是否达到临界值，否则进行扩容。
切记，返回oldValue。

4.3 Node[] resize()
resize() 方法中比较重要的是链表和红黑树的 rehash 操作，先来说下 rehash 的实现原理：
我们在扩容的时候，一般是把长度扩为原来2倍，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。如图：
n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的计算示例，图（b）表示扩容后key1和key2两种key确定索引位置的计算示例，其中hash1是key1对应的哈希与高位运算结果。

文章图片
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

文章图片
因此，我们在扩充HashMap的时候，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

文章图片
代码中非常巧妙的用了(e.hash & oldCap) == 0来判断。oldCap仅仅高位为1，其余位为0。因此相&为0说明e.hash最高位为0，否则为1。

final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; //设置旧容量、旧阈值，有可能都是0 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) {扩容两倍没有超过最大容量且旧容量 >= 16 newThr = oldThr << 1; // double threshold } } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 使用旧阈值设置新容量 else {// zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; //如果旧容量、旧阈值都为0，则使用默认值 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) {// 如果新阀值为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)//红黑树重新rehash ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order //链表重新rehash // 一个桶中有多个元素，遍历将它们移到新的bucket或原bucket Node loHead = null, loTail = null; //lo原bucket的链表指针 Node hiHead = null, hiTail = null; //hi新bucket的链表指针 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; }

总结：

无需重新计算Hash，节省了时间；
由于所计算的hash(key)位是1是0可以认为是随机的，所以将一个冲突长链表又“均分”成了两个链表，减少碰撞与检索时间。

5. 悬念 5.1 为什么容量必须是2的幂次方？
我们在resize()方法中知道获取 bucketIndex 是通过 tab[(length - 1) & hash]来获取，由于hash我们可以认为是随机的，而 (length - 1) 可以保证最后一位为1(二进制表示),从而保证了 bucketIndex的最后一位同时有为0和为1的可能性，保证了散列的均匀性。反过来讲，若 length 为奇数，length-1 最后一位为0，这样与h按位与(同1为1)的最后一位肯定为0，即索引位置肯定是偶数，这样数组的奇数位置全部没有放置元素，浪费了大量空间。
总而言之：
length为2的幂保证了按位与最后一位的有效性，使哈希表散列更均匀。
5.2 hash方法为何如此计算？
我们知道，使用散列的容器，其高性能的主要影响因素之一就是hash值。
在HashMap中，为了更好的性能，我们希望作为Key的对象提供一个合理的hash函数以便能将其合理的分配到桶中。

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

按位异或就是把两个数按二进制，相同就取0，不同就取1。
比如：0101 ^ 1110 的结果为 1011。
无符号右移16位，高16位补0，丢弃掉低16位，那么也就是说小于2^16的数字右移16位后结果为0。
所以，任何一个数，与0按位异或的结果都是这个数本身。
所以这个 hash() 函数对于非null的hash值，仅在其大于等于2^16的时候才会重新调整其值。
有什么好处吗？
我们知道获取 bucketIndex 是通过 tab[(length - 1) & hash]来获取。我们以默认容量16为例。
此时 size-1 =15的二进制为 1111 ，也就是任意二进制最后四位为0000的hash值，都会被存储到位置为0的桶位上，一个桶中的元素太多，就一定会降低其性能，即使使用了红黑树。
而正是由于将大于等于2^16的hash值，将他们的高16位与低16位异或，才能变成另外的值，避免了装到同一桶内。