Java 中有哪些集合类？

Java 中的集合类主要分为两大类：Collection 接口和 Map 接口。Collection 接口下又分为 List、Set 和 Queue 接口。每个接口有其具体实现类。以下是主要的集合类：

List 接口：

  • ArrayList：基于动态数组，查询速度快，插入、删除慢。
  • LinkedList：基于双向链表，插入、删除快，查询速度慢。
  • Vector：线程安全的动态数组，类似于 ArrayList，但开销较大（加了synchronized ）。
  • CopyOnWriteArrayList：线程安全的动态数组，但所有可变操作（如 add()、set() 等）都会创建一个新的数组（写实复制）。

Set 接口：

  • HashSet：基于哈希表，元素无序，不允许重复。
  • LinkedHashSet：基于链表和哈希表，维护插入顺序，不允许重复。
  • TreeSet：基于红黑树，元素有序，不允许重复。

所以网上有些说 Set 是无序集合非常不准确，因为需要看具体的实现类。

Queue 接口：

  • PriorityQueue：基于优先级堆，元素按照自然顺序或指定比较器排序。
  • LinkedList：可以作为队列使用，支持 FIFO（先进先出）操作。

Map 接口：

  • HashMap：基于哈希表，键值对无序，不允许键重复。
  • LinkedHashMap：基于链表和哈希表，维护插入顺序，不允许键重复。
  • TreeMap：基于红黑树，键值对有序，不允许键重复。
  • Hashtable：线程安全的哈希表，不允许键或值为 null。
  • ConcurrentHashMap：线程安全的哈希表，适合高并发环境。

Java 中 HashMap 的实现原理是什么？

HashMap 基于哈希表的数据结构实现，允许存储键值对，并且通过键快速访问对应的值。

它内部使用数组和链表（在 Java 8 及以后还可以使用红黑树）来存储元素，每个数组槽位（bucket）对应一个链表或红黑树。

数组内的元素保存了 key 和 value。当要塞入一个键值对的时候，会根据一个 hash 算法计算 key 的 hash 值，然后通过数组大小 n-1 & hash 值之后，得到一个数组的下标，然后往那个位置塞入这键值对。

为了解决键值对冲突的问题，采用了链表法，如下图所示：

在 JDK1.7 及之前链表的插入采用的是头插法，即在链表的头部插入新的键值对。

在 JDK1.8 的时候，改成了尾插法，并且引入了红黑树。

当链表的长度大于 8 且数组大小大于等于 64 的时候，就把链表转化成红黑树，当红黑树节点小于 6 的时候，又会退化成链表。

Java 中 HashMap 的扩容机制是怎样的？

在 HashMap 中有阈值的概念，比如我们设置一个 16 大小的 map，那么默认的阈值等于 16 * 0.75 = 12。

也就是说，如果 map 中元素的数量超过 12，那么就会触发扩容。

扩容的时候，默认会新建一个数组，新数组的大小是老数组的两倍。

然后将 map 内的元素重新 hash 映射搬运到新的数组中。

因为数组的长度是 2 的 n 次方，所以假设以前的数组长度（16）二进制表示是 010000，那么新数组的长度（32）二进制表示是 100000，这个应该很好理解吧？

它们之间的差别就在于高位多了一个 1，而我们通过 key 的 hash 值定位其在数组位置所采用的方法是 (数组长度-1) & hash（与运算）。我们还是拿 16 和 32 长度来举例：

16-1=15，二进制为 001111
32-1=31，二进制为 011111

所以重点就在 key 的 hash 值的从右往左数第五位是否是 1，如果是 1 说明需要搬迁到新位置，且新位置的下标就是原下标+16（原数组大小），如果是 0 说明吃不到新数组长度的高位，那就还是在原位置，不需要迁移。

所以，我们刚好拿老数组的长度（010000）来判断高位是否是 1，这里只有两种情况，要么是 1 要么是 0 。

为什么 HashMap 在 Java 中扩容时采用 2 的 n 次方倍？

哈希分布均匀性

如果数组容量为 2 的 n 次方，那么 n - 1 后低位都是 1 ，此时进行 & （两个位都为 1 时，结果才为 1）运算可以确保哈希码的最低几位均匀分布。

