集合相关类和接口都在java.util中，主要分为3种：List（列表）、Map（映射）、Set(集)。

其中 Collection 是集合 List 、 Set 的父接口，它主要有两个子接口：

List ：存储的元素有序，可重复。
Set ：存储的元素无序，不可重复。

Map 是另外的接口，是键值对映射结构的集合。

List

ArrayList和LinkedList的区别是什么？它们的时间复杂度是怎样的？

ArrayList和LinkedList都是List接口的实现类，ArrayList是基于数组实现的，而LinkedList是基于双向链表实现的。

插入和删除是否受元素位置的影响：
- ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
- LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o)），时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。

另外，不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了，LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的时间复杂度都是 O(n) 。

ArrayList的扩容机制了解吗？

ArrayList是基于数组的集合，数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容。

ArrayList的扩容是创建一个1.5倍的新数组，然后把原数组的值拷贝过去。

ArrayList怎么序列化的知道吗？为什么用transient修饰数组？

ArrayList的序列化不太一样，它使用 transient 修饰存储元素的 elementData 的数组， transient 关键字的作用是让被修饰的成员属性不被序列化。

为什么最ArrayList不直接序列化元素数组呢？

出于效率的考虑，数组可能长度100，但实际只用了50，剩下的50不用其实不用序列化，这样可以提高序列化和反序列化的效率，还可以节省内存空间。
那ArrayList怎么序列化呢？

ArrayList通过两个方法readObject、writeObject自定义序列化和反序列化策略，实际直接使用两个流 ObjectOutputStream 和 ObjectInputStream 来进行序列化和反序列化。

快速失败(fail-fast)和安全失败(fail-safe)了解吗？

快速失败（fail—fast）：快速失败是Java集合的一种错误检测机制

在用迭代器遍历一个集合对象时，如果线程A遍历过程中，线程B对集合对象的内容进行了修改（增加、删除、修改），则会抛出ConcurrentModificationException。
原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如ArrayList 类。

安全失败（fail—safe）

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发ConcurrentModificationException。
缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如CopyOnWriteArrayList类。

有哪几种实现ArrayList线程安全的方法？

fail-fast是一种可能触发的机制，实际上，ArrayList的线程安全仍然没有保证，一般，保证ArrayList的线程安全可以通过这些方案：

使用 Vector 代替 ArrayList。（不推荐，Vector是一个历史遗留类）
使用 Collections.synchronizedList 包装 ArrayList，然后操作包装后的 list。
使用 CopyOnWriteArrayList 代替 ArrayList。
在使用 ArrayList 时，应用程序通过同步机制去控制 ArrayList 的读写。

CopyOnWriteArrayList了解多少？

CopyOnWriteArrayList就是线程安全版本的ArrayList。

它的名字叫 CopyOnWrite ——写时复制，已经明示了它的原理。

CopyOnWriteArrayList采用了一种读写分离的并发策略。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

Map

能说一下HashMap的数据结构吗？

JDK1.7的数据结构是数组 + 链表

JDK1.8的数据结构是数组 + 链表 + 红黑树 。

其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。

数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
如果链表长度>8&数组大小>=64，链表转为红黑树
如果红黑树节点个数<6 ，转为链表

红黑树

红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它可以保证在最坏情况下，基本的动态操作（插入、删除、查找）都可以在 O(log n) 时间内完成，是一种高效的数据结构。红黑树的名字来自于每个节点被标记为红色或黑色，以满足特定的约束。

红黑树的约束条件如下：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（NIL节点，空节点）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点，这个数目被称为该节点的黑色高度。

这些约束条件保证了红黑树的平衡性和搜索效率。通过这些约束条件，红黑树可以保证在最坏情况下，查找、插入和删除的时间复杂度都是 O(log n)。

红黑树的插入和删除操作会涉及到颜色变化和旋转操作，旋转操作有两种类型：左旋和右旋。左旋是将一个节点的右子树移到该节点的位置，而右旋是将一个节点的左子树移到该节点的位置。这些操作的具体实现可以根据红黑树的性质进行推导和实现。

总之，红黑树是一种自平衡的二叉查找树，通过颜色标记和旋转操作来保持树的平衡性和搜索效率。红黑树常用于各种编程语言和库的实现中，例如C++ STL的set和map容器，Java集合框架中的TreeMap和TreeSet，以及Linux内核中的进程调度和文件系统实现等。

