栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java HashMap

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java HashMap

Java HashMap
  • 数据结构:
  • Java7 版本
    • 缺陷:
  • Java8 版本
    • 考点:
      • 为什么容量是2的幂?
      • 一个对象是如何被映射到哈希桶的?
      • HashMap的容量/负载因子/变树的阈值/恢复成链表的阈值
      • Java8的实现中HashMap 哈希桶里面的链表什么时候会变成红黑树?
      • Java8对Java7进⾏了什么改进?
      • 线程安全问题?

数据结构:
  • 是一个经典的哈希表的实现.
  • Java7 哈希桶+链表
  • Java8 哈希桶+链表+红黑树
  • 插入/查找/删除操作时间复杂度是O(1)
  • 缺陷:哈希值的碰撞(退化链表)
Java7 版本

数据结构:哈希桶+链表
初始容量(16)
负载因子(0.75 四分之三)
哈希算法(根据hashCode值计算出放到哪个哈希桶里面,防止碰撞)
扩容:容量达到负载就会触发扩容,变为原来的两倍,重新哈希计算将原有的元素重新分配

缺陷:
  1. 非常容易碰到死锁,链表死循环(扩容后链表顺序会反转,并发容易导致链表成环 酷壳-hashmap 文章)
  2. 哈希值的碰撞:如果恰巧每个值都挂在同一个哈希桶的时候,hashmap就会退化成一个链表
    (有个安全漏洞,tomcat将http参数用hashmap存储,黑客可以精心构造一个请求参数,使得所有的参数哈希值都一样,一次让hashmap退化成链表,消耗系统cpu 漏洞名:CVE-2011-4858
Java8 版本

数据结构:哈希桶+链表+红⿊树
大幅度减轻线程安全问题:扩容时使用与插入顺序一致的方法

考点: 为什么容量是2的幂?
  1. 方便将哈希值映射到桶的编号 hash&(size-1) 容量减一后二进制数后面全是1,方便与哈希值&(按位与)后快速得到桶的编号

  2. 方便扩容原先的元素要么保持不变,要么被移动到旧index+旧桶大小的位置上

一个对象是如何被映射到哈希桶的?

hashCode -> rehash -> index

HashMap的容量/负载因子/变树的阈值/恢复成链表的阈值

初始16,永远2的幂/0.75(四分之三)/8/6

Java8的实现中HashMap 哈希桶里面的链表什么时候会变成红黑树?

当前桶容量大于8并且哈希桶数量超过64位的时候,小于等于6会转化回来

大于8 源码


小于等于6源码

Java8对Java7进⾏了什么改进?

更好的处理哈希碰撞(效率)
改进了扩容时的插⼊顺序(安全性)

线程安全问题?

Java7存在,Java8被大幅度减轻

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/963216.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号