HashMap 与 HashTable的对比

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()方法来判断是否含有某个键。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Felix的技术分享

KMP子字符串查找算法

29660
来自专栏小狼的世界

Ruby学习笔记

Ruby语言中,以对象为基本单位,可以说所有的元素都是对象。按照之前对于面向对象程序的理解,对象是指包含了特定属性和方法集合的一组程序。对象由类来定义,具体的表...

9720
来自专栏飞雪无情的博客

从Java到Golang快速入门

Golang从09年发布,中间经历了多个版本的演进,已经渐渐趋于成熟,并且出现了很多优秀的开源项目,比如我们熟知的docker,etcd,kubernetes等...

14230
来自专栏JackeyGao的博客

关于Python的20个面试题

Python 是一个高级、解释型、交互式和面向对象的脚本语言. Python 语言设计具有高度可读性的, 使用一些常见的英语词组和其他语言常用的标点符号组成的语...

18210
来自专栏海天一树

图的广度优先搜索

广度优先搜索算法是最简便的图的搜索算法之一,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索...

16430
来自专栏Python小屋

Python花式编程案例锦集(1)

首先解答上一篇文章详解Python中的序列解包(2)中最后的习题,该题答案为5,表达式功能为迭代求解序列中元素的最大值。 -----------------分割...

42850
来自专栏博岩Java大讲堂

关于Java泛型"擦除"的一点思考

38750
来自专栏Ryan Miao

java基础面试题

参考:http://blog.csdn.net/jackfrued/article/details/44921941 说未经允许不转载,我只好参考了。 1.面向...

38150
来自专栏禅林阆苑

LESS 学习demo 【原创】

LESS 学习demo Write By CS逍遥剑仙 我的主页: www.csxiaoyao.com GitHub: github.com/...

41290
来自专栏java架构师

【SQL Server】系统学习之三:逻辑查询处理阶段-六段式

一、From阶段 针对连接说明: 1、笛卡尔积 2、on筛选器 插播:unknown=not unknuwn 缺失的值; 筛选器(on where having...

372110

扫码关注云+社区

领取腾讯云代金券