转载

Java数据结构之HashMap

相信写过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