HashMap

基础

  1. 数组+链表+红黑树
  2. 初始值默认为16,重载因子为0.75f
  3. 每次扩容为原来的两倍
  4. 非线程安全

进阶

1.为什么1.8中数量到8后会转为treeNode结构

时间和空间的权衡考虑,正常情况下,链表元素超过8的概率为百万分之一,因为不能阻止别人实现性能查的hash算法,如果hash算法离散型很差,那么链表元素将大概率超过8,此时转换为树结构提升查询效率比较合理。

2.为什么初始容量要设为8?

初始容量固定为2的n次方,原因是hashmap计算元素落到哪个数组位置时,是通过hash值 & 容量得出。

3.为什么hashmap是线程不安全的?

两个线程同时put,put要先计算当前元素应该落在哪个桶内(数组),然后再插入到链表中,如果此时cpu切片,导致两个线程都计算出落在同一个桶,并且同时插入到链表中,那就会导致其中的一个线程更新的值被覆盖。

4.hashmap的hash算法

获取key的hash值,hash值右移16位,然后与原hash进行异或操作(这样可以让高位参与到hash运算中),最后与容量-1进行与操作

5.为什么使用1.7头插法,会产生什么问题

因为后插入的可能会被更多使用,会导致并发扩容时链表倒置,产生环境链表,1.8已使用尾插法

红黑树

特点:

  1. 根节点是黑色
  2. 节点是红色或黑色
  3. 每个叶子节点是黑色(null节点)
  4. 从任一节点到每个叶子节点,到包含相同数目的黑色节点