文档章节

HashMap的实现

本人慧星撞地球
 本人慧星撞地球
发布于 2017/02/13 13:51
字数 1066
阅读 1
收藏 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
作品 0
朝阳
程序员
hashmap实现原理浅析

看了下JAVA里面有HashMap、Hashtable、HashSet三种hash集合的实现源码,这里总结下,理解错误的地方还望指正 HashMap和Hashtable的区别 HashSet和HashMap、Hashtable的区别 HashMap和Hashtab...

商者
2016/03/30
37
0
HashMap,LinkedHashMap,TreeMap的有序性

HashMap 是将 Key 做 Hash 算法,然后将 Hash 值映射到内存地址,直接取得 Key 所对应的数据。在 HashMap 中,底层数据结构使用的是数组,所谓的内存地址即数组的下标索引。HashMap 的高性能...

小杰java
03/08
0
0
HashMap和HashSet的区别

HashMap和HashSet的区别是Java面试中最常被问到的问题。如果没有涉及到Collection框架以及多线程的面试,可以说是不完整。而Collection框架的问题不涉及到HashSet和HashMap,也可以说是不完整...

LCZ777
2014/03/29
0
0
HashMap和HashTable简介和区别

一、HashMap简介 HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。 HashMap是非线程安全的,只是用于单...

光明辉煌
04/17
0
0
Hashtable HashMap ConcurrentHashMap 源码分析

1.Hashtable与HashMap区别比较 先来说说这两者之间的不同: 1.Hashtable 是JDK1.2出现的, 父类继承Dictionary 实现的是Map, HashMap父类是AbstractMap实现的Map public class Hashtable exte...

陈小扁
2016/03/10
230
0

没有更多内容

加载失败,请刷新页面

加载更多

将桌面捕获到虚拟摄像头

当然你可以直接用现成的虚拟摄像头软件实现这个功能。不过当初我开发这个插件的原因是,需要在Flash产品里面共享桌面,如果此时需要引导用户安装一个第三方的虚拟摄像头体验不好,所以公司希...

一个灰
31分钟前
1
0
Linux 配置网络绑定

1. 常见的网卡绑定驱动模式: mod=0 (balance-rr) Round-robin 衡抡循环策略 特点: 传输数据包顺序是依次传输(即:第1个包走eth0,下一个包就走eth1.一直循环下去,直到最后一个传输完毕),...

JeremyTown
40分钟前
0
0
VS code 编辑器使用技能

VS code 文档:https://code.visualstudio.com/docs/getstarted/locales 1、安装中文扩展包 打开扩展包按钮(最左上角从上往下数第5个按钮或者快捷键 Ctrl + Shift + X) 搜索语言包categor...

削个椰子皮_给个梨
49分钟前
4
0
Django 2.1.2项目中创建一个应用

Django 2.1.2项目中创建一个应用: 1.新建一个应用(app), 名称叫 learn python manage.py startapp learn # learn 是一个app的名称 2.在learn应用中修改视图文件views.py: # Create your vi...

MichaelShu
50分钟前
5
0
Swagger中配置了@ApiModelProperty的allowableValues属性但不显示的问题

现在用Swagger来生成API文档的例子已经非常多了,今天碰到开发同事问了一个问题,帮着看了一下,主要还是配置方法的问题,所以记录一下。如果您也碰到了同样的问题,希望本文对您有用。 问题...

程序猿DD
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部