比如 64 二进制表示为 0100 0000，64 - 1 = 0011 1111。

此时 0011 1111 与哈希码进行 & 运算，低位能均匀的反应出哈希码的随机性。

假设来个 0100 0000 与哈希码进行 & 运算，那么低位得到的值就都是 0 了，随机性很差，都是冲突。

性能

正常情况下，如果基于哈希码来计算数组下标，我们想到的都是 %（取余）计算。例如数组长度为 5 ，那么哈希码 % 5 得到的值就是对应的数组下标。

但相比于位运算而言，效率比较低，所以推荐用位运算，而要满足 i = (n - 1) & hash 这个公式，n 的大小就必须是 2 的 n 次幂。即：当 b 等于 2 的 n 次幂时，a % b 操作等于 a & ( b - 1 )

为什么 Java 中 HashMap 的默认负载因子是 0.75？

设置 0.75 是因为空间和时间上的平衡。

较低的负载因子（例如 0.5）会导致 HashMap 需要频繁扩容，空间利用率就低。不过因为冲突少，查找效率就高，但是因为扩容频繁会增加 rehashing 的开销。

较高的负载因子（例如 1.0）会减少扩容次数，空间利用率高了，但会增加哈希冲突的概率，从而降低查找效率。

经过大量实践，0.75 被认为是大多数场景下比较合适的值，能够在时间和空间之间取得良好的平衡。

所以设置了 0.75。

JDK 1.8 对 HashMap 进行了哪些改动？（不含红黑树）

主要有以下几个方面：

  1. hash 函数的优化
  2. 扩容 rehash 的优化
  3. 头插法和尾插法
  4. 插入与扩容时机的变更

hash 函数的优化

1.7 的操作太多了，经历了四次异或，所以 1.8 优化了下，它将 key 的哈希码的高 16 位和低 16 位进行了异或，得到的 hash 值同时拥有了高位和低位的特性，使得哈希码的分布更均匀，不容易冲突。

扩容 rehash 的优化

按照我们的思维，正常扩容肯定是先申请一个更大的数组，然后将原数组里面的每一个元素重新 hash 判断在新数组的位置，然后一个一个搬迁过去。

在 1.7 的时候就是这样实现的，然而 1.8 在这里做了优化，关键点就在于数组的长度是 2 的次方，且扩容为 2 倍。

在扩容过程中，节点被分布到新的桶中时，不再需要重新计算 hash，而是利用了原桶的位置和新桶的二进制位关系，来快速确定新桶的位置。

头插法和尾插法

1.7 是头插法，头插法的好处就是插入的时候不需要遍历链表，直接替换成头结点，但是缺点是扩容的时候会逆序，而逆序在多线程操作下可能会出现环，然后就死循环了。

然后 1.8 是尾插法，每次都从尾部插入的话，扩容后链表的顺序还是和之前一致，所以不可能出现多线程扩容成环的情况。

插入与扩容时机的变更

1.7 是先判断 put 的键值对是新增还是替换，如果是替换则直接替换，如果是新增会判断当前元素数量是否大于等于阈值，如果超过阈值且命中数组索引的位置已经有元素了，那么就进行扩容。

所以 1.7 是先扩容，然后再插入。

而 1.8 则是先插入，然后再判断 size 是否大于阈值，若大于则扩容。

为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

主要是避免 hash 冲突导致链表的长度过长，这样 get 的时候时间复杂度严格来说就不是 O(1) 了，因为可能需要遍历链表来查找命中的键值对。

那么为什么定义链表长度为 8 且数组大小大于等于 64 才转红黑树？不要链表直接用红黑树不就得了吗？

因为红黑树节点的大小是普通节点大小的两倍，所以为了节省内存空间不会直接只用红黑树，只有当节点到达一定数量才会转成红黑树，这里定义的是 8。

为什么是 8 呢？这个其实 HashMap 注释上也有说的，和泊松分布有关系。

简单翻译下就是在默认阈值是 0.75 的情况下，冲突节点长度为 8 的概率为 0.00000006，也就概率比较小（毕竟红黑树耗内存，且链表长度短点时遍历的还是很快的）。

