HashMap是基于哈希表的数据结构, 用于存储键值对(key-value).
其核心是将键的哈希值映射到数组索引位置, 通过数组 + 链表(JDK8之后是数组 + 链表 + 红黑树)来处理哈希冲突.
HashMap使用键的hasCode方法计算哈希值, 并通过indexFor方法(JDK7移除了, 改用
(n-1) & hash)来确定元素在数组中的存储位置.哈希值是经过一定扰动处理的, 以防哈希值分布不均, 减少冲突.
HashMap初始容量默认为16, 负载因子0.75, 当元素元素数量超过容量*0.75时, 会进行Hash扩容, 容量翻倍, 扩容非常耗时.
扩展
HashMap的红黑树优化
从JDK8开始, 为了优化哈希冲突时的查询性能, 当链表长度达到8且数组长度达到64时, 链表会转化为红黑树.
红黑树是一种自平衡二叉搜索树, 能够降低最坏情况下的查找复杂度.
如果树中的元素低于6, 红黑树会转化为链表, 降低开销
hashCode()与equals()的重要性
HashMap的键必须实现hashCode()和equals()方法.
hashCode()用于计算哈希值, 决定键的存储位置
equals()用于比较两个键是否相等
两个键的hashCode相同, 但equals不等, 视为不同的键, 存储在同一个桶的不同位置, 例如: "重地"和"通话"
默认容量与负载因子的选择
默认容量为16, 负载因子为0.75, 这个组合是性能和空间的平衡
较高的负载因子会增加哈希冲突的概率
较低的负载因子会增加空间开销
如果已知HashMap的容量需求, 提前预设初始容量可以减少扩容带来的损耗
Hash冲突链表法相关源码
当要插入一个键值对时, 会根据一个hash算法计算key的hash值, 然后通过数组大小
(n - 1) & hash值之后, 得到一个数组下标, 然后往这个位置插入这个键值对.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
...
}hash算法可能产生冲突
在JDK8之前采用头插法, 新的节点总是插入到链表头部, 老节点向后移动, 形成新的链表
在多线程环境下可能产生环路, 因此在JDK8时改为尾插法, 并引入红黑树
扩展-ConcurrentHashMap
JDK8之前
在JDK8之前采用分段锁, 每个Segment独立, 可以并发访问不同的Segment
默认有16个Segment, 意味着最大支持16个线程并发执行
采用数组 + 链表
JDK8及之后
移除了Segment, 锁的粒度更细了, 锁只在链表或红黑树的节点级别上进行
通过CAS进行插入操作, 只有在更新链表或红黑树时才使用synchronized, 并且只锁住链表或红黑树的头节点, 进一步减少了锁竞争
采用数组 + 链表 + 红黑树