HashMap的实现
HashMap的实现
本人慧星撞地球 发表于1年前
HashMap的实现
  • 发表于 1年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

一:提要

1、第一次学习HashMap的实现,所以有学的不周到的地方以后会更正,也请路过的读者拔刀相助。

2、java中的取模运算就是算余数的。例如12/16=12;28/16=12

3、Entry:条目

4、线性数组

二:正题

在java语言编程中,就基本的结构就是两种,一个是数组另一个就是模拟指针(引用),即链表。所有的数据结构都可以用这两种数据结构来构造。HashMap也不例外。

这两种最基本的结构基本上可以算是两个极端。

数组存储区域是连接的,占用内存严重,故空间复杂度大,时间复杂度小。所以数组存储的特点是:寻址容易,插入和删除困难。

链表存储区域比较离散,占用内存比较宽松,故空间复杂度小,但是时间复杂度大。所以链表存储的特点就是:寻址困难,插入和删除容易。

综合两者的特性,能不能做出一种寻址容易,插入和删除也容易的数据结构呢,答案是肯定的。那就是哈希表。哈希表有多种实现方式,今天要学习的是--拉链法。

HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。

从上图中可以看到,HashMap底层就是一个数组结构,数组的每一项又是一个链表。每个数组中存储的是链表的头结点。

当新建一个HashMap的时候就会初始化一个数组,源码如下:

可以看出,Entry就是数组中的元素,每个Map.Entry其实就是一个key-value对。它持有一个指向下一个元素的引用,这就构成了链表。

HashMap的存储实现:

存储:

从上面的源代码中可以看出:当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

也就是说数组中存储的是最后插入的元素。

 addEntry(hash, key, value, i)方法根据计算出的hash值,将key-value对放在数组table的i索引处。addEntry 是HashMap 提供的一个包访问权限的方法,代码如下:

 当系统决定存储HashMap中的key-value对时,完全没有考虑Entry中的value,仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value 随之保存在那里即可。

   hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算,防止低位不变,高位变化时,造成的hash冲突。

读取:

有了上面存储时的hash算法作为基础,理解起来这段代码就很容易了。从上面的源代码中可以看出:从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

 

 

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 24
码字总数 10716
×
本人慧星撞地球
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: