前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >HashMap 与 HashTable的对比

HashMap 与 HashTable的对比

作者头像
desperate633
发布于 2018-08-23 07:59:48
发布于 2018-08-23 07:59:48
5490
举报
文章被收录于专栏:desperate633desperate633

HashMap为何数组的长度是2的n次方

  • 1.这个方法非常巧妙, 它通过 h & (table.length -1) 来得到该对象的保存位, 而HashMap 底层数组的长度总是 2 的 n 次方, 2n-1 得到的二进制数的每个位上的值都为 1,那么与全部为 1 的一个数进行与操作, 速度会大大提升。
  • 2.当 length 总是 2 的 n 次方时, h& (length-1)运算等价于对 length 取模, 也就是h%length, 但是&比%具有更高的效率
  • 3.当数组长度为 2 的 n 次幂的时候, 不同的 key 算得的 index 相同的几率较小,那么数据在数组上分布就比较均匀, 也就是说碰撞的几率小, 相对的, 查询的时候不用遍历某个位置上的链表, 这样查询效率也就较高了。

HashMap 的扩容机制:

而负载因子表示一个散列表的空间的使用程度,有这样一个公式:initailCapacity*loadFactor=HashMap的容量。

所以负载因子越大则散列表的装填程度越高,也就是能容纳更多的元素,元素多了,链表大了,所以此时索引效率就会降低。

反之,负载因子越小则链表中的数据量就越稀疏,此时会对空间造成烂费,但是此时索引效率高。

当 HashMap 中的结点个数超过数组大小loadFactor(加载因子) 时, 就会进数组扩容,loadFactor 的默认值为 0.75。也就是说,默认情况下,数组大小为 16,那么当 HashMap中结点个数超过 160.75=12 的时候, 就把数组的大小扩展为2*16=32, 即扩大一倍, 然后重新计算每个元素在数组中的位置, 并放进去, 而这是一个非常消耗性能的操作。

多线程下 HashMap 出现的问题:

  • 1.多线程 put 操作后, get 操作导致死循环,导致 cpu100%的现象。 主要是多线程同时put 时, 如果同时触发了 rehash 操作, 会导致扩容后的 HashMap 中的链表中出现循环节点, 进而使得后面 get 的时候, 会死循环。
  • 2.多线程 put 操作, 导致元素丢失, 也是发生在多个线程对 hashmap 扩容时。

HashMap 和 HashTable 的区别

    1. Hashtable 是线程安全的, 方法是 Synchronized 的, 适合在多线程环境中使用, 效率稍低; HashMap 不是线程安全的, 方法不是 Synchronized 的, 效率稍高, 适合在单线程环境 下 使 用 , 所 以 在 多 线 程 场 合 下 使 用 的 话 , 需 要 手 动 同 步 HashMap ,Collections.synchronizedMap()。
  • 2.HashMap 的 key 和 value 都可以为 null 值, HashTable 的 key 和 value 都不允许有 Null 值。
  • 3.HashMap 中数组的默认大小是 16, 而且一定是 2 的倍数, 扩容后的数组长度是之前数组长度的 2 倍。 HashTable 中数组默认大小是 11, 扩容后的数组长度是之前数组长度的 2 倍+1。
  • 4.哈希值的使用不同
  • 5 HashMap 重新计算 hash 值, 而且用&代替求模

HashTable 的效率比较低的原因

在线程竞争激烈的情况下 HashTable 的效率非常低下。 因为当一个线程访问HashTable 的同步方法时, 访问其他同步方法的线程就可能会进入阻塞或者轮训状态。 如线程 1 使用 put 进行添加元素, 线程 2 不但不能使用 put 方法添加元素, 并且也不能使用get 方法来获取元素, 所以竞争越激烈效率越低

判断是否含有某个键

在 HashMap 中, null 可以作为键, 这样的键只有一个; 可以有一个或多个键所对应的值为 null。 当 get()方法返回 null 值时, 既可以表示 HashMap 中没有该键, 也可以表示该键所对应的值为 null。 因此, 在 HashMap 中不能用 get()方法来判断 HashMap 中是否存在某个键, 而应该用 containsKey()方法来判断。 Hashtable 的键值都不能为 null, 所以可以用 get()方法来判断是否含有某个键。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017.09.05 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
HashMap&ConcurrentHashMap&HashTable
JDK1.8以前Hashmap底层是数组和链表结合在一起使用,也就是散列链表。hashmap的key的hashcode()扰动函数处理后得到hash值,然后通过(n-1)& hash 判断当前元素存放的位置,如果当前位置存在元素的话,就判断当前位置存在的元素是否与之相同,相同则直接覆盖,不相同就通过拉链法解决冲突。
Tim在路上
2020/08/04
4340
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
十一、为什么我们需要hash()函数 (n-1)\&hash,而不是直接用key的hashcode直接计算下标
寻求出路的程序媛
2024/10/17
8080
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
HashMap,HashTable,ConcurrentHashMap异同比较
(3)因为线程安全、哈希效率的问题,HashMap效率比HashTable的要高。
爱撸猫的杰
2019/03/28
5420
HashMap,HashTable,ConcurrentHashMap异同比较
Java集合详解4:一文读懂HashMap和HashTable的区别以及常见面试题
《Java集合详解系列》是我在完成夯实Java基础篇的系列博客后准备开始写的新系列。
Java技术江湖
2019/10/11
9010
HashMap底层实现详解
  HashMap是基于哈希表的Map接口的非同步实现(Hashtable跟HashMap很像,唯一的区别是Hashtalbe中的方法是线程安全的,也就是同步的)。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