这就是基于时间和空间的平衡了，红黑树占用内存大，所以节点少就不用红黑树，如果万一真的冲突很多，就用红黑树，选个参数为 8 的大小，就是为了平衡时间和空间的问题。

为什么节点小于等于 6 要从红黑树转成链表？

链表树化的节点是 8，除此之外，当树节点数小于等于 6 时候，又会从红黑树转为链表。

这个操作是为了平衡时间和空间，节点太少链表遍历也很快，没必要成红黑树，变成链表节约内存。

为什么定了 6 而不是小于等于 8 就变？

是因为要留个缓冲余地，避免反复横跳。举个例子，一个节点反复添加，从 8 变成 9 ，链表变红黑树，又删了，从 9 变成 8，又从红黑树变链表，再添加，又从链表变红黑树？

所以余一点，毕竟树化和反树化都是有开销的。

使用 HashMap 时，有哪些提升性能的技巧？

1）合理设置初始容量：

如果在使用时可以预估 HashMap 存储的数据量大小，那么需要在创建时设置一个合适的初始容量，以避免频繁的扩容操作。

Java 中 HashMap 默认初始容量是 16。

2）调整负载因子：

官方提供的默认负载因子是 0.75。

可以根据具体应用场景调整这个值。较低的负载因子会减少冲突，提高查找效率，但会占用更多内存。较高的负载因子则会减少内存消耗，但可能增加冲突的概率，降低查找效率。

3）确保 hashCode 均匀分布：

对应 key 的 hashCode() 方法生成的哈希值需均匀分布，减少哈希冲突。避免使用质量不高的哈希函数，防止大量键映射到相同的槽位上，造成性能瓶颈。

其他优化

例如需要保留元素的插入顺序，则可以使用 LinkedHashMap替换 HashMap。它基于 HashMap 但维护了一个链表，记录元素的插入顺序。

这样就不需要我们从 HashMap 中获取数据，然后再排序。

如果是需要保留有序的键值对，则可以使用 TreeMap。

如果是线程安全场景，则可以使用 ConcurrentHashMap。

Java 中的 HashMap 和 Hashtable 有什么区别？

线程安全性

HashMap：不是线程安全的。如果多个线程同时访问一个 HashMap，并且至少有一个线程在结构上修改了它（比如添加或删除键值对），可以通过以下代码封装进行同步：

Map<String, String> map = Collections.synchronizedMap(new HashMap<>());

Hashtable：是线程安全的。所有的方法都加了锁，可以在多线程环境中使用。

性能

HashMap：由于没有同步开销，所以它的性能一般比 Hashtable 更好，尤其是在单线程环境中。

Hashtable：由于每个方法都进行同步，因此性能比 HashMap 差。

null 值的处理

HashMap：允许一个 null 键和多个 null 值。

HashMap<String, String> map = new HashMap<>();
map.put(null, "value");
map.put("key", null);

Hashtable：不允许 null 键和 null 值。如果将 null 键或值放入 Hashtable，会抛出 NullPointerException。

Hashtable<String, String> hashtable = new Hashtable<>();
// hashtable.put(null, "value"); // 抛出 NullPointerException
// hashtable.put("key", null); // 抛出 NullPointerException

其他

HashMap：默认初始容量为 16，负载因子为 0.75。使用 Iterator 遍历键值对，支持 fail-fast 机制，如果在遍历过程中结构发生变化，会抛出 ConcurrentModificationException

Hashtable：默认初始容量为 11，负载因子为 0.75。使用 Enumeration 遍历键值对，不支持 fail-fast 机制。

Hashtable 其实是过期的类，如果真的需要线程安全的容器，现在也都用 ConcurrentHashMap，因为它的加锁粒度更低，性能更好，Hashtable 基本没有使用场景。

Java 中的 HashSet 和 HashMap 有什么区别？

HashSet 其实内部的实现还是 HashMap！

从上图我们可以发现，构造一个 HashSet 内部就是 new 了一个 HashMap，并且 add 方法实际上调用的就是 HashMap 的 put。

因此 HashSet 就是封装了一下 HashMap！内部的实现逻辑其实都由 HashMap 来代劳。