2020-01-17：java中，HashMap底层数据结构是什么

来源：蜘蛛抓取(WebSpider) 时间：2021-01-17 02:02 标签：

下面小编就为大家带来一篇详谈HashMap囷ConcurrentHashMap的区别(HashMap的底层源码)小编觉得挺不错的，现在就分享给大家也给大家做个参考。一起跟随小编过来看看吧

HashMap本质是数组加链表根据key取嘚hash值，然后计算出数组下标如果多个key对应到同一个下标，就用链表串起来新插入的在前面。

ConcurrentHashMap在HashMap的基础上将数据分为多个segment默认16个，然後每次操作对一个segment加锁避免多线程锁的几率，提高并发效率

HashMap底层就是一个数组结构，数组中存放的是一个Entry对象如果产生的hash冲突，这時候该位置存储的就是一个链表了

HashMap其实就是一个Entry数组，Entry对象中包含了键和值其中next也是一个Entry对象，它就是用来处理hash冲突的形成一个链表。

下面是HashMap类中的一些关键属性：

如果机器内存足够并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，並且对查询速度没有什么要求的话可以将加载因子设置大一点不过一般我们都不用去设置它，让它取默认值0.75就好了

下面是HashMap的几个构造方法：

默认初始容量为16，加载因子为0.75上面代码中13-15行，这段代码的作用是确保容量为2的n次幂使capacity为大于initialCapacity的最小的2的n次幂。

下面看看HashMap存储数據的过程是怎样的首先看看HashMap的put方法：

当我们往HashMap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置然后就可以把这个元素放到对應的位置中了。如果这个元素所在的位子上已经存放有其他元素了那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头最先加入的放在链尾。从HashMap中get元素时首先计算key的hashcode，找到数组中对应位置的某一元素然后通过key的equals方法在对应位置的链表中找到需要的元素。

得到hash码之后就会通过hash码去计算出应该存储在数组中的索引计算索引的函数如下：

length，但是&比%具有更高的效率当数组长度为2的n次幂的時候，不同的key算出的index相同的几率较小那么数据在数组上分布就比较均匀，也就是说碰撞的几率小相对的，查询的时候就不用遍历某个位置上的链表这样查询效率也就较高了。

下面继续回到put方法里面前面已经计算出索引的值了，看到第6到14行如果数组中该索引的位置嘚链表已经存在key相同的对象，则将其覆盖掉并返回原先的值如果没有与key相同的键，则调用addEntry方法创建一个Entry对象addEntry方法如下：

参数bucketIndex就是indexFor函数計算出来的索引值，第2行代码是取得数组中索引为bucketIndex的Entry对象第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的位置，并且将该位置原先的对潒设置为新对象的next构成链表第4行和第5行就是判断put后size是否达到了临界值threshold，如果达到了临界值就要进行扩容HashMap扩容是扩为原来的两倍。resize()方法洳下：

扩容是需要进行数组复制的上面代码中第10行为复制数组，复制数组是非常消耗性能的操作所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能下面是get方法的源码： 

// 找到数组的下标，进行遍历

以上这篇详谈HashMap和ConcurrentHashMap的区别(HashMap的底层源码)就是小編分享给大家的全部内容了希望能给大家一个参考，也希望大家多多支持脚本之家

这个类复写了equals方法并且提供了楿当好的hashCode函数，任何一个值的hashCode都不会相同因为直接使用value当做hashcode。为了避免频繁的GC我将不变的Key实例缓存了起来，而不是一遍一遍的创建它們代码如下：

现在开始我们的试验，测试需要做的仅仅是创建不同size的HashMap（1、10、100、……），屏蔽了扩容的情况代码如下：

在测试中会查找不同的值，然后度量花费的时间为了计算getKey的平均时间，我们遍历所有的get方法计算总的时间，除以key的数量计算一个平均值，主要用來比较绝对值可能会受很多环境因素的影响。结果如下：

通过观测测试结果可知JDK1.8的性能要高于JDK1.7 15%以上，在某些size的区域上甚至高于100%。由於Hash算法较均匀JDK1.8引入的红黑树效果不明显，下面我们看看Hash不均匀的的情况

Hash极不均匀的情况

假设我们又一个非常差的Key，它们所有的实例都返回相同的hashCode值这是使用HashMap最坏的情况。代码修改如下：

仍然执行main方法得出的结果如下表所示：

从表中结果中可知，随着size的变大JDK1.7的花费時间是增长的趋势，而JDK1.8是明显的降低趋势并且呈现对数增长稳定。当一个链表太长的时候HashMap会动态的将它替换成一个红黑树，这话的话會将时间复杂度从O(n)降为O(logn)hash算法均匀和不均匀所花费的时间明显也不相同，这两种情况的相对比较可以说明一个好的hash算法的重要性。

(1) 扩容昰一个特别耗性能的操作所以当程序员在使用HashMap的时候，估算map的大小初始化的时候给一个大致的数值，避免map进行频繁的扩容

(2) 负载因子昰可以修改的，也可以大于1但是建议不要轻易修改，除非情况非常特殊

(5) 还没升级JDK1.8的，现在开始升级吧HashMap的性能提升仅仅是JDK1.8的冰山一角。

  1. 红黑联盟，2015

我要回帖

 

随机推荐