如何遍历一个HashMap？

遍历HashMap有以下几种方法：

迭代器（Iterator）遍历：使用Map接口中的entrySet()方法获取到一个Set集合，然后使用迭代器遍历Set集合中的每个元素，再使用Map.Entry的getKey()和getValue()方法获取键值对。代码示例：

Map<String, String> map = new HashMap<String, String>();
// 添加元素到HashMap中
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, String> entry = iterator.next();
    String key = entry.getKey();
    String value = entry.getValue();
    // 处理键值对
}

for-each循环遍历：使用Map接口中的keySet()方法获取到一个Set集合，然后使用for-each循环遍历Set集合中的每个元素，再使用Map的get()方法获取键对应的值。代码示例：

Map<String, String> map = new HashMap<String, String>();
// 添加元素到HashMap中
for (String key : map.keySet()) {
    String value = map.get(key);
    // 处理键值对
}

Java 8中的Stream API遍历：使用Map接口中的entrySet()方法获取到一个Set集合，然后使用Java 8中的Stream API遍历Set集合中的每个元素，再使用Map.Entry的getKey()和getValue()方法获取键值对。代码示例：

Map<String, String> map = new HashMap<String, String>();
// 添加元素到HashMap中
map.entrySet().stream().forEach(entry -> {
    String key = entry.getKey();
    String value = entry.getValue();
    // 处理键值对
});

无论采用何种方式遍历，遍历时需要注意：HashMap是无序的，不能保证元素的顺序。

HashMap的put流程知道吗？

当我们向 HashMap 中插入一个键值对时，首先会进行哈希值的扰动，算出一个新的hash值。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

判断tab是否为空或者长度为0，如果是就进行扩容操作。

1 2	if ((tab = table) == null \|\| (n = tab.length) == 0) n = (tab = resize()).length;

根据哈希值计算下标，如果对应下标正好没有存放数据，则直接插入即可。
1
tab[i = (n - 1) & hash]

如果第一个节点与要插入的键值对匹配，则将其赋值给变量e。

1
2
3

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

如果一个节点是树节点，则调用树节点的插入方法。

1 2	else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

否则就遍历链表，找到链表尾部插入新节点，如果链表长度达到树化阈值，则调用treeifyBin方法将链表转化为红黑树。

// 遍历链表查找匹配的节点
           for (int binCount = 0; ; ++binCount) {
               if ((e = p.next) == null) {
                   // 找到链表尾部，插入新节点
                   p.next = newNode(hash, key, value, null);
                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                       // 如果链表长度达到树化阈值，则将链表转化为红黑树
                       treeifyBin(tab, hash);
                   break;
               }
               if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                   // 找到匹配的节点，跳出循环
                   break;
               p = e;
           }

增加计数器，如果大小超过阈值，则调用resize方法进行扩容。

// 增加修改计数器
   ++modCount;
   if (++size > threshold)
       // 如果大小超过阈值，则进行扩容
       resize();

HashMap的哈希/扰动函数是怎么设计的?

HashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这么设计是为了降低哈希碰撞的概率。

为什么哈希/扰动函数能降hash碰撞？

因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为 -2147483648~2147483647，加起来大概 40 亿的映射空间。

只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40亿长度的数组，内存是放不下的。

假如 HashMap 数组的初始大小才 16，就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。

源码中模运算就是把散列值和数组长度 - 1 做一个 “ 与& “ 操作，位运算比取余 % 运算要快。

bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {
	return h & (length-1);
}

顺便说一下，这也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。因为这样（数组长度 - 1）正好相当于一个 “低位掩码”。与操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2进制表示是 0000 0000 0000 0000 0000 0000 0000 1111 。和某个散列值做与操作如下，结果就是截取了最低的四位值。

这样是要快捷一些，但是新的问题来了，就算散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，那就更难搞了。

这时候 扰动函数 的价值就体现出来了，看一下扰动函数的示意图：

右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

HashMap怎么查找元素的呢？

使用扰动函数，获取新的哈希值
计算数组下标，获取节点
当前节点和key匹配，直接返回
否则，当前节点是否为树节点，查找红黑树
否则，遍历链表查找

为什么HashMap的容量是2的倍数呢？

第一个原因是为了方便哈希取余：

