特点
-
根据键的 hashCode 值存储数据
-
遍历顺序不确定
-
允许 key 和 value 为 null
-
非线程安全。如果需要满足线程安全，可以用 Collections.synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap
存储结构
-
JDK 7 中的 HashMap 采用数组 + 链表的结构来存储数据
-
JDK 8 中的 HashMap 采用数组+链表或树的结构存储数据
HashMap存储结构.png
核心属性
table
transient Node<K,V>[] table;
这是 HashMap 的核心，HashMap 内部实际上是一个 Node 数组，这个数组的大小必须是 2 的幂次方。
再看 Node 的实现：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
可见，Node 实际上是单链表结构，即 HashMap 中是用单链表结构的数组来存储数据。
需要注意的是，在 JDK1.8 之后，如果单链表长度大于等于 8 ，则把单链表转换为红黑树结构。
size
transient int size;
key-value 键值对的数量，这里不是 table 数组的大小
capacity
table 数组的 length，默认是 16，这里需要注意的是，capacity 的值必须是 2 的幂次方。
loadFactor
table 能使用的比例，默认是 0.75。
当负载因子 loadFactor 增大时，每个链表所能容纳的键值对个数越多，遍历链表的时间也就越长，查询、插入等速度也就越慢，适应于内存空间较少且而时间效率要求不高的场景；
相反，当负载因子减少时，每个链表所能容纳的键值对个数越少，操作 map 的时间较快，但需要增加 table 的长度，所以需要更多的内存，适应于内存空间很多而对时间效率很高的场景；
默认值是对空间和时间效率的一个平衡选择，一般不需要修改。
threshold
int threshold;
size 需要扩容的临界值，当 size 大于等于 threshold 时，就需要进行扩容操作。
扩容后的 HashMap 容量是之前容量的两倍。
threshold = capacity * loadFactory
其中，影响 HashMap 的性能主要有两个因素：initial capacity 和 loadFactory。
方法
put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/*
* hash：key 的 hash 值
* onlyIfAbsent：如果为 true 的话，存在 value 的话不进行修改
* evict：在 HashMap 中没有意义
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n,i;
// 这里只有在第一次调用 put 方法时可能会触发
if ((tab = table) == null || (n == tab.length) == 0)
n = (tab - resize()).length;
// 根据 key 的 hash 值找到具体位置，如果这个位置没有值，初始化一个 Node
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);
// 执行到这里说明该节点属于单链表，且第一个节点 key 不相等
else {
for (int binCount = 0; ; ++binCount) {
// 循环到链表的最后，插入该值
// 在 JDK 1.8中是插入到链表的最后，JDK 1.7中是插入到最前面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD = 8
// 如果新插入的值位于链表的第 8 个，则将链表转换为红黑树结构
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifBin(tab, hash);
break;
}
// 如果链表中的某个节点的 key 与要插入的 key 相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 如果没有满足上面的条件，则把下一个节点赋给当前节点，下一次循环时再获取下一个节点
p = e;
}
}
// 如果 e 不为 null 的话，则说明与 key 相等的 节点
if (e != null) { // existing mapping for key
// 获取这个 key 之前的 value
V oldValue = e.value;
// onlyIfAbsent 为 true 的话，就不要改变已有的值
// 则这里如果 onlyIfAbsent 为 false，或 value 是 null，则将新值替换老的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// HashMap 中不进行操作
afterNodeAccess(e);
// 进行覆盖操作时，直接返回之前的值，说明修改值时 modCount 不修改
return oldValue;
}
}
// 如果是新增值时，需要增加 modCount变量，为迭代器服务
++modCount;
// 如果数组长度大于 threshold 阈值
if (++size > threshold)
// 重新散列
resize();
// HashMap 中什么都不做
afterNodeInsertion(evict);
// 新增值返回 null
return null;
}
put 函数大致可以分以下几步：
- 如果 table 为 null，则调用 resize() 初始化，默认是创建长度为 16 的数组；
- 通过与运算计算对应 hash 值的下标，如果对应下标的位置没有元素，则直接创建一个；
- 如果有元素，则说明该 hash 值已经有对应的节点，则再进行判断：
- 判断两个冲突的 key 是否相等，，如果相等的话，则到最后执行该节点的替换操作；
- 如果 key 不相等，再判断该节点是否为红黑树，如果是的话，则交给红黑树添加此元素；
- 如果只是普通链表的话，则遍历链表，判断是否有与给定 key 相等的节点，如果有的话，跳出循环，在后面执行该节点的更新操作，否则在最后添加一个节点，并且判断链表的长度是否已经大于等于 8，满足条件的话，则将链表改为红黑树。
- 最后，如果存在该 key 的节点，则执行更新操作
- 最后判断当前数组的长度是否已经大于阈值，如果大于则 rehash()
resize
resize() 方法用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果之前 table 的长度不为 0，则进行扩容
if (oldCap > 0) {
// 如果 table 长度超出最大值，则不扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 长度允许的情况进行扩容2倍
newThr = oldThr << 1;
} else if (oldThr > 0)
// 这里主要是调用 new HashMap(int initialCapacity) 初始化后，第一次进行初始化的时候
newCap = oldThr;
else {
// 对应调用 new HashMap() 初始化后，第一次进行初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 这里只要调用 new HashMap(int initialCapacity) 初始化，执行这里
// 主要为了校验，newCap 是否超出最大值，且 newCap * loadFactor 是否超出最大值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
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)
// e.hash & (newCap - 1) 确定元素所位于的桶下标
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;
}
} 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;
}
经过 resize 后，元素的位置要么是在原位置，要么是在原位置再移动 2次幂的位置，即原位置 + oldCap
get
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;
// 判断 table 是否为空，如果为空则返回 null，如果不为空，根据 hash 获得桶下标
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断该下标的桶第一个节点是否与当前 key 相等
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);
// 如果该节点属于单链表，则循环该链表，获得与该 key 相等的节点
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get函数可以分为下面几步：
- 根据 key 的 hash 值找到桶所在的下标：
hash & (length - 1) - 判断该位置的第一个元素是否是要寻找的元素，如果是，则返回
- 判断该元素类型是否是 TreeNode，如果是，用红黑树的方式取数据
- 遍历链表，直到找到相等的 key
小结
- HashMap 线程不安全，如果需要在并发的情况下同时操作，建议使用 ConcurrentHashMap。
- 负载因子默认是0.75，可以修改，并且可以大于 1，当设置其值较大时，时间效率低而空间效率高，反之则时间效率高而空间效率低，但是建议一般不要轻易修改，除非情况非常特殊。
- 扩容是一个特别消耗性能的操作，所以在使用 HashMap 的时候，估算 map 的大小，初始化的时候给一个大致的数值，避免 map 进行频繁的扩容。
- JDK1.8 中引入了红黑树，大程序优化了 HashMap 的性能。
网友评论