前面讲过 ArrayList 和 LinkedList, 它们都是 List 类型, 对于 List 集合来说, 它存储的元素除了有先后顺序关系外, 不会在这个集合中表示出其他的联系. 本文要讲的 HashMap 是 Map 类型, 它同时存储 key 和 value 两个元素, 并且 key 和 value 之间是一一对应的. 换句话说, Map 不光存储数据, 并且存储数据的映射关系.
对于 HashMap 来说, 其基本特性如下:
基本特性 | 结论 |
---|---|
元素是否允许为 null | key 和 value 可以为 null |
元素是否允许重复 | key 重复会覆盖,value 可以重复 |
是否有序 | 否 |
是否线程安全 | 否 |
源码分析
本文使用的是 JDK 1.8.0_201 的源码.
成员变量
HashMap 在 JDK 1.7 时基于数组 + 链表实现, 在 JDK 1.8 时作了优化, 变成了数组 + 链表 + 红黑树实现. 我们来看下 JDK 1.8 下 HashMap 的成员变量:
成员变量 | 作用 |
---|---|
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; | 底层数组的默认大小为 16,这个数字必须为 2 的次方 |
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; | 由链表转为红黑树,底层数组的最小长度 |
transient Node<K,V>[] table; | 底层数组 |
transient Set<Map.Entry<K,V>> entrySet; | entrySet 缓存 |
transient int size; | 实际存储的元素个数 |
int threshold; | 需要进行 resiz 时 size 的大小,即 capacity * load factor |
final float loadFactor; | 负载因子,默认为 0.75 |
HashMap 的源码明显比 ArrayList 和 LinkedList 要复杂.
put()操作
put 操作的大致思路为:
对 key 的 hashCode()做 hash 处理, 然后再通过求模计算 bucket 的下标;
如果没有产生 hash 碰撞, 直接放入 bucket 中;
如果产生碰撞, 以链表的形式追加到桶后面;
如果链表的长度过长(即大于等于 TREEIFY_THRESHOLD), 就把链表转为红黑树;
如果节点已经存在就替换 old value(保证 key 的唯一性);
如果该 map 中的元素个数超过阈值 threshold(即 capacity * load factor), 就 resize
- public V put(K key, V value) {
- // 对 key 的 hashCode()做 hash 处理
- 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;
- // table 为空则创建
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- // 计算桶的下标(等同于 % 求模运算), 并判断该桶是否为 null, 即判断是否产生 hash 碰撞, 如果该桶为 null 则创建一个桶
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- // 如果该桶不为 null, 即 hash 碰撞, 则需要根据情况进行处理
- else {
- Node<K,V> 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<K,V>)p).putTreeVal(this, tab, hash, key, value);
- // 第三种情况, 需要往桶中添加一个链表节点
- else {
- // 遍历桶中的元素, 为添加的元素寻找位置, 注意这里的时间复杂度为 O(n)
- 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 = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- // 超过负载阈值, resize
- if (++size> threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
get()操作
有了前面 put 操作的基础, 再看 get 操作就容易多了. 大致思路如下:
先检查 map 以及根据 hash 求模的桶是否有数据, 如果没有数据, 直接返回 null;
判断是否命中该桶第一个元素, 是则直接返回第一个元素 value;
判断该桶的元素是否为红黑树, 如果是则调用红黑树的方法获取 value;
如果是普通节点, 遍历节点元素, 匹配就返回 value, 否则返回 null.
- 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;
- // 先检查该 map 是否有数据, 以及根据 hash 求模的桶是否有数据, 如果没有数据则直接返回 null
- if ((tab = table) != null && (n = tab.length)> 0 &&
- (first = tab[(n - 1) & hash]) != null) {
- // 若命中桶的第一个元素, 直接返回第一个元素 value
- 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<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;
- }
hash()方法的实现
在 put()和 get()操作时, 都对 key 做了 hash 操作. 先看下源码:
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
这个方法的作用是: 对 key 的 hashCode 值做计算, 让其高 16 位不变, 低 16 位与高 16 位进行异或计算. 代码非常简单, 但是其背后的设计思想并不是那么简单.
HashMap 其底层数组 table[]的长度一定是 2 的幂次方, 在根据 hash 值计算 table 下标时, 可以用 (n - 1) & hash 的方式代替求模 % 运算. 这么做提高了计算 table 下标的效率, 却容易导致 hash 碰撞. 比如, n - 1 为 15(0x1111)时, hash 真正有效的只是低 4 位, 当然容易发生碰撞.
为了解决上面的碰撞, 设计者将 hashCode 的低 16 位异或高 16 位. 那么为什么不多异或几次呢? 这里考虑到了综合性能, 因为现在很多类的 hashCode 实现得很好, 原本就很分散, 多几次异或操作作用不大. 另一方面, 对于冲突较多的情形, 使用树来解决频繁的碰撞. 仅异或一次, 既减少了系统的开销, 也不会造成的因为高位没有参与下标的计算(table 长度比较小时), 从而引起的碰撞.
在 JDK 1.8 之前, HashMap 是用链表实现的, 在产生碰撞的情况下, get 操作的时间复杂度为 O(n), 因此当碰撞很厉害, n 非常大的时候, O(n)的效率是不够好的.
因此 JDK 1.8 采用红黑树代替链表, 这样 get 操作的时间复杂度变为了 O(log n) , 在 n 非常大的时候, 能够明显的提高效率. 在 《Java 8:HashMap 的性能提升》 http://www.importnew.com/14417.html 一文中有相关的性能测试结果.
resize()操作
当添加元素时, 比如 put 操作, 如果 map 的元素个数大于阈值(即 size> threshold), 就会触发 resize.resize 操作会将 map 的容量扩大为原先的 2 倍, 而每个元素的桶下标要是不变, 要么移动 2 的幂次方.
原理在于, 计算桶下标的方法是:
(n - 1) & hash
现在 n 为原先的 2 倍, 比如原先 n 为 16, 那么 (n - 1) 即 15(0x1111), 现在 n 为 32,(n - 1)即为 31(0x11111). 原先有效的 hash 位是 4 位, 现在变成了 5 位. 所以, hash 位第 5 位是 0 的元素, 仍然在原先的桶中, 而 hash 位第 5 位是 1 的元素, 将移动 2 的幂次方.
总结
为了加深对 HashMap 的理解, 总结了以下几个问题:
1. 什么时候会使用 HashMap? 他有什么特点?
HashMap 是基于 Map 接口的实现, 存储键值对时, 它可以接收 null 的键值, 是非同步的, HashMap 存储着 Entry(hash, key, value, next)对象.
2. 你知道 HashMap 的工作原理吗?
HashMap 通过 put 和 get 存储和获取对象. 存储对象时, 我们将 K/V 传给 put 方法时, 它调用 hashCode 计算 hash 从而得到 bucket 位置, 进一步存储, HashMap 会根据当前 size 的大小自动调整容量 (超过 Load Facotr 则 resize 为原来的 2 倍). 获取对象时, 我们将 K 传给 get, 它调用 hashCode 计算 hash 从而得到 bucket 位置, 并进一步调用 equals() 方法确定键值对. 如果发生碰撞的时候, Hashmap 通过链表将产生碰撞冲突的元素组织起来, 在 Java 8 中, 如果一个 bucket 中碰撞冲突的元素超过某个限制(默认是 8), 则使用红黑树来替换链表, 从而提高速度.
3. 你知道 get 和 put 的原理吗? equals()和 hashCode()的都有什么作用?
通过对 key 的 hashCode()进行 hashing, 并通过 ( n-1 & hash) 求模的方式计算下标, 从而获得 buckets 的位置. 如果产生碰撞, 则利用 key.equals()方法去链表或树中去查找对应的节点.
4. 你知道 hash 的实现吗? 为什么要这样实现?
在 Java 1.8 的实现中, 是通过 hashCode()的高 16 位异或低 16 位实现的:(h = k.hashCode()) ^ (h>>> 16), 主要是从速度, 功效, 质量来考虑的, 这么做可以在 bucket 的 n 比较小的时候, 也能保证考虑到高低 bit 都参与到 hash 的计算中, 同时不会有太大的开销.
5. 如果 HashMap 的大小超过了负载因子 (load factor) 定义的容量, 怎么办?
如果超过了负载因子(默认 0.75), 则会重新 resize 一个原来长度两倍的 HashMap. 元素要么仍然在之前的 bucket 中, 要么移动 2 的幂次方.
参考资料
《Java HashMap 工作原理及实现》
《Java 8:HashMap 的性能提升》 http://www.importnew.com/14417.html
来源: http://www.bubuko.com/infodetail-3024655.html