将元素放在table数组上面，是用hash值%数组大小定位位置，而HashMap是用hash值&(数组大小-1)，却能和前面达到一样的效果，这就得益于HashMap的大小是2的倍数，2的倍数意味着该数的二进制位只有一位为1，而该数-1就可以得到二进制位上1变成0，后面的0变成1，再通过&运算，就可以得到和%一样的效果，并且位运算比%的效率高得多。

HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。
第二个方面是在扩容时，利用扩容后的大小也是2的倍数，将已经产生hash碰撞的元素完美的转移到新的table中去。

扩容在什么时候呢？为什么扩容因子是0.75？

为了减少哈希冲突发生的概率，当当前HashMap的元素个数达到一个临界值的时候，就会触发扩容，把所有元素rehash之后再放在扩容后的容器中，这是一个相当耗时的操作。

而这个临界值threshold 就是由加载因子和当前容器的容量大小来确定的，假如采用默认的构造方法：

1	临界值（threshold ）= 默认容量（DEFAULT_INITIAL_CAPACITY） * 默认扩容因子（DEFAULT_LOAD_FACTOR）

那就是大于 16x0.75=12 时，就会触发扩容操作。

那么为什么选择了0.75作为HashMap的默认加载因子呢？

简单来说，这是对空间成本和时间成本平衡的考虑。

我们都知道，HashMap的散列构造方式是Hash取余，负载因子决定元素个数达到多少时候扩容。

假如我们设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的时间成本就增加了。

我们设的比较小的话，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。

HashMap的扩容机制

HashMap是基于数组+链表和红黑树实现的，但用于存放key值的桶数组的长度是固定的，由初始化参数确定。

那么，随着数据的插入数量增加以及负载因子的作用下，就需要扩容来存放更多的数据。而扩容中有一个非常重要的点，就是jdk1.8中的优化操作，可以不需要再重新计算每一个元素的哈希值。

因为HashMap的初始容量是2的次幂，扩容之后的长度是原来的二倍，新的容量也是2的次幂，所以，元素，要么在原位置，要么在原位置再移动2的次幂。

看下这张图，n为table的长度，图 a 表示扩容前的key1和key2两种key确定索引的位置，图 b 表示扩容后key1和key2两种key确定索引位置。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

所以在扩容时，只需要看原来的hash值新增的那一位是0还是1就行了，是0的话索引没变，是1的化变成原索引+oldCap ，看看如16扩容为32的示意图：

jdk1.8对HashMap主要做了哪些优化呢？为什么？

jdk1.8 的HashMap主要有五点优化：

数据结构：数组 + 链表改成了数组 + 链表或红黑树

原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由 O(n) 降为 O(logn)
链表插入方式：链表的插入方式从头插法改成了尾插法

简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后。

原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。
扩容rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 旧的数组容量大小。

原因：提高扩容的效率，更快地扩容。
扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；
散列函数：1.7 做了四次移位和四次异或，jdk1.8只做一次。

原因：做 4 次的话，边际效用也不大，改为一次，提升效率。

HashMap 是线程安全的吗？多线程下会有什么问题？

HashMap不是线程安全的，可能会发生这些问题：

多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

有什么办法能解决HashMap线程不安全的问题呢？

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大；
Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized。

HashMap和ConcurrentHashMap的区别是什么？ConcurrentHashMap的线程安全是如何实现的？

HashMap和ConcurrentHashMap都是Map接口的实现类，HashMap是非线程安全的，ConcurrentHashMap是线程安全的。

jdk1.7：

ConcurrentHashMap的线程安全是通过分段锁（Segment）实现的。每个Segment可以看作是一个小的HashMap，不同的Segment之间是相互独立的，因此在多线程的情况下，不同的线程可以同时对不同的Segment进行操作，这样就避免了对整个Map进行加锁，从而提高了并发性能。
- put流程
  
  整个流程和HashMap非常类似，只不过是先定位到具体的Segment，然后通过ReentrantLock去操作而已，后面的流程，就和HashMap基本上是一样的。
  
  1. 计算hash，定位到segment，segment如果是空就先初始化
  
  2. 使用ReentrantLock加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功
  
  3. 遍历HashEntry，就是和HashMap一样，数组中key和hash一样就直接替换，不存在就再插入链表，链表同样操作
- get流程
  
  get也很简单，key通过hash定位到segment，再遍历链表定位到具体的元素上，需要注意的是value是volatile的，所以get是不需要加锁的。

