JDK1.8 HashMap 总结
- JDK1.8 HashMap源码解析 目录
概论
- HashMap 是无论在工作还是面试中都非常常见常考的数据结构。比如 Leetcode 第一题 Two Sum 的某种变种的最优解就是需要用到 HashMap 的,高频考题 LRU Cache 是需要用到 LinkedHashMap 的。
- 随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。
- HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。
- HashMap最多只允许一条记录的键为null,允许多条记录的值为null。
- HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。
Hasmap 的继承关系
Hashmap 的原理
1、对于 HashMap 中的每个 key,首先通过 hash function 计算出一个 hash 值,这个hash值经过取模运算就代表了在 buckets 里的编号 buckets 实际上是用数组来实现的,所以把这个hash值模上数组的长度得到它在数组的 index,就这样把它放在了数组里。
2、如果果不同的元素算出了相同的哈希值,那么这就是哈希碰撞,即多个 key 对应了同一个桶。这个时候就是解决hash冲突。
3、随着插入的元素越来越多,发生碰撞的概率就越大,某个桶中的链表就会越来越长,直到达到一个阈值,HashMap就受不了了,为了提升性能,会将超过阈值的链表转换形态,转换成红黑树的结构,这个阈值是 8 。也就是单个桶内的链表节点数大于 8 ,就会将链表有可能
变身为红黑树。(树化的条件是:桶中链表的长度达到了8,并且数组的长度大于等于64。)
解决Hash冲突的方法
开放定址法
这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:
Hi=(H(key)+di)% m i=1,2,…,n
其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有三种 线性探测再散列,二次探测再散列,伪随机探测再散列.
再哈希法
这种方法是同时构造多个不同的哈希函数
Hi=RH1(key) i=1,2,…,k
当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间.
链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。
链地址法适用于经常进行插入和删除的情况。
建立公共溢出区
这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。
Hashmap 最终的形态
HashMap主体上就是一个数组结构,每一个索引位置英文叫做一个 bin,我们这里先管它叫做桶,比如你定义一个长度为 8 的 HashMap,那就可以说这是一个由 8 个桶组成的数组。
当我们像数组中插入数据的时候,大多数时候存的都是一个一个 Node 类型的元素,Node 是 HashMap中定义的静态内部类。
在集合初始化时,指定集合初始值大小。
见《阿里编程规范》第一章 1.5集合处理章节第9条。
- 在需要存储的数据个数确定的情况下,指定集合初始值大小。
- initialCapacity = (需要存储的元素个数 / 负载因子) + 1.
对红黑树的理解
- 1、每个节点非红即黑
- 2、根节点总是黑色的
- 3、如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
- 4、每个叶子节点都是黑色的空节点(NIL节点)
- 5、从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?
默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方,一个是原下标的位置,另一种是在下标为<原下标+原容量>的位置。
重新调整HashMap大小存在什么问题吗?
- 当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。(多线程的环境下不使用HashMap)
- 为什么多线程会导致死循环,它是怎么发生的?
- HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。这时候,HashMap需要扩展它的长度,也就是进行Resize。
- 1.扩容:创建一个新的Entry空数组,长度是原数组的2倍。
- 2.ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。
- HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。这时候,HashMap需要扩展它的长度,也就是进行Resize。
链表法导致的链表过深问题为什么不用二叉查找树代替
之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。
而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。
JDK8中对HashMap做了哪些改变?
在 JDK1.8中,如果链表的长度超过了8,那么链表将转换为红黑树。(桶的数量必须大于64,小于64的时候只会扩容)
发生hash碰撞时,JDK 1.7 会在链表的头部插入,而 JDK1.8会在链表的尾部插入
在 JDK1.8中,Entry被Node替代
Hashmap 的容量大小为什么要求是2^n?
前提
元素在数组中的位置的计算方式是: tab[i = (n - 1) & hash] 。也就是通过对数组大小求模得到的,因为我们知道hash 的计算方式是 hashCode() 的高 16 位异或低 16 位实现的,32 位值只要有一位发生改变,整个 hash() 返回值就会改变,也就是说我们的hash 值发生冲突的概率是比较小的,也就是说hash 值是比较随机的。
冲突发生时
更多的冲突是发生在取模的时候,所以这个时候只要保证了我们的取模运算 (n - 1) & hash,尽量能保证hash 值的特性也就是随机性。因为我们知道与运算的特点是,两位同时为“1”,结果才为“1”,否则为0。
这个时候我们只要 (n - 1) 让的二进制表示都是一串1,例如"011111" 就可以了,因为安位与1 结果是不变的,也就是可以延续hash 值的散列性。
2n次方的二进制表示
2的6次方,就是从右向左 6 个 0,然后第 7 位是 1。
why?
只有数组的长度是2的次方了,n-1 的二进制才能尽可能多的是1 !
你觉得Hashmap 还有什么可以改进的地方吗,欢迎讨论
虽然java 源代码的山很高,如果你想跨越,至少你得有登山的勇气,这里我给出自己的一点点愚见,希望各位不吝指教