Java数据结构之HashMap

栏目: Java · 发布时间: 5年前

内容简介:相信写过Java代码的都知道Map接口,它是一个key,value键值对的存储结构. Map接口里最常用的实现类就是HashMap了,相信大家都用过,今天我们就简单讲一讲HashMap底层的数据结构.HashMap在java1.7及之前,底层数据结构是数组加链表,到java1.8之后为了优化链表存储时候的插入和查询性能,增加了二叉树这种数据结构,下面就一起看看HashMap的源码看看这些数据结构它是怎么用到.先看构造函数,HashMap一共有4个构造函数,但是实际上最终调用的只有一个,下面是代码.

相信写过 Java 代码的都知道Map接口,它是一个key,value键值对的存储结构. Map接口里最常用的实现类就是HashMap了,相信大家都用过,今天我们就简单讲一讲HashMap底层的数据结构.

HashMap在java1.7及之前,底层数据结构是数组加链表,到java1.8之后为了优化链表存储时候的插入和查询性能,增加了二叉树这种数据结构,下面就一起看看HashMap的源码看看这些数据结构它是怎么用到.

先看构造函数,HashMap一共有4个构造函数,但是实际上最终调用的只有一个,下面是代码.

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

这个构造方法一共有两个参数,一个叫initalCapacity,一个叫loadFactor.翻译过来就是初始化容量和加载因子,初始化容量很好理解,因为用的数组,初始化容量实际上就是数组的长度(这里实际上还有一个类似于懒加载的过程,当你只是定义了初始化长度但是并没有put数据进去的时候,数组实际上为null,就不存在说定义数组长度),那什么是加载因子呢,实际上HashMap在存放put进去的key的时候是根据这个key的hashcode来计算具体放在数组的那个位置,hashcode一般来说是分布均匀的,也就是存储相同个数的key,数组长度越长,那么两个key被放到数组同一个位置的可能性就越小,如果多个key被放到数组的同一个位置,那么就会产生链表,链表的查询效率是低于数组的,那么为了保证效率,肯定是尽量让元素不被放到数组的同一个位置,所有数组长度肯定是越长越好,但是数组长度边长之后带来一个问题,你的数组太长了,很多位置都是空的,就造成了空间的浪费,实际上加载因子这个参数就是用来描述你是如何平衡效率和空间利用率的,加载因子实际上就是存放元素的个数除以数组的长度,你的加载因子越大,那么你存放key的时候出现链表的可能性就越大,浪费的空间就越小,你的加载因子越小,浪费的空间就越大,出现链表的可能性就越小,这个加载因子默认的是0.75,官方给的注释对这个0,75也做了一番解释,大概意思就是平均分布的hashCode,0.75是一个比较均衡的性能与空间兼顾点.

实际上明白这两个构造方法里的参数之后,大概就已经知道HashMap底层的数据是怎么存储的了,无非就是一个key来了之后,用这个key的hashCode来计算出这个key 应该放在数组的那个位置,如果这个位置没有元素,那就直接放,如果计算出来的这个位置之前已经有key了,那么就把这个key和原来就有的key合并成一个链表放到数组的这个位置.

说完了数组跟链表怎么存在于hashMap中之后,再来讲讲二叉树什么时候会用到,在java1.7之前是hashMap里是没有二叉树的,只有数组和链表,但是我么知道链表的查询效率和插入效率是比数组低很多的,假如正好我这个map中的key的hashCode方法设计的不合理或者其他原因,导致计算出来的存放的数组位置重复率特别高,上面已经说过,如果位置一样的,那么多个元素会以链表的形式存放在数组的某个位置中,这个时候hashMap的插入和查询会大大降低,因为每次插入和查询都要对链表进行操作,而且链表越长效率越低.这个时候就出现了二叉树,如果一个链表长度太长了,那么就不存链表,直接以二叉树的形式存放进去,默认的链表转二叉树的长度是8,链表长度超过8就会以树的形式存储在数组对应位置,虽然二叉树的查询和插入性能低于数组,但是比链表还是要好很多的.实际上如果你的hashCode是一个均匀分布的值并且loadFactor定义的合理,根本就不会出现二叉树,二叉树是用来解决极端情况下性能问题的.

以上就是关于HashMap相关的数据结构如何使用的简要说明,其实Java中的hashMap有很多设计的亮点,可以说相比与老版本里的hashtable增加了很多亮眼的设计,后续我会再继续再写一些关于HashMap设计中比较牛逼的算法,希望能找到有兴趣的人一起探讨学习.

转载时请注明出处及相应链接,本文永久地址:https://blog.yayuanzi.com/24614.html

Java数据结构之HashMap

Java数据结构之HashMap 微信打赏

Java数据结构之HashMap 支付宝打赏

感谢您对作者joy1的打赏,我们会更加努力!    如果您想成为作者,请点我


以上所述就是小编给大家介绍的《Java数据结构之HashMap》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

这才是马云

这才是马云

陈伟 / 浙江人民出版社 / 2011-5 / 30.00元

“幽默马云”、“开心马云”、“顽皮马云”、“狂妄马云”等。《这才是马云》从各个角度揭开了千面马云的真面目,告诉你一个与想象中大不一样的马云。这不只是一本书,更像一部喜剧电影,让你通过声音、色彩、表情等诸多要素走近马云,感受阿里巴巴。没有冗长的说教,只有让人忍俊不禁的细节;没有高深的理论,只有通俗、诚恳的陈述。作者借幽默平常的琐事,记录下马云“可爱”的一面,看完后让人恍然大悟:原来,马云是这样一个人......一起来看看 《这才是马云》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具