jdk1.8：

jdk1.8实现线程安全不是在数据结构上下功夫，它的数据结构和HashMap是一样的，数组+链表+红黑树。它实现线程安全的关键点在于put流程。

put流程

1.首先计算hash，遍历node数组，如果node是空的话，就通过CAS+自旋的方式初始化

1	tab = initTable();

node数组初始化：

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

2.如果当前数组位置是空则直接通过CAS自旋写入数据

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

3.如果hash==MOVED，说明需要扩容，执行扩容

1 2	else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f);

/**
  * Helps transfer if a resize is in progress.
  */
 final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
     Node<K,V>[] nextTab; int sc;
     if (tab != null && (f instanceof ForwardingNode) &&
         (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
         int rs = resizeStamp(tab.length);
         while (nextTab == nextTable && table == tab &&
                (sc = sizeCtl) < 0) {
             if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                 sc == rs + MAX_RESIZERS || transferIndex <= 0)
                 break;
             if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                 transfer(tab, nextTab);
                 break;
             }
         }
         return nextTab;
     }
     return table;
 }

4.如果都不满足，就使用synchronized写入数据，写入数据同样判断链表、红黑

树，链表写入和HashMap的方式一样，key hash一样就覆盖，反之就尾插法，链

表长度超过8就转换成红黑树

1
2
3

synchronized (f){
……
}

get查询

get很简单，和HashMap基本相同，通过key计算位置，table该位置key相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取。

HashMap内部节点是有序的吗？

HashMap是无序的，根据 hash 值随机插入。如果想使用有序的Map，可以使用LinkedHashMap 或者 TreeMap。

讲讲 LinkedHashMap 怎么实现有序的？

LinkedHashMap维护了一个双向链表，有头尾节点，同时 LinkedHashMap 节点 Entry内部除了继承 HashMap 的 Node 属性，还有 before 和 after 用于标识前置节点和后置节点。

可以实现按插入的顺序或访问顺序排序。

讲讲 TreeMap 怎么实现有序的？

TreeMap 是按照 Key 的自然顺序或者 Comprator 的顺序进行排序，内部是通过红黑树来实现。所以要么 key 所属的类实现 Comparable 接口，或者自定义一个实现了Comparator 接口的比较器，传给 TreeMap 用于 key 的比较。

Set

讲讲HashSet的底层实现？

HashSet 底层就是基于 HashMap 实现的。（ HashSet 的源码⾮常⾮常少，因为除了clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不实现之外，其他⽅法都是直接调用 HashMap 中的⽅法。

HashSet的add方法，直接调用HashMap的put方法，将添加的元素作为key，new一个Object作为value，直接调用HashMap的put方法，它会根据返回值是否为空来判断是否插入元素成功。

1
2
3

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

而在HashMap的putVal方法中，进行了一系列判断，最后的结果是，只有在key在table数组中不存在的时候，才会返回插入的值。

if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }

HashSet和TreeSet的区别是什么？它们是如何保证元素的唯一性的？

HashSet和TreeSet都是Set接口的实现类，HashSet基于HashMap实现，而TreeSet基于红黑树实现。HashSet通过哈希表保证元素的唯一性，而TreeSet通过比较器或元素的自然顺序保证元素的唯一性。

HashSet 是基于哈希表实现的，可以用于存储不重复的元素，支持快速的添加、删除和查找操作，但元素并不保证有序。
TreeSet 是基于红黑树实现的，可以用于存储不重复的元素，并且元素是有序的，支持有序遍历和查找操作，但添加、删除和查找操作的效率较低。
如果需要存储不重复的元素，并且不需要保证元素的顺序，可以使用 HashSet；如果需要存储不重复的元素，并且需要按照一定的顺序进行遍历和查找操作，可以使用 TreeSet。

Collections工具类有哪些常用的方法？它们的作用是什么？

Collections工具类提供了很多静态方法，包括：

sort(List)：对List进行排序。
binarySearch(List, Object)：在List中查找指定元素，返回其下标。
shuffle(List)：随机打乱List中的元素顺序。
reverse(List)：将List中的元素倒序排列。
max(Collection)：返回Collection中的最大元素。
min(Collection)：返回Collection中的最小元素。

这些方法都是为了方便地对集合进行操作而提供的。