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