Java集合类主要由两个接口Collection和Map派生出来的，Collection有三个子接口：List、Set、Queue。

Collection：最基本的集合接口，代表一组元素的集合。

List：代表有序的、可重复的元素。
Set：代表不可重复的的集合。
Queue： 代表队列

Map：存储键值对的集合，键不允许重复。

List 、Set、Queue、Map的区别

List：

基于索引的集合，可以包含重复的元素。
支持元素的有序存储，即元素插入的顺序就是它们在列表中的顺序。
允许对元素进行快速随机访问。
常见的实现类有 ArrayList、LinkedList

Set:

不包含重复元素的集合。
通常不保证元素的顺序，或者保证元素按照某种规则排序（如 TreeSet）。
HashSet 是基于哈希表实现的，不保证元素顺序；LinkedHashSet 维护元素插入的顺序；TreeSet 则根据元素的自然顺序或构造时提供的比较器对元素进行排序。
常见的实现类有 HashSet、LinkedHashSet 和 TreeSet。

Queue：

队列是一种特殊的集合，主要用于维护元素的顺序。通常按照先进先出（FIFO）的原则进行元素的插入和移除。
支持元素的插入和移除操作，如 offer、poll、peek 等
常见的实现类有LinkedList（先进先出FIFO）、PriorityQueue（优先队列）和 ArrayDeque。

Map

存储键值对的集合，每个键最多只能映射到一个值。
键必须唯一，而值可以重复。
不保证元素的顺序，或者可以按照键或值的某种规则排序（如 TreeMap）。
常见的实现类有 HashMap、LinkedHashMap、TreeMap

ArrayList与LinkedList的区别

1.底层数据结构：ArrayList基于动态数组实现；LinkedList基于（双向）链表实现。
2.随机索引访问：ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素；LinkedList要移动指针遍历每个元素直到找到为止。
3.新增和删除元素：LinkedList的速度要优于ArrayList。因为ArrayList在新增和删除元素时，可能移动其它元素、扩容和复制数组；LinkedList除了实例化对象需要时间外，只需要修改指针即可。（LinkedList新增删除元素比ArrayList快的两个前提：1 往集合中间插入数据时ArrayList比linkedList慢 2 ArrayList正好扩容的时候添加数据要比LinkedList慢）
4.内存占用：ArrayList占用比LinkedList小，因为LinkedList的每个元素都需要存储额外的指针（prev 和 next）
5.线程安全：ArrayList与LinkedList都是非同步的，说明是非线程安全的，

Arraylist 和 Vector 的区别

ArrayList在内存不够时，默认是1.5被扩展，Vector是默认扩展1倍。
ArrayList是非同步的。Vector是同步的，属于线程安全级别的。由于 Vector 的同步机制，它在性能上通常比 ArrayList 慢。
通常建议使用 ArrayList，因为它提供了更好的性能，并且在需要线程安全时，可以通过Collections.synchronizedList() 方法或使用 CopyOnWriteArrayList 类来实现。

HashMap

HashMap是一个散列表，它存储的内容是键值对(key-value)映射，根据键的HashCode值存储数据。HashMap 使用数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的， 链表长度大于8（TREEIFY_THRESHOLD）时，会把链表转换为红黑树，红黑树节点个数小于6（UNTREEIFY_THRESHOLD）时才转化为链表，防止频繁的转化。

哈希表

哈希表也称为散列表，是一种通过哈希函数将键（Key）映射到表中一个位置以便快速访问记录的数据结构。

hash算法

在HashMap 实现中，hash算法是用来计算键的哈希码并将其映射到内部数组的索引上。以下是其核心：

第一步，获取key的hash

h = key.hashCode()

第二步，计算hashmap的hash

hash =(h = key.hashCode()) ^ (h >>> 16)

第三步，计算槽位（数组下标）。n是Node<K,V>[] table哈希桶数组的长度。

i = (n – 1) & hash

示例：
hashcode是int型。提前了解，十进制转二进制，位运算符。

假设
第一步：h=10，
第二步：hash=10^(10>>>16)。

>>>是无符号右移运算。10的二进制是0000000000000000 0000000000001010。那么10>>>16，右移16位意味着丢弃最低的16位，结果是0。
^是异或运算，10^0结果还是10。

第三步：i = (n – 1) & hash

&是与运算。n默认是16。i=(16-1)&10结果是10。

因为第二步是取hashcode丢弃最低的16位的结果与hashcode进行按位异或运算，所以又被称为高16位运算。
因为10&(16-1)=10%16，所以第三步又被称为取模运算。
计算机中直接求余效率不如位移运算，hash%length==hash&(length-1)的前提是length是2的n次方，能均匀分布减少碰撞。

源码解析可以查看HashMap的put方法

扩容机制（请阅读HashMap的resize方法）

数组扩容
当hashmap中的元素超过阈值（当前容量与负载因子的乘积），触发扩容。
通过创建一个2倍当前容量的新数组，替换原数组来完成扩容。
在此过程中需要重新计算每个键的哈希值，键值对需要重新映射。

