全国旗舰校区

不同学习城市 同样授课品质

北京

深圳

上海

广州

郑州

大连

武汉

成都

西安

杭州

青岛

重庆

长沙

哈尔滨

南京

太原

沈阳

合肥

贵阳

济南

下一个校区
就在你家门口
+
当前位置:首页  >  技术干货  >  大数据技术干货  >  详情

java底层hashmap扩容怎么实现?

来源:千锋教育
发布人:qyf
2022-11-08

推荐

在线提问>>

java底层hashmap扩容怎么实现

  第一:java底层 hashmap扩容怎么实现

  答:可是当哈希表接近装满时,因为数组的扩容问题,性能较低(转移到更大的哈希表中).

  Java默认的散列单元大小全部都是2的幂,初始值为16(2的4次幂)。假如16条链表中的75%链接有数据的时候,则认为加载因子达到默认的0.75。HahSet开始重新散列,也就是将原来的散列结构全部抛弃,重新开辟一个散列单元大小为32(2的5次幂)的散列结果,并重新计算各个数据的存储位置。以此类推下去.....

  负载(加载)因子:0.75.-->hash表提供的空间是16 也就是说当到达12的时候就扩容

  第二:hashtable和currenthashmap的原理

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

  hashtable实现:

  底层数组+链表实现,无论key还是value都**不能为null**,线程**安全**,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低,ConcurrentHashMap做了相关优化

  初始size为11,扩容:newsize = olesize*2+1

  计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length

  Java5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。concurrentHashMap的原理:

  底层采用分段的数组+链表实现,线程安全

  通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。)

  Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术

  有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁

  扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容

  concurrentMap和hashtable比较:

  ConcurrentHashMap是使用了锁分段技术来保证线程安全的。

  锁分段技术:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

  ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表,从而在同一时刻只能由一个线程对其进行操作;而ConcurrentHashMap中则是一次锁住一个桶。

  ConcurrentHashMap默认将hash表分为16个桶,诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样,原来只能一个线程进入,现在却能同时有16个写线程执行,并发性能的提升是显而易见

相关文章

hadoop搭建完全分布式

spark和hadoop的区别

redis数据类型有几种

hadoop的核心是哪两部分

spark有什么用

开班信息 更多>>

课程名称
全部学科
咨询

HTML5大前端

Java分布式开发

Python数据分析

Linux运维+云计算

全栈软件测试

大数据+数据智能

智能物联网+嵌入式

网络安全

全链路UI/UE设计

Unity游戏开发

新媒体短视频直播电商

影视剪辑包装

游戏原画

    在线咨询 免费试学 教程领取