说说HashMap 的底层实现

HashMap 底层实现是通过一个数组和链表/红黑树组成的。在 Java 中，HashMap 继承了 AbstractMap 类，实现了 Map 接口。

当我们向 HashMap 中 put 一个键值对时，会先将键通过哈希函数计算出一个对应的哈希值，然后将该键值对存储到数组的对应位置上。如果此时该位置上已经有键值对了，那么就会以链表的形式将该键值对添加到链表的末尾。

当链表长度超过一定值时，链表就会转化为红黑树，这是为了优化查找操作的时间复杂度。红黑树的查找操作时间复杂度为 O(log n)，而链表的查找操作时间复杂度为 O(n)。

在 Java 8 中，HashMap 的实现还引入了一个新的数据结构——红黑树，它可以更好地处理哈希冲突。当链表长度超过一定值时，会将链表转化为红黑树。这样可以将查找操作的时间复杂度从 O(n) 降低到 O(log n)。

HashMap 的实现还考虑了负载因子的问题，当 HashMap 中的元素数量达到数组长度的 75% 时，就会触发扩容操作，将数组的长度扩大为原来的两倍，并将元素重新散列到新的数组中。这样可以保证 HashMap 的性能和空间利用率。