文档章节

HashMap底层实现原理,以及和Hashtable的比较

 懿宁19931210
发布于 2017/09/12 10:25
字数 507
阅读 14
收藏 0

我们要知道HashMap底层实现是数组(Entry类型)加上链表的数据结构---拉链法实现哈希表Entry 实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数。

1.通过hash()函数,计算key对应的哈希值,找到数组中存储位置,在冲突(不同的关键字,对应相同的哈希值,在)较少的情况下,他的查询效率是很高的,如果发生冲突就在数组元素所在链表的表头插入该值,所以在查找HashMap时候有两个关键函数,一个是hash()函数找到key在数组中的位置,一个是equals()函数,在链表中找到key,返回value,通常返回某关键字时候用的判断方法:(key==null ? k==null :key.equlas(k)),可见关键字可以为null

   2.Hashtable 的实例有两个参数影响其性能:初始容量 和 加载因子。容量是哈希表中桶的数量,初始容量 就是哈希表创建时的容量。注意,哈希表的状态为 open:在发生“哈希冲突”的情况下,单个桶会存储多个条目,这些条目必须按顺序搜索。加载因子是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。通常,默认加载因子是 0.75(当数据元素个数达到数组总容量的75%时候,要对数组进行动态扩展), 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查找某个条目的时间(在大多数 Hashtable 操作中,包括 get 和 put 操作,都反映了这一点)。

© 著作权归作者所有

共有 人打赏支持
粉丝 0
博文 37
码字总数 10902
作品 0
包头
私信 提问
Java常见面试题及答案 21-30(集合类)

21.HashMap的工作原理是什么? HashMap内部是通过一个数组实现的,只是这个数组比较特殊,数组里存储的元素是一个Entry实体(jdk 8为Node),这个Entry实体主要包含key、value以及一个指向自身的...

t4i2b10x4c22nf6a
2017/12/18
0
0
hashmap实现原理浅析

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

商者
2016/03/30
37
0
BAT面试必备——Java 集合类

本文首发于我的个人博客:尾尾部落 1. Iterator接口 Iterator接口,这是一个用于遍历集合中元素的接口,主要包含hashNext(),next(),remove()三种方法。它的一个子接口LinkedIterator在它的基...

繁著
09/09
0
0
HashMap和HashTable简介和区别

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

光明辉煌
04/17
0
0
[收藏文章]Java岗位面试题

一、Java基础 1. String类为什么是final的。 final修饰的类不能被继承,即它不能拥有自己的子类,否在会在编译期间报错。 final修饰的方法不能被重写 final修饰的变量,无论是类属性、对象属...

vaneL
01/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

最重要的是做什么,而不是怎么做。

最重要的是做什么,而不是怎么做。 做什么是战略,怎么做是战术。将军下令说,天黑前拿下这座山头,这是战略。手下的士兵可以不知道为什么要拿下这座山头,还非得是天黑之前,但士兵必须知道...

我是菜鸟我骄傲
34分钟前
0
0
w, vmstat, top, sar, nload命令查看系统状态信息

w/uptime 查看系统负载 cat /proc/cpuinfo 查看cpu核数 vmstat 监控系统状态,用法 vmstat 1,关键的几列: r, b, swpd, si, so, bi, bo, us, wa top 查看进程使用资源情况 top -c 显示详细的...

野雪球
今天
2
0
小白创建一个spring boot项目

进入 https://start.spring.io/

lilugirl
今天
3
0
Alibaba Java诊断利器Arthas实践--使用redefine排查应用奇怪的日志来源

背景 随着应用越来越复杂,依赖越来越多,日志系统越来越混乱,有时会出现一些奇怪的日志,比如: [] [] [] No credential found 那么怎样排查这些奇怪的日志从哪里打印出来的呢?因为搞不清...

hengyunabc
今天
2
0
home hosts

home hosts lwk@qwfys:~$ cat /etc/hosts127.0.0.1 localhost127.0.1.1 qwfys192.168.56.101vm600.qwfys.com39.108.212.91alpha1.ppy.com39.108.117.122alpha2.p......

qwfys
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部