IT小马哥
2020/03/18
6730
内含扩容源码的面试题,目标是手写HashMap!
    推荐在单线程环境下使用HashMap替代,如果需要多线程使用则用ConcurrentHashMap。
上分如喝水
2021/08/16
3960
内含扩容源码的面试题,目标是手写HashMap!
HashMap常见面试题_java面试题大汇总
大家好,又见面了,我是你们的朋友全栈君。 目录 1.HashMap的数据结构? 2.HashMap的工作原理? 3.当两个对象的hashCode相同会发生什么? 4.你知道hash的实现吗?为什么要这
全栈程序员站长
2022/09/22
3930
HashMap常见面试题_java面试题大汇总
Java面试题:ArrayList底层实现原理、HashMap的实现原理、HashMap的jdk1.7和jdk1.8有什么区别
举个例子:在一开始,如果默认的长度为10的数组已经装满了,在装满的情况下,我一次性要添加100个数据 addAll,很显然 10扩容1.5倍 变成15,还是不够,怎么办? ——> 此时新数组的长度,就以实际情况为准,就是110(100+10)
寻求出路的程序媛
2024/06/04
2590
Java面试题:ArrayList底层实现原理、HashMap的实现原理、HashMap的jdk1.7和jdk1.8有什么区别
深入理解HashMap
HashMap是一个非常重要的集合,日常使用也非常的频繁,同时也是面试重点。本文并不打算讲解基础的使用api,而是深入HashMap的底层,讲解关于HashMap的重点知识。需要读者对散列表和HashMap有一定的认识。
Java旅途
2021/02/04
5580
深入理解HashMap
面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别
HashMap和Hashtable都是用hash算法来决定其元素的存储,因此HashMap和Hashtable的hash表包含如下属性:
猿人谷
2018/08/01
1.8K0
面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别
HashMap的实现原理
HashMap概述 HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap的数据结构 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。 从上图中可以看出,HashMap底层就是一个数组结构,数组中的每一项
Tanyboye
2018/07/02
4940
HashMap的实现原理及hash冲突(碰撞)解决方法[通俗易懂]
HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法 时,系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法,都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后,系统会根据该 hashCode 值来决定该元素的存储位置。源码如下:
全栈程序员站长
2022/11/01
8740
HashMap的实现原理及hash冲突(碰撞)解决方法[通俗易懂]
Java集合篇:HashMap 与 ConcurrentHashMap 原理总结
(1)HashMap 是基于 Map 接口的非同步实现,线程不安全,是为了快速存取而设计的;它采用 key-value 键值对的形式存放元素(并封装成 Node 对象),允许使用 null 键和 null 值,但只允许存在一个键为 null,并且存放在 Node[0] 的位置,不过允许存在多个 value 为 null 的情况。
全栈程序员站长
2022/09/12
13.4K0
Java集合篇:HashMap 与 ConcurrentHashMap 原理总结
高效编程之hashmap你必须要懂的知识点
以前看Java的招聘要求:Java基础扎实,熟悉常用集合类,多线程,IO,网络编程,经常会疑惑,集合类不就ArrayList,HashMap会用,熟悉下API不就好了么,知道得越多才会发觉不知道的还有好多!     一入Java深似海啊
矿泉水
2018/05/11
1.1K1
高效编程之hashmap你必须要懂的知识点
看完这篇 HashMap ,和面试官扯皮就没问题了
「如果你没有时间细抠本文,可以直接看 HashMap 概述,能让你对 HashMap 有个大致的了解」。
cxuan
2020/06/28
5750
看完这篇 HashMap ,和面试官扯皮就没问题了
HashMap实现原理及源码分析
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/details/52388682
DannyHoo
2018/09/13
5K0
HashMap实现原理及源码分析
去哪面试都会问的HashMap
HashMap可以说是面试的重中之重,去10家公司面试,8家都会问道,为什么大家都爱用HashMap打开话题?
Java识堂
2020/03/17
4560
去哪面试都会问的HashMap
一文搞定HashMap的实现原理和面试
HashMap在日常开发中基本是天天见的,而且都知道什么时候需要用HashMap,根据Key存取Value,但是存和取的时候那些操作却是很少去研究。同时在面试中也是面试官们必问的。以下是基于JDK1.8
秃头哥编程
2019/06/19
7540
手撕HashMap
在我扒拉那么多大厂面试题目后,发现HashMap的出现频率是非常高的,当然也会拿出一些类似的进行对比解析,比如HashTable、ConCurrentHashMap、LinkedHashMap,不着急我们后面慢慢聊它们。在讲HashMap前我们先简单回忆一下Hash的相关内容。
东边的大西瓜
2022/05/05
2340
手撕HashMap
基于JDK8的HashMap详解
HashMap是程序员使用频率较高的一种用于映射(键值对)处理的数据类型,随着JDK(Java Development Kit)版本的更新,HashMap也在不断被优化。其中JDK1.8在HashMap底层引入了红黑树的数据结构并对其扩容进行了优化等。本文将结合JDK1.7与JDK1.8对HashMap进行分析,浅析HashMap在JDK1.8中的改进。
Java阿呆
2020/11/04
4260
基于JDK8的HashMap详解
推荐阅读
相关推荐
HashMap&ConcurrentHashMap&HashTable
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档