HashMap底层是如何实现的？

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。

所以在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过8的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度O（log n），可以提高查询性能，但是在数量较少时，即数量小于6时，会将红黑树转换回链表。

追问：哈希冲突如何解决，链表转红黑树的条件是什么？

HashMap 哈希冲突是通过拉链法来解决的，当有新的键值对要插入到HashMap中时，会先计算键的哈希值，然后根据哈希值确定在数组中的位置。如果该位置已经有元素了，就会将新的元素插入到该位置的链表尾部（在 Java 8 及之后的版本中，当链表长度达到一定阈值时会转换为红黑树）。这样，同一个位置上的多个元素就通过链表（或红黑树）的方式连接起来，从而解决了哈希冲突。

当链表的长度大于等于 8 时，并且HashMap的容量大于等于 64，会将链表转换为红黑树。这是因为当链表长度较长时，查找、插入和删除操作的时间复杂度会退化为On，而红黑树可以将这些操作的时间复杂度保持在O(logn)，从而提高了性能。

追问：HashMap进行插入、删除等操作的时间复杂度是什么？

不存在哈希冲突时：

• 插入一个键值对只需要根据哈希值直接定位到对应的数组位置，然后将元素插入即可，时间复杂度为O(1)。
• 类似插入操作，在没有哈希冲突的情况下，通过哈希值可以直接找到要删除的元素所在位置，然后进行删除，时间复杂度也是O(1)。

存在哈希冲突时，采用链地址法解决冲突且为「链表」结构：

• 当发生哈希冲突，新元素需要插入到链表中时，如果插入操作是在链表头部进行（如 Java 中的 HashMap 在链表未树化时采用头插法），时间复杂度为O(1)。；如果是在链表尾部插入，则需要遍历链表找到尾部节点，时间复杂度为O(n)。n 为链表的长度。
• 需要遍历链表找到要删除的节点，然后进行删除操作，平均时间复杂度为O(n)。

存在哈希冲突时，采用链地址法解决冲突且为「红黑树」结构：

• 红黑树的插入操作需要进行一系列的平衡调整操作，以保持红黑树的性质，时间复杂度为O(logn)，n 为红黑树的节点数。
• 删除操作也可能会引发红黑树的平衡调整，时间复杂度同样为O(logn)。

追问：链表和红黑树在其中的性能表现如何？相较于链表，红黑树有哪些优势？

• 当哈希冲突较少，链表长度较短时，链表的插入、删除和查找操作相对简单，空间开销也较小，性能表现较好。
• 当哈希冲突严重，链表长度较长时，链表的查找、插入和删除操作时间复杂度会退化为 O(n)，性能显著下降。此时，红黑树的O(logn) 时间复杂度优势就会凸显出来，能够提供更高效的操作。

final关键字在Java中有什么作用？

final关键字主要有以下三个方面的作用：用于修饰类、方法和变量。

• 修饰类：当final修饰一个类时，表示这个类不能被继承，是类继承体系中的最终形态。例如，Java 中的String类就是用final修饰的，这保证了String类的不可变性和安全性，防止其他类通过继承来改变String类的行为和特性。
• 修饰方法：用final修饰的方法不能在子类中被重写。比如，java.lang.Object类中的getClass方法就是final的，因为这个方法的行为是由 Java 虚拟机底层实现来保证的，不应该被子类修改。
• 修饰变量：当final修饰基本数据类型的变量时，该变量一旦被赋值就不能再改变。例如，final int num = 10;，这里的num就是一个常量，不能再对其进行重新赋值操作，否则会导致编译错误。对于引用数据类型，final修饰意味着这个引用变量不能再指向其他对象，但对象本身的内容是可以改变的。例如，final StringBuilder sb = new StringBuilder("Hello");，不能让sb再指向其他StringBuilder对象，但可以通过sb.append(" World");来修改字符串的内容。

本文内容来源微信公众号小林coding，仅个人学习使用，侵权请联系删除。