文档章节

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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JS三元运算示例

1. topFlag=topFlag ==0?1:0; 等于 if(topFlag=00){ topFlag=1; }else if(topFlag == 1){ topFlag=0; } 2. 5>3?alert('5大'):alert('3大'); 即 if(5>3){alert('5大')}else{alert('3大')}; 注......

森火
今天
0
0
利用Slf4j的MDC跟踪方法调用链

why? 一个web项目通常提供很多URL访问地址, 项目一般都是分层处理,例如Controller——>Service——>DAO。 如果想根据日志查看用户一次请求都走了哪些方法(多数是查错误)。 如果系统是多人...

杨春炼
今天
7
0
Maven介绍及安装

Maven介绍及安装 以下内容是本人早期学习时的笔记,可能比较详实繁琐,现在复习一下Maven,顺便将内容抛出来,供大家一起学习进步。 一、Maven简介 Maven是Apache旗下的一款项目管理工具,是...

星汉
今天
0
0
小程序Aes解密

主要步骤: 1、下载AES源码(JS版) 2、在小程序中新建一个公共的文件夹,把AES源码拷贝进去(注意:需要暴露接口 module.exports = CryptoJS;) 3、添加一个用于加密解密的公共JS,可取名为...

Mr_Tea伯奕
今天
0
0
Go实现文件传输(基本传输可用)

发送端 package mainimport ("fmt""os""net""io")func SendFile(path string, connect net.Conn){file, oerr :=os.Open(path)if oerr !=nil{fmt.Println("Open", oerr)......

CHONGCHEN
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部