Java 源码--HashMap
HashMap结构
HashMap采用数组+链表+红黑树的存储结构。当一个键值对要存储到HashMap中时，HashMap会根据它的键值的哈希值映射到数组的某个位置。如果发生了哈希碰撞，就以链表的形式接在碰撞元素的后边。当链表过长时，就会转变为红黑树。
下边我们就先来看下链表和红黑树的数据结构。
链表
内部类Node定义了链表的每个结点的结构，它记录结点的hash、key、value和下一个结点next。
final int hash;
final K key;
V value;
Node<K,V> next;
红黑树
内部类TreeNode定义了红黑树每个结点的结构，每个结点都保存了父结点、左结点、右结点、颜色以及一个在删除时需要解除连接的（其实这个我也不知道是干啥的）。
TreeNode<K,V> parent; // 父结点
TreeNode<K,V> left; // 左结点
TreeNode<K,V> right; // 右结点
TreeNode<K,V> prev; // 前一个结点
boolean red; // 是否是红色
结构实现细节
首先来看下HashMap中的变量。
transient Node<K,V>[] table; // table存储HashMap中数组的元素
transient Set<Map.Entry<K,V>> entrySet; // 遍历的入口，可以获取到key和value
transient int size; // HashMap的已存储元素的个数
transient int modCount; // 被修改的次数
int threshold; // 扩容的阈值
final float loadFactor; // 装载因子
size是HashMap中已经存储的元素的个数，它并不等于table的长度，也不等于table中已存储的元素的个数。如下图的HashMap，它的size大小是14。
HashMap的扩容机制并不像ArrayList等，在容量不够用时才会扩容。HashMap在容量达到某个百分比时就会开始扩容，这个百分比就是loadFactor，threshold就是对应这个百分比的容量，即capacity * loadFactor。HashMap中将loadFactor的默认值设为0.75f。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
我们大概了解到，链表达到某个长度会转变为红黑树。HashMap中定义了这个长度的阈值为8。
static final int TREEIFY_THRESHOLD = 8;
当红黑树的结点数小于某个值时，又会变为链表，HashMap将其设定为6。
static final int UNTREEIFY_THRESHOLD = 6;
如果数组的长度太小，会造成哈希碰撞频繁，链表结构臃肿，所以HashMap定义了阈值，当HashMap的容量小于这个值时，优先去扩容减小哈希碰撞，而不是去优化链表的结构。
static final int MIN_TREEIFY_CAPACITY = 64;
构造方法
HashMap的初始容量和装载因子可以由开发者设定，也可以使用HashMap提供的默认值。对应的构造方法有三种。还可以根据一个Map来构造一个HashMap。
-
指定容量和装载因子。
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); }首先指定的容量不能超过最大容量，HashMap对最大容量的设定为2^30。
static final int MAXIMUM_CAPACITY = 1 << 30;当指定容量不超过最大容量时，也需要对指定容量进行处理，使之成为2的倍数，我们首先来看一下如何取得一个数的2的倍数，并且这个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; }n = 100 0000 0000 0000 0000 0000 0000 0000。
第一步： n |= n >>> 1
第二步：n |= n >>> 2
第三步：n |= n >>> 4
第四步：n |= n >>> 8
第五步：n >>> 16
可以看出，这个方法的操作相当于，从最高位1开始，低位都填充1。
弄清楚了这几个位移的操作就不难理解这个方法了，首先将参数减1，最后再加1。有效位都是1的数加1就是2的倍数。如果指定容量已经是2的倍数，先减1再位移可避免再扩大2倍。
-
指定容量
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }指定容量时使用默认装载因子。
-
不指定容量和装载因子
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; }无参构造时，使用默认装载因子，不设定容量大小。
-
根据Map构造
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }根据Map构造HashMap时，使用默认装载因子。然后将map中的值放入。
常用方法
- 增
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<K,V>[] tab; Node<K,V> p; int n, i;
// 数组为空或者长度为0先扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1)&hash计算出应放置在数组中的位置
// 如果数组的对应位置上没有元素，就直接放在数组中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 发生哈希碰撞
else {
Node<K,V> e; K k;
// 先判断一下hash是否相等，再判断key是否相等，相等就替换
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
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)
treeifyBin(tab, hash);
break;
}
// 有相同的key就替换旧值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 赋新值并返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 修改次数加1
++modCount;
// 达到容量阈值就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
看到(n - 1)&hash，我们一定会有疑问，为什么这个计算就可以获取到值应该放置的位置呢？
根据之前我们的分析，我们知道n - 1的每一个有效位都为1，那么与操作就可以拿到hash的二进制中n - 1的有效位的值，即hash % (n - 1)的值。这就是二进制0和1的魅力呀。比如n = 32，hash = 1010011001：
-
查
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) { 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) { // 数组中元素的value是我们要的 if (first.hash == hash && ((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; } -
删
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { 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)))) 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); } } // 到此为止如果要删除的元素存在，就已经拿到了结点 // 要删除的结点不为空并且判断需不需要判断传入value和要删除的结点value的相等 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; // 修改次数加1 ++modCount; // 大小减1 --size; afterNodeRemoval(node); return node; } } return null; }
JDK 8 新增方法
-
getOrDefault(Object key, V defaultValue)
获取key的值，当key的值为null时返回指定的defaultValue。
-
putIfAbsent(K key, V value)
当key的值为null或者不存在key时向HashMap中添加元素。
-
remove(Object key, Object value)
当指定的key和value都正确时才将其移除掉。
-
replace(K key, V oldValue, V newValue)
如果指定的key和oldValue正确就用newValue替换掉oldValue。
-
replace(K key, V value)
key存在的话直接将值替换为value。
-
computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
如果key的值为null或者不存在就使用指定函数执行key，并将返回值设为对应的值。
-
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
如果存在就使用指定函数执行key和oldValue，并将返回值设为新值。
-
merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)
如果key对应的值不为空，就使用指定函数执行oldValue和value，并将返回值设为新值。
-
forEach(BiConsumer<? super K, ? super V> action)
对每一个元素都执行指定操作。
-
replaceAll(BiFunction<? super K, ? super V, ? extends V> function)
将每个元素都替换为执行函数之后的返回值。
扩容机制
resize方法对HashMap进行扩容，我们来分析此方法就可以了解到HashMap的扩容机制。
final Node<K,V>[] resize() {
// 原来的数组
Node<K,V>[] oldTab = table;
// 原来的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 原来的扩容阈值
int oldThr = threshold;
// 新的容量和阈值
int newCap, newThr = 0;
// 原来的容量大于0
if (oldCap > 0) {
// 如果原来的容量大于等于最大容量，就将扩容阈值设为Integer的最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果原来的容量的2倍不超过HashMap的最大容量，并且原来的容量大于HashMap的默认初始容量
// 就将扩容阈值扩大两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
// 原来的容量为0，但是原来的扩容阈值大于0
else if (oldThr > 0)
// 将新的容量设为原来的扩容阈值
newCap = oldThr;
// 原来的容量和扩容阈值都为0
else {
// 新的容量设为默认初始容量，新的扩容阈值设为默认装载因子*默认初始容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新的扩容阈值为0
if (newThr == 0) {
// 计算扩容阈值
float ft = (float)newCap * loadFactor;
// 如果新的容量小于最大容量并且新容量对应的扩容阈值小于最大容量
// 就将新的扩容设为ft，否则就将新的扩容阈值设为Integer的最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
// 设置扩容阈值
threshold = newThr;
// 申请一个新的table
@SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果原来的数组中有元素，就将原来的HashMap中的元素移到新的数组中
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 {
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;
}
总的来说，有以下几种情况：
-
当目前容量大于等于最大容量时，扩容阈值设为整型最大值。
-
当当前容量不超过最大容量且扩大2倍之后也不超过最大容量时，扩容至2倍，新的扩容阈值扩大至2倍。
-
当当前容量不超过最大容量但是扩大2倍之后会超过最大容量时，扩容至2倍，就将扩容阈值设为整型最大值。
-
当当前容量为0且当前扩容阈值大于0时，扩容至原来阈值大小，阈值变为新容量乘以装载因子。
-
当当前容量和扩容阈值都等于0时，容量设为默认初始容量大小，阈值设为默认容量乘以默认装载因子，
总结
总的来说，HashMap就是围绕数组+链表+红黑树的结构展开的。关于红黑树的具体细节，会在另一篇博客中展开分析。