HashMap原理浅析

数组 数组存储区间是连续的,直接可以放到L1缓存里面CPU读取占用内存严重,故空间复杂度很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;

链表 链表存储区间离散,必须在堆空间,一个一个看next遍历,占用内存比较宽松,故空间复杂度很小T(1),但时间复杂度很大,达O(N)、优化后O(lgN)。链表的特点是:寻址困难,插入和删除容易。

哈希表 那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表

HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

jdk1.6 头插法

数组加链表

Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,它们通过next这个属性链接在一起。也就是说数组中存储的是最后插入的元素。©

jdk1.8尾插法

HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的。

https://tryenough.com/java-hashmap

在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券