【JAVA】HashMap详解

一.实现

JDK7采用数组+链表。
JDK8采用数组+链表、红黑树。

二.知识点

  1. 初始容量为2^4=16。
  2. 负载因子为0.75
  3. JDK1.8开始,一个桶存储的链表长度大于8时会将链表转化成红黑树。
  4. 确定桶的下标:hashcode & (length – 1),length为当前容量,按位与操作。
  5. JDK7的链表插入以头插法进行的(扩容后顺序会相反,JDK8保持顺序)。

三.扩容

  1. 何时扩容?
    默认键值对的数量大于等于(容量(桶)*负载因子)的个数时即扩容为原来的两倍。

  2. 实现过程
    扩容使用resize()实现,扩容操作把oldTable的所有键值对重新插入newTable中。
    扩容的时候需要重新计算桶的下标,容量(桶)为2的n次方极大降低桶下标操作的复杂度。对于一个key,16扩容为32只需看第五位,为0不变,为1+16。

五.问题

  1. 用户传入的初始容量不为2的n次方。
    HashMap可以自动地将传入的容量转换为2的n次方。

  2. 为什么数组的长度一定为2的n次方?
    只有长度为2的n次方的时候,我们对它减1才能拿到全部为1的二进制,这样才能在按位与操作中非常快速的拿到下标,并且分布也是均匀的。

  3. Java7d HashMap有哪些问题?
    1) 非常容易死锁,多线程扩容导致链表的值互相指向(头插法导致的),然后在查询的时候无此元素循环导致死锁(环形链表导致CPU100%)。
    2) 潜在的安全隐患:可以通过精心构造的恶意请求引发Dos。链表的性能退化(产生大量链表,消耗大量cpu)。
    3) 为什么大于8才能转换成红黑树?
    根据泊松分布计算,参数为0.5,超过8的时候概率非常的小。

六.ConcurrentHashMap

线程安全的HashMap。

  1. HashTable通过使用Synchronized修饰方法的方式来实现多线程同步,因此,HashTable的同步会锁住整个数组,性能在高并发情况下非常差。
  2. ConcurrentHashMap采用锁分离技术,对应的put、remove等操作也只需要锁住当前线程需要用到的桶,而不需要锁住整个数据。
  3. JDK1.7采用Segment分段锁,1.8采用CAS+Synchronized来保证并发安全性。
  4. ConcurrentHashMap的Hash链中除了变量value外,其他变量都被定义为final类型,保证不加锁读取到一致的数据。(HashEntry链表)

七.参考视频

https://www.bilibili.com/video/BV18E411C7kD
https://www.bilibili.com/video/BV1T54y1B7rV?p=37

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