hashmap的数据结构

存储结构

hashmap在jdk1.8之前采用数组加链表的方式存储,根据key的hash计算存储在数组中的位置,因为hash可能重复,当hash值重复时,则在该数组元素下卦一个链表,jdk1.8以后,默认当链表长度大于8时,会在该链表下挂一个红黑树。

  • 如何计算hash
    使用数据的hash值与数组长度进行按位与运行

    hash(data) & table.length

效果相当于取模,得到的值不会大于数组长度(redis中的slot也是这样的算法)

效率

所以对于没有链表数组元素的操作,比如CRUD都很快,只需一次寻址即可,如果定位到有链表的数组元素,对于添加操作其时间复杂度依然位O(1),因为最新的Entry会插入链表的头部,只需要简单的改变引用链即可,但是对于查找来说,就需要遍历整个链表,通过key的equals方法逐一对比。

容量问题

解释1:创建hashmap和hashtable时,若不指定初始容量值,hashtable默认的初始值为11,之后每次扩充,容量变为原来的==2n+1==。hashmap默认初始大小为16,之后每次扩容,容量变为原来的==2倍==。如果创建时制定了大小,hashtable会直接使用给定大小,但hashmap会将其扩充到==2的幂次方==大小。也就是说hashmap总是使用2的幂次方作为hash表的大小。原因:为了能让hashmap存取高效,尽量减少碰撞,也就是说要尽量把数据分配均匀,每个链表/红黑树长度大致相同,首先会想到取余操作实现,但是,取余(%)中如果除数是2的幂次则等价于与其除数减一的与(&)操作,即 hash%length==hash&(length-1),前提是length是2的n次方,并且二进制操作&相对于%能提高效率,这就解释了hashmap的长度为什么是2的幂次方。

解释2:
根据上面计算元素在数组中的角标算法(按位与),则table的长度的二进制必须得是 000011111的形式(后面必须全是连续的1),否则进行按位与时就有的值取不到,例如,如果表长为 0110(十进制为6),则任何数据与其进行按位与时都无法取到 xxx1,因为按位与必须两个数据对应位置全是1结果才是1。这样就浪费了一个空间

Leave a Comment