一, 前言
HashMap 顾名思义, 就是用 hash 表的原理实现的 Map 接口容器对象, 那什么又是 hash 表呢.
我们对数组都很熟悉, 数组是一个占用连续内存的数据结构, 学过 C 的朋友对这一点影响肯定更为深刻. 既然是一段连续的内存, 数组的特点就显而易见了, 一旦你知道要查第几个数据, 时间复杂度就是 O(1), 但是对于插入操作就很困难; 还有一种数据结构你也一定很熟悉, 那就是链表, 链表由一组指向 (单向或者双向) 的节点连接的数据结构, 它的特点是内存不连续, 查找困难, 但是插入删除都很容易.
那有没有一种查找容易, 插入删除查找都容易的数据结构呢, 没错, 它就是 hash 表.
本篇, 我们就来讨论:
HashMap 的数据结构实现方式
HashMap 是怎么做到为 get,put 操作提供稳定的时间复杂度的
HashMap 什么时候从单节点转成链表又是什么时候从链表转成红黑树
HashMap 初始化时为什么要给自定义的初始容量.
HashMap 如何保证容量始终是 2 的幂
HashMap 为何要保证容量始终是 2 的幂
HashMap 的 hash 值如何计算
HashMap 为什么是线程不安全的
要了解 HashMap 最好的方式就是看源码, 本篇内容基于 Jdk1.8HashMap 源码.
二, HashMap 的基本要素
磨刀不误砍柴功, 想了解 HashMap 的原理, 必然绕不过 HashMap 源码中的以下几个变量:
DEFAULT_INITIAL_CAPACITY: 初始容量 1<<4 也就是 16
MAXIMUM_CAPACITY: 最大容量 1<<30.
DEFAULT_LOAD_FACTOR: 负载因子, 默认是 0.75. 什么意思呢, 比如说你定义了一个初始容量为 16 的 HashMap, 当你不断向里面添加元素后, 最多到初始容量的 0.75,HashMap 就会触发扩容操作.
threshold: 下一个触发扩容操作的阈值, threshold = CAPACITY * LOAD_FACTOR.
TREEIFY_THRESHOLD: 链表转红黑树阈值, 默认为 8, 超过 8 就会执行链表转红黑树方法, 但是注意转红黑树方法中会判断当前 size 是否大于 64, 只有大于 64 才转红黑树, 否则执行 resize()操作.
UNTREEIFY_THRESHOLD: 红黑树转链表阈值, 默认为 6, 顾名思义, 红黑树节点小于 6 就会转成链表.
Node<K, V> implements Map.Entry<K, V> HashMap 存放数据的基本单位, 里面存有 hash 值, key,value,next.
Node<K, V>[] table: 存放 Node 节点的数组, HashMap 最底层数组, 数组元素可以为单节点 Node, 多节点链表, 多节点红黑树.
以上内容, 有个印象就好, 不必每个都记得. 但这些概念对理解 HashMap 至关重要.
三, 正文
3.1 HashMap 数据结构
HashMap 的数据结构很简单, 它是一个 Node 类型的数组, 每个元素可以为单节点, 多节点链表, 多节点红黑树. 关键的问题是, 这么简单的结构怎么实现的 put,get 都很快? 什么时候从单节点转成链表又是什么时候从链表转成红黑树?
3.1.1 HashMap 如何实现 put,get 操作时间复杂度为 O(1)~O(n)?
我们知道, 查找一个数组的元素, 当我们不知道 index 的时候, 复杂度是很高的, 但是当我们知道 index 的时候, 这个复杂度就是 O(1)级别的. HashMap 使用的就是这个原理.
对于 get 操作, 首先根据 key 计算出 hash 值, 而这个 hash 值执行操作(n - 1) & hash 后就是它所在的 index, 在最好的情况下, 该 index 恰好只有一个节点且 hash 值和 key 的 hash 值相同, 那么时间复杂度就是 O(1), 当该节点为链表或者红黑树时, 时间复杂度会上升, 但是由于 HashMap 的优化(链表长度, 红黑树长度相对于 HashMap 容量不会过长, 过长会触发 resize 操作), 所以最坏的情况也就是 O(n), 可能还会小于这个值.
对于 put 操作, 我们知道, 数组插入元素的成本是高昂的, HashMap 巧妙的使用链表和红黑树代替了数组插入元素需要移动后续元素的消耗. 这样在最好的情况下, 插入一个元素, 该 index 位置恰好没有元素的话, 时间复杂度就是 O(1), 当该位置有元素且为链表或者红黑树的情况下, 时间复杂度会上升, 但是最坏的情况下也就是 O(n).
3.1.2 HashMap 什么时候从单节点转成链表又是什么时候从链表转成红黑树?
单节点转链表很简单, 当根据新加入的值计算出来的 index 处有元素时, 若元素为单节点, 则从节点转为链表.
链表转红黑树有两个条件:
链表长度大于 TREEIFY_THRESHOLD, 默认阈值是 8
HashMap 长度大于 64
当同时满足这两个条件, 那么就会触发链表转红黑树的操作.
3.2 HashMap 初始化时为什么要给自定义的初始容量?
为啥前辈们都要求定义一个 HashMap 的时候一定要使用构造函数 HashMap(int initialCapacity)指定初始容量呢?
在阿里的《Java 开发手册》中是这样说明的:
[推荐] 集合初始化时, 指定集合初始值大小.
说明: HashMap 使用 HashMap(int initialCapacity) 初始化,
正例: initialCapacity = (需要存储的元素个数 / 负载因子) + 1. 注意负载因子(即 loader
factor)默认为 0.75, 如果暂时无法确定初始值大小, 请设置为 16(即默认值).
反例: HashMap 需要放置 1024 个元素, 由于没有设置容量初始大小, 随着元素不断增加, 容
量 7 次被迫扩大, resize 需要重建 hash 表, 严重影响性能.
这个问题在 HashMap 源码中是显而易见的, 每次 put 函数中都会检查当前 size 是否大于 threshold, 如果大于就会进行扩容, 新容量是原来容量的二倍. 那么问题就来了, 当你要存大量数据到 HashMap 中而又不指定初始容量的话, 扩容会被一次接一次的触发, 非常消耗性能.
而初始容量和负载因子给多少好呢, 日常开发中如无必要不建议动负载因子, 而是根据要使用的 HashMap 大小确定初始容量, 这也不是说为了避免扩容初始容量给的越大越好, 越大申请的内存就越大, 如果你没有这么多数据去存, 又会造成 hash 值过于离散.
3.3 HashMap 如何保证容量始终是 2 的幂
HashMap 使用方法 tableSizeFor()来保证无论你给值是什么, 返回的一定是 2 的幂:
- static final int tableSizeFor(int cap)
- {
- int n = cap - 1; // 作用: 保证当 cap 为 2 的幂时, 返回原值而不是二倍, 如 8 返回 8 而不是 16
- 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 |= n>>> 1;
- n |= n>>> 2;
- n |= n>>> 4;
- n |= n>>> 8;
- n |= n>>> 16
假设 n=01000000, n |= n>>> 1 后 n=01100000,n |= n>>> 2 后 n=01111000,n |= n>>> 4; 后 n=01111111, 我们可以发现, 上述 5 步操作可以将一个 32 位数第一位为 1 的后面所有位全变为 1. 这样再执行 n + 1 操作后, 该数就必为 2 的幂次方了. 如 01111111+1 = 10000000.
那又为什么要保证一定是 2 的幂次方呢? 不是不行吗?
3.3.1 HashMap 为何要保证容量始终是 2 的幂
说到这个问题不得不说执行 put()方法时, 是如何根据 hash 值在 table 中定位.
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
- {
- ......
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- ......
可以看到, 它使用了一个 (n - 1) & hash 的操作, n 为当前 hashmap 的容量, 而容量一定为 2 的幂次方, n-1 的二进制低位都为 1, 举例: 16=0000000000010000,15=0000000000001111, 这样的处理好处在于, 当执行(n - 1) & hash 的操作时, 元素的位置仅取决于低位而与高位无关(这种无关性随着 HashMap 容量的增大而减小), 这个逻辑优点是, 无论你的 hash 值有多大, 我都锁定了你的取值范围小于当前容量, 这样做避免了 hash 值过于离散的情况, 而当 HashMap 扩容时又可以同时增大 hash 值的取值范围, 缺点是增加了 hash 碰撞的可能性, 为了解决这个问题 HashMap 修改了 hash 值的计算方法来增加低位的 hash 复杂度.
3.3.2 HashMap 计算 hash 值
不废话, 直接上源码:
- static final int hash(Object key)
- {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
hash 方法用 key 的 hash 值异或上 key 的 hash 值的高 16 位, 为什么要这样做呢?
首先, h>>>16 的值高 16 位都为 0, 这样 h^(h>>>16)时, 高 16 位的值不会有任何变化, 但是低 16 位的值混杂了 key 的高 16 位的值, 从而增加了 hash 值的复杂度, 进一步减少了 hash 值一样的概率.
3.4 HashMap 为什么是线程不安全的
在 Jdk1.7 中, 造成 HashMap 线程不安全的原因之一是 transfer 函数, 该函数使用头查法在多线程的情况下很容易出现闭环链表从而导致死循环, 同时还有数据丢失的问题, Jdk1.8 中没有 transfer 函数而是在 resize 函数中完成了 HashMap 扩容或者初始化操作, resize 采用尾插法很好的解决了闭环链表的问题, 但是依旧避免不了数据覆盖的问题.
在 HashMap 的 put 操作中:
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
- {
- Node<K, V>[] tab;
- Node<K, V> p;
- int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- ......
在执行完 if ((tab = table) == null || (n = tab.length) == 0)判断且为 true 的情况下, 会直接进行赋值, 但是在多线程的环境下, 当两个线程同时完成判断, 线程 1 刚赋值完, 线程 2 再进行赋值, 就造成了数据覆盖的问题.
这只是最简单的现象, 我们要想线程安全, 首先要有多线程安全的处理逻辑, 很明显 HashMap 是没有这样的逻辑的, 那么很多为单线程设计的逻辑就很大可能出问题, 所以 HashMap 为什么是线程不安全的? 它本身设计就不支持多线程下的操作, 所以不该有此问.
如果想要线程安全的使用基于 hash 表的 map, 可以使用 ConcurrentHashMap, 该实现 get 操作是无锁的, put 操作也是分段锁, 性能很好.
所以说术业有专攻, 每个容器的实现都有它对应的优缺点. 我们需要学会的是分析面对的每一种情况, 合理的使用不同的容器去解决问题.
HashMap 基本的原理和对应实现就说到这里了, 更深入的话题如: 红黑树插入节点, 平衡红黑树, 遍历红黑树, 可以直接看红黑树对应的原理和实现.
需要源码注释的请戳这里源码解析
最后, 最近很多小伙伴找我要 Linux 学习路线图, 于是我根据自己的经验, 利用业余时间熬夜肝了一个月, 整理了一份电子书. 无论你是面试还是自我提升, 相信都会对你有帮助!
免费送给大家, 只求大家金指给我点个赞!
电子书 | Linux 开发学习路线图
也希望有小伙伴能加入我, 把这份电子书做得更完美!
有收获? 希望老铁们来个三连击, 给更多的人看到这篇文章
来源: https://segmentfault.com/a/1190000023325586