JDK8源码阅读（四）：HashMap
程序员文章站
2022-06-17 10:27:41
...
1.是什么
是通过K-V键值对来保存数据的数据结构，K和V都可以为null。
继承关系如下图所示：
数据结构如下图所示：
2.构造函数和主要属性
- 加载因子loadFactor非常重要，这个决定了什么时候进行数组的扩容操作
- 每次扩容时，都扩容为原来数组长度的2倍
// 存放数据的数组默认初始大小为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 默认的加载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表变形为红黑树时，链表的长度
static final int TREEIFY_THRESHOLD = 8;
// 红黑树变形为链表时，红黑树节点个数
static final int UNTREEIFY_THRESHOLD = 6;
// 当hashmap中元素达到64时，才会让链表变形为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组
transient Node<K,V>[] table;
// hashmap中元素的个数
transient int size;
// 加载因子
final float loadFactor;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
int threshold;
static final int MAXIMUM_CAPACITY = 1 << 30;
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<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
2.1 这里着重讲一下带有初始容量时的代码
当在创建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);
}
但是这个时候还没有初始化存放数据的数组，而是在第一次 put 时，才会去初始化存放数据的数组。
如下图所示：
- 第一次执行resize()方法，oldTab 是 null，所以 oldCap = 0
- 然后就会执行图中红框的方法，初始化新的数组容量为
oldThr，也就是threhold
下面这段代码是在JDK1.7以后的实现
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
- 第一行代码
int n = cap - 1;是因为当cap的值为2x时，如果cap不减1的话n的值会为2x+1，所以我们需要先将cap的值减一。 - 然后再算出一个2的次方的值，这个值为最接近并大于cap的值。例如5最近的2的次方的值为23（8），29的最近的2的次方的值为25（32）。
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
为什么上面算法能实现找到大于n的最小的2的次方的值呢？
因为当我们把n无符号右移1位后做或操作，那么一个1就会变为两个1，再右移2位，两个1就变为4个，依次类推，到最后右移16位就会将n的二进制的最高位的1的后面位置全部变为1。
然后最后return 返回的时候，再对n进行加1操作，使得返回值是一个大于n的最小的2的次方的一个值。也就是把n的二进制表示的值的最高位的1前面变为1，然后新的最高位后面的全部变为0。
例如：
17 ==> 0001 0001n |= n >>> 1：0001 0001 | 0000 1000 ==> 0001 1001n |= n >>> 2：0001 1001 | 0000 0110 ==> 0001 1111
因为最高位1后面已经全部是1了，所以后面的无符号右移4位、8位和16位后或的结果也为0001 1111。
然后末尾+1就等于0010 0000，也就是大于17的最小的2的次方的值32
3.新增元素
在调用put()方法时，主要有2种情况：
- 该key不在hashmap中存在，则新增一个元素，并判断hashmap是否需要扩容，最后返回null
- 该key已经存在于hashmap中，则替换掉原来的value为新值，最后返回key对应的旧value值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 当key为null时，hash值为0，否则hash值为key的hashcode与hashcode高16位进行异或，减少hash冲突。
// 在《码出高效：Java开发手册》一书中对这个算法进行了说明：“将高位与低位进行异或 有助于泊松分布。”
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1.当数组为null或者数组长度为0时，进行扩容操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.当所在位置为null时，直接在该位置放入元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 判断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 {
// binCount是为了统计链表的长度
for (int binCount = 0; ; ++binCount) {
// 找到了链表的末尾，说明key不存在
if ((e = p.next) == null) {
// 将新增的元素添加到链表的末尾
p.next = newNode(hash, key, value, null);
// 判断是否需要将该链表转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 在这个方法里，不会直接将链表转为红黑树，而是还会判断table数组的长度，
// 如果大于64，才会将链表转为红黑树，否则会进行resize()扩容操作。
treeifyBin(tab, hash);
break;
}
// 如果是在链表中间找到了，说明key已经存在
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e不为空，说明是修改key所映射的value值，而不是新增的key-value键值对
if (e != null) { // existing mapping for key
V oldValue = e.value;
// put方法默认onlyIfAbsent为false，即如果旧值不为null，就返回旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 是LinkedHashMap实现的方法，在HashMap中为一个空方法
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 元素新增成功后，判断元素个数（包括刚刚新增的元素）是否大于 数组长度 * 加载因子，大于则进行扩容操作
if (++size > threshold)
resize();
// 是LinkedHashMap实现的方法，在HashMap中为一个空方法
afterNodeInsertion(evict);
return null;
}
4.移除元素
若key不存在，则返回null
若key存在，则移除key对应的元素，并返回key所对应的value值
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);
}
}
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;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}