- HashMap底层数据结构，设计原因？
答：JDK 1.8，底层是由“数组+链表+红黑树”组成，JDK 1.8 之前是由“数组+链表”组成。
原因主要是为了提升在 hash 冲突严重时（链表过长）的查找性能，使用链表的查找性能是 O(n)，而使用红黑树是 O(logn)。
- 什么时候使用链表和红黑树？
答：插入时：默认使用链表，节点超过8个时：如果数组长度大于等于64，触发链表节点转换成红黑树节点；数组长度小于64，不会触发链表转红黑树，会进行扩容。
删除时：当一个节点数少于6个时并且该节点为红黑树节点，会触发红黑树节点转链表节点。
- 为什么是转换发生在“8”和“6”？
答：a). 方案设计时，综合考虑空间和时间的结果，红黑树的查找效率高，占用内存更多点，且数据结构更复杂，链表查找效率低。
b). 理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的公式计算，链表中节点个数为8时的概率为 0.00000006, 这个概率足够低了，并且到8个节点时，红黑树的性能优势也会开始展现出来，因此8是一个较合理的数字。
c).如果我们设置节点多于8个转红黑树，少于8个就马上转链表，当节点个数在8徘徊时，就会频繁进行红黑树和链表的转换，造成性能的损耗。所以删除时少于6才会发生红黑树到链表的转换.
- HashMap有哪些重要属性？
答：a). size: HashMap已经存储的节点个数；
b). threshold: 扩容阈值，当HashMap的个数达到该值，触发扩容；
c). loadFactor: 负载因子，扩容阈值=容量*负载因子。
- threshold 除了用于存放扩容阈值还有其他作用吗？
答：在我们新建 HashMap 对象时， threshold 还会被用来存初始化时的容量。HashMap 直到我们第一次插入节点时，才会对 table 进行初始化，避免不必要的空间浪费。
- HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？
答：默认初始容量是16。HashMap 的容量必须是2的N次方，HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方，例如传 9，容量为16。
- HashMap的插入流程
- HashMap的实现，concurrentHashMap
若有收获，就点个赞吧
0 人点赞