链表扩容
当链表长度超过一定阈值（TREEIFY_THRESHOLD，默认为8）时，链表会被转换为红黑树。
当红黑树节点个数小于6（UNTREEIFY_THRESHOLD）时，红黑树会被转化为链表。

红黑树

红黑树是一种自平衡的二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。它具有以下特性:

1.节点颜色：每个节点要么是红色，要么是黑色。
2.根节点：根节点是黑色的。
3.叶子节点：所有叶子节点（NIL节点，空节点）都是黑色的。
4.红色节点的子节点：每个红色节点的两个子节点都是黑色的（不能有两个连续的红色节点）。
5.路径黑色节点数：从根节点到任意叶子节点的路径上，黑色节点的数量相同。

可结合HashMap里的TreeNode类理解。

HashMap和HashTable的区别

HashMap 和 Hashtable 都是 Java 中用于存储键值对的集合类，以下是它们的一些区别：

继承关系：

Hashtable 继承自 Dictionary 类，而 Dictionary 类是 Java 的早期版本中的一个类，现在已经不推荐使用。
HashMap 继承自 AbstractMap 类

线程安全性：

Hashtable 是线程安全的，它的所有公共方法都是同步的，这意味着在多线程环境中，Hashtable 可以安全地使用而不需要额外的同步措施。
HashMap 是非线程安全的，如果在多线程环境中使用，需要外部同步或者使用 Collections.synchronizedMap 方法来包装它。

null 键和值：

Hashtable 不允许使用 null 作为键或值。
HashMap 允许使用一个 null 键和多个 null 值。

在实际应用中，由于 HashMap 提供了更好的性能和更灵活的使用方式，它通常是首选的 Map 实现。如果需要线程安全的 Map 实现，可以使用 ConcurrentHashMap，它是 Java 并发包中的一个线程安全 Map 实现，或者使用 Collections.synchronizedMap 方法来包装一个 HashMap。

HashMap与ConcurrentHashMap的区别

ConcurrentHashMap 和 HashMap 都用于存储键值对，以下是它们的以下区别：

线程安全性

ConcurrentHashMap 是线程安全的
HashMap 是非线程安全的

HashSet

HashSet 实现了 Set 接口，它不允许集合中有重复的元素，并且不保证集合的迭代顺序；

以下是 HashSet 的一些关键特性：

不允许重复：

HashSet 保证集合中每个元素都是唯一的。尝试添加已存在的元素将不会被添加。

无序：

HashSet 不保证元素的顺序，这意味着每次迭代 HashSet 时元素的顺序可能不同。

基于哈希表：

HashSet 内部使用哈希表实现，这使得添加、删除和查找元素的操作通常具有常数时间复杂度（即 O(1)）。

非同步：

HashSet 是非线程安全的。在多线程环境中，如果需要线程安全，可以使用 Collections.synchronizedSet 方法将其包装，或者使用 ConcurrentHashMap 作为替代。

当需要迭代顺序一致时，不应该使用 HashSet，而应该使用 LinkedHashSet。

TreeSet

TreeSet 实现了 Set 接口，它不允许集合中有重复的元素，并且保证了元素处于排序状态。TreeSet 基于红黑树（一种自平衡的二叉搜索树）实现，这使得它能够提供有序的数据集合。

以下是 TreeSet 的一些关键特性和用法：

不允许重复：

TreeSet 不允许插入重复的元素。如果尝试添加已存在的元素，该元素不会被添加。

有序：

TreeSet 保证了元素的迭代顺序是有序的，这使得它适合需要有序数据的场景。

性能：

TreeSet 的查找、插入和删除操作通常具有 O(log n) 的时间复杂度，其中 n 是集合中的元素数量。

线程安全性：

TreeSet 是非线程安全的。在多线程环境中，如果需要线程安全，可以使用 Collections.synchronizedSortedSet 方法将其包装，或者使用 ConcurrentSkipListSet。

TreeMap

TreeMap 实现了 Map 接口，它存储键值对并保证了键处于排序状态。TreeMap 基于红黑树（一种自平衡的二叉搜索树）实现，这使得它能够提供有序的数据集合。

以下是 TreeMap 的一些关键特性和用法：

不允许重复键：

TreeMap 不允许插入重复的键。如果尝试添加已存在的键，那么旧的值将被新的值替换。

有序：

TreeMap 保证了键处于有序状态，并且保证了元素的迭代顺序是有序的，这使得它适合需要有序数据的场景。

性能：

TreeMap 的查找、插入和删除操作通常具有 O(log n) 的时间复杂度，其中 n 是映射中的元素数量。

线程安全性：

TreeMap 是非线程安全的。在多线程环境中，如果需要线程安全，可以使用 Collections.synchronizedMap 方法将其包装。

参考

Java集合框架体系
Java集合面试题
Java常见集合总结
Java集合框架全面解析
菜鸟教程：Java集合
java集合框架综述
ArrayList 和 LinkedList 的真正区别
Java 8的 HashMap 设计与实现
HashMap理解
深入理解HashMap(四): 关键源码逐行分析之resize扩容