HashMap
2023-04-19 15:14:41 11 举报
AI智能生成
登录查看完整内容
HashMap常见问题
作者其他创作
大纲/内容
a.next = head,a = headb.next = head,b = head并发情况下a.next = b,b.next = a
头插法,并发情况下,可能产生循环链表
数据 + 双向链表
jdk1.7
尾插法
数组 + 单向链表 + 红黑树
jdk1.8
数据结构
存储键值对的对象,内含4个属性,hashcode、next指针、key和value
Entry
数组中每个元素会存储一个Entry
发生hash冲突的时候,才会使用链表或者红黑树
基础概念
因为负载因子过大容易产生hash冲突。负载因子过小扩容阈值降低,浪费空间。经过大量实验测试,0.75在时间和空间上取得了一个较好的平衡
负载因子为什么是0.75
负载因子0.75
数组默认长度16
数组扩容阈值 = 16 * 0.75 = 12
默认值
即不同的属性生成相同的hashcode,但是key和value是不同的
一个元素通过hash函数产生多个hash值,存入多个槽位中,有值的槽位赋值为1。当所有槽位都为1的时候,查询数据内容,如果任一为0,就没有数据误判率取决于模的长度和hash表的大小
布隆过滤器
一种将任意长度的消息压缩到一个固定长度的消息摘要的算法。
散列算法
在散列算法得到的哈希值的基础上,使用位运算对其进行进一步的扰动,以增加元素在哈希表中的分布均匀性,减少哈希冲突的发生率
扰动函数
jdk1.7 HashMap
把hash值在hash一次
再哈希法
当哈希冲突发生时,不使用链表或树等数据结构,而是直接找到下一个空槽存储冲突的数据
开放寻址法
jdk1.8 HashMap
发生hash冲突时,把冲突的元素往链表或者红黑树里面塞
链表法(拉链法)
解决方案
hash冲突
前置知识
链表长度为TREEIFY_THRESHOLD(8)并且数组长度为MIN_TREEIFY_CAPACITY(64)的时候转红黑树
链表 => 红黑树
树的根节点为nullremove操作时候,根节点的左/右节点为null,或者左节点的左节点为null上述满足其一时,也会转回链表,官方的注释是这样的判定条件下,认定树的节点很少
节点长度小于UNTREEIFY_THRESHOLD(6)
红黑树 => 链表
发生hash冲突的时候会使用链表
什么时候会使用到链表或者红黑树
前置知识:HashMap中的哈希表包含了数组和链表或红黑树这两种数据结构
链表长度为7的时候发生hash碰撞的概率是千万分之6
链表长度为8的时候发生hash碰撞的概率是亿分之3
泊松分布
链表时间复杂度O(N),红黑树时间复杂度O(logN)
链表长度为8
最小是32,所以临界值是32,64避免临界值
可以为其树化箱的最小表容量。(否则,如果箱中的节点过多,则会调整表的大小。应至少为 4 * TREEIFY_THRESHOLD(8)以避免调整大小和树化阈值之间的冲突
如果数组的容量小于64,则认为是哈希表太小,导致的hash冲突,这种情况下,会进行数组扩容,而不是转换红黑树
hashMapDemo.java
此处提供调试hashmap测试代码,通过重写hashcode提高碰撞率来供demo使用
数组长度为64
为什么链表长度为8并且数组长度为64的时候转红黑树
防止临界值导致链表和红黑树频繁的转化导致的性能损耗
为什么链表长度为6的时候转回链表
HashSet的key重复就跳过不操作,HashMap的Key重复就更新value
HashMap VS HashSet
ConcurrentHashMap线程安全,jdk1.7是分段锁。jdk1.8是桶级别的锁
个人感觉实际业务开发的场景使用其实蛮小的,实际业务中,大部分场景是单线程同步运行的即使遇到多线程的场景,可以也被包装成业务对象了
HashMap VS ConcurrentHashMap
HashMap
0 条评论
回复 删除
下一页