JAVA基础—集合详细解析_java集合详解

1.JAVA中的4种集合类型

1. Set：无序、不可重复的集合
2. List：有序、重复的集合
3. Queue： 队列
4. Map：映射关系

首先，JAVA的集合类主要有两个接口派生而出：Collection和Map。Collection和Map就是JAVA集合的根接口。所以后面了解集合的特性主要就是研究Collection和Map的特性。

2. Collection（root接口）

在JAVA源码解释，Collection就是一个root接口，它的存在是给各种衍生的集合提供规范设计与基本特性的。

2.1 Iterator

collection接口提供了最基础的 添加、删除、遍历元素等方法。其中iterator()迭代是重点。

public interface Collection<E> extends Iterable<E> {
1

看源码可以知道Collection是继承了Iterable迭代属性的，也就是说实现该接口允许对象成为增强型for语句（有时称为“for-each循环”语句）的目标。

/**
An iterator over a collection. Iterator takes the place of Enumeration in the Java Collections Framework. Iterators differ from enumerations in two ways:
Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
Method names have been improved.
This interface is a member of the Java Collections Framework.
API Note:
An Enumeration can be converted into an Iterator by using the Enumeration.asIterator method.

一个集合的迭代器。在Java集合框架中，迭代器取代了Enumeration。迭代器与枚举有两个不同之处：

迭代器允许调用者在迭代期间从底层集合中删除元素，并具有明确定义的语义。
方法名称得到了改进。
 */
public interface Iterator<E> {
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 看上面注释可以看出来，Iterator遍历过程只提供了删除元素操作。
• 在使用迭代器遍历集合时，迭代出来的元素都是原来集合元素的拷贝，而 Java集合中保存的元素实质是对象的引用，而非对象本身，所以不能直接修改集合中的元素，但可以使用 remove() 方法来删除当前元素。
• iterator()方法与普通的for循环区别是，如果在for循环的过程中调用集合的remove()方法，就会导致循环出错，因为循环过程中list.size()的大小变化了，就导致了错误。
• iterator和foreach都是单向遍历的。

2.2 Iterator VS for

1.首先，for循环有两种，它们的行为非常不同，一种使用索引

for (int i = 0; i < list.size(); i++) {
    Thing t = list.get(i);
    ...
}
1
2
3
4

这种循环并不总是可行的。例如，List有索引，但Set没有，因为它是无序集合。
另一种是 foreach 循环，其在幕后也是使用迭代器：

for (Thing thing : list) {
    ...
}
1
2
3

这适用于各种可迭代集合（或数组）

最后， Iterator也适用于任何 继承了Iterable的集合：

for (Iterator<Thing> it = list.iterator(); it.hasNext(); ) {
    Thing t = it.next();
    ...
} 
1
2
3
4

所以实际上有 3 个循环需要比较，从性能、可读性、易错性、功能去比较的话。

1.功能性：Iterator 可以做 foreach 循环不能做的事情。例如，如果迭代器支持，您可以在迭代时删除元素：

for (Iterator<Thing> it = list.iterator(); it.hasNext(); ) {
    Thing t = it.next();
    if (shouldBeDeleted(thing) {
        it.remove();
    }
} 
1
2
3
4
5
6

2.可读性与易错性：很明显foreach要比Iterator好很多
3.性能：使用fori遍历，对于数组，使用索引访问元素的效率稍高一些。但是，如果使用 LinkedList，性能会很糟糕，因为每次访问 时list.get(i)，链表都必须循环遍历其所有元素，直到第 i 个元素。但是Iterator迭代器（以及 foreach 循环）不存在这个问题。它总是使用最好的方法来迭代给定集合的元素，因为集合本身有它自己的 Iterator 实现。

so，一般经验法则是：使用 foreach 循环，除非确实需要迭代器的功能。当我需要访问循环内的索引时，使用带有数组索引的 fori 循环。

3 List （Extends Collection）

• 说说List的特点

  1. List是有序集合
  2. List接口在Iterator接口基础上增加了ListIterator方法，可以双向遍历，还可以在遍历时通过add()方法向List集合中添加元素。

  add(): 将指定的元素插入列表中（可选操作）。如果有的话，该元素将被插入到下一个将被 next 返回的元素之前，并且在任何情况下都会在 previous 返回的元素之后。（如果列表不包含元素，则新元素将成为列表上的唯一元素。）新元素被插入到隐式光标之前：后续调用 next 将不受影响，而后续调用 previous 将返回新元素。（此调用将增加调用 nextIndex 或 previousIndex将返回的值的一个单位。）

继承了List的几个主要集合分别是ArrayList、Vector、LinkedList，下面详细说说这三个集合

3.1 ArrayList和Vector简介

Vector和ArrayList功能是非常相似的，都是可调整大小的数组实现。它实现了所有可选的列表操作，并允许所有元素，包括null。除了实现List接口外，还提供了一些方法来操作内部用于存储列表的数组的大小。最大的区别就是Vector是同步的，ArrayList是异步的。

Vector和ArrayList都是实现了List接口的可调整大小的数组实现。它们之间的主要区别在于以下几点：

1. 线程安全——Vector线程安全，ArrayList非线程安全

• Vector是线程安全的，所有方法都被synchronized修饰，因此在多线程环境种使用不会有问题。但是，在并发环境下过度的同步会导致性能下降。

  Vector的所有方法都被声明为synchronized，这意味着在多线程环境下，同一时刻只能有一个线程访问Vector的方法，从而保证了线程安全性。
  这种同步机制确保了在多线程环境下对Vector的操作不会导致数据不一致或不正确的结果。但是，这也会带来性能上的一些开销，因为在访问Vector的方法时需要获取同步锁，这可能会导致其他线程需要等待。
  因此，尽管Vector在多线程环境中是安全的，但在单线程环境中，由于同步机制的开销，它的性能可能会比非同步的实现（比如ArrayList）稍差。

• ArrayList是非线程安全的，这意味着在单线程环境性能更好，但是在多线程环境种需要外部执行同步操作。

2. 容量增长策略——Vector自动扩容一倍，ArrayList自动扩容50%

• Vector和ArrayList在内部都是用了数组来存储元素。
• 当向Vector添加元素时，如果容量不足，它的容量会自动增加一倍。
• ArrayList的容量增长策略是增加当前容量的50%。
• 旧的元素使用Arrays.copyOf方法被复制到新的数组中去，现有的数组引用指向了新的数组。

3. 性能——单线程：ArrayList>Vector

• 在单线程下，ArrayList肯定是要比Vector的性能好的。虽说Vector是线程安全的，在多线程下，安全性要比ArrayList好，但是ArrayList也可以使用工具类实现线程的安全，如下：

   List list = Collections.synchronizedList(new ArrayList(...));
  1

  按使用习惯来说，ArrayList通常比Vector更常用。

总之，如果在单线程环境中使用，并且不需要考虑线程安全问题，通常会选择ArrayList。而如果需要在多线程环境中使用，或者需要一个线程安全的集合，则可以选择Vector。

3.5 LinkedList

与List接口不同，该接口不支持对元素进行索引访问，LinkedList是List和Deque接口的双向链表共同实现的。

Deque(双端队列)是一种线性集合，支持在两端进行元素插入和删除。大多数deque实现对它们可以包含的元素熟练没有固定限制，此接口支持具有容量限制和没有固定大小限制的双端队列。

LinkedList每个节点都会记录自己的前驱集结点和后继节点，这样的好处是插入元素的时候很容易找到自己的前驱节点和后继节点。 而且LinkedList 数据结构还是比较简单的，LinkedList维护了三个变量，链表的大小加上一个头节点和一个尾节点。

• LinkedList优点：对头尾元素操作效率很高
  add()方法相对队列而言，其实就是往队列的尾部添加一个元素，当添加一个新元素时：只需要维护前驱与后继节点，队列数量+1即可。

• LinkedList缺点：查找元素慢
  由于链表特性，查找一个元素时，只能一个个遍历，平均时间复杂度为O(n)。所以需要频繁遍历集合的操作，不要使用LinkedList

• 总结一下
  LinkedList使用双向链表实现List的功能，相比ArrayList，它有以下特点：

  1. 空间占用小，不需要提前分配内存,但还是比ArrayList占用内存多（多存储了前后节点）
  2. 不可以随机访问，需要通过索引查找元素，平均时间复杂度为O(n)
  3. 同时实现了队列和栈的特性（双向链表）
  4. 对头尾元素操作效率很高，均为O(1)
  5. 相比于ArrayList，对于增加删除频繁的操作，LinkedList更适合作为存储对象。相反，对于随机访问或者频繁查找的操作，ArrayList比LinkedList效率高。

4.Map（root接口）

1. Map集合是一个将键映射到值的对象。映射不能包含重复的键；每个键最多只能映射到一个值。）。
2. Map集合中的元素，key和value的数据类型可以相同，也可以不同。
3. Map集合中的元素，key是不允许重复的，value是可以重复的。
4. Map集合中的元素，key和 value是一一对应的。

Map实话说很好理解，也没有什么可以问的点。最重要的就是HashMap的实现原理了，HashMap的桶数、负载因子、扩容问题还有就是超过阈值变成红黑树，最难理解的就是红黑树的平衡还有代码实现了。

4.1 HashMap

直接上源码的注解

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
HashMap 是基于哈希表的 Map 接口的实现。该实现提供了所有可选的映射操作，并允许 null 值和 null 键。（HashMap 类大致相当于 Hashtable，但是它是不同步的，并且允许 null 值。）该类不保证映射的顺序；特别是，它不保证顺序会随时间保持不变。

这段话其实已经给出了hashmap和hashtable的区别了，HashTable是线程安全的，HashMap反之

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
这个实现为基本操作（get 和 put）提供了常数时间的性能，假设哈希函数将元素正确地分散在桶之间。对集合视图的迭代需要与 HashMap 实例的“容量”（桶的数量）加上其大小（键-值映射的数量）成正比的时间。因此，如果迭代性能很重要，就非常重要不要将初始容量设置得太高（或负载因子设置得太低）。

// 设置初始容量为16，负载因子为0.75
HashMap<String, Integer> map1 = new HashMap<>(16, 0.75f);

// 设置初始容量为32（负载因子默认为0.75）
HashMap<String, Integer> map2 = new HashMap<>(32);
1
2
3
4
5

在选择初始容量和负载因子时，可以根据预期的元素数量和对性能的要求来进行调整。通常建议负载因子设置在0.5到0.75之间，以保持在添加元素时保持较高的性能。初始容量应该根据预期的元素数量来选择，以减少在运行时重新调整容量的频率，从而提高性能。

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
HashMap 的一个实例有两个参数影响其性能：初始容量和负载因子。容量是哈希表中的桶数，初始容量是哈希表创建时的容量。负载因子是哈希表允许在其容量自动增加之前变得多满的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将重新调整大小（即，内部数据结构将被重新构建），使哈希表大约有两倍的桶数。

划重点，当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将重新调整大小（即，内部数据结构将被重新构建），使哈希表大约有两倍的桶数。

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
作为一般规则，默认负载因子（0.75）在时间和空间成本之间提供了良好的折衷。更高的值减少了空间开销，但增加了查找成本（在 HashMap 类的大多数操作中反映，包括 get 和 put）。在设置初始容量时应考虑映射中的预期条目数和负载因子，以便最小化重新调整大小的次数。如果初始容量大于最大条目数除以负载因子，那么将永远不会发生重新调整大小的操作。

重点，作为一般规则，默认负载因子（0.75），在设置初始容量时应考虑映射中的预期条目数和负载因子，以便最小化重新调整大小的次数。

这里说一下阿里巴巴的开发手册
【推荐】集合初始化时，指定集合初始值大小。
说明 : HashMap 使用 HashMap(int initialCapacity) 初始化， 正例 : initialCapacity = (需要存储的元素个数 / 负载因子) +1。注意负载因子(即 loaderfactor)默认为 0.75，如果暂时无法确定初始值大小，请设置为 16。

反例 : HashMap需要放置 1024 个元素，由于没有设置容量初始大小，随着元素不断增加，容量 7 次被迫扩大，resize 需要重建 hash表，严重影响性能。

If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table. Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.
如果要存储许多映射到 HashMap 实例中，那么使用足够大的容量创建它将允许映射的存储比让它按需要执行自动重新调整大小更有效。请注意，使用具有相同 hashCode() 的键会减慢哈希表性能（hashcode冲突）。为了缓解影响，当键可比较时，该类可以使用键之间的比较顺序来帮助解决冲突。

• HashMap的扩容逻辑
  默认桶数16，默认负载因子0.75
  1. 第一次添加时，table数组扩容到16，临界值是 16 * 负载因子0.75 = 12
  2. 如果table数组使用到了临界值12，就会扩容到 16 *2= 32 ，新的临界值就是 32 * 0.75 = 24 以此类推
  3. 表里面全部的数据到达了临界值就会扩容，而不是只看某一个链表。扩容时，HashMap 会创建一个新的哈希表，其容量是原来的两倍。然后，HashMap 会将原来哈希表中的所有元素重新计算哈希值，并将它们添加到新的哈希表中。这个过程是比较耗时的，因为需要重新计算哈希值和重新分配存储空间。
  4. 在jdk8中，如果一条链表的元素个数到达 8 并且table的大小 >= 64 就会进行树化(红黑树) ,否则仍然采用数组扩容机制

- HashMap底层实现（简单记录）
红黑树的出现需要自己慢慢从二叉树、二叉平衡树再进化到红黑树慢慢理解。明白为什么使用红黑树，红黑树解决了什么问题。

二叉树（最多两子节点左小右大,如果一直比父节点大/小，会导致链表化）
|
二叉平衡树（高度差至多等于1，规则太严格，容易导致平衡树频繁变动）
|
红黑树（只有红黑节点，黑高限制，自动平衡）

1. 根节点黑色；叶节点（NIL）黑色；红色节点后一定是黑节点；两个红节点不能相连；
2. 任意一节点到每个叶子节点的路径都包含数量相同的黑节点。红黑树保持黑色完美平衡
3. 红黑树自平衡：左旋、右旋、变色
   变色：节点颜色有红变黑或黑变红
   左旋：以某个结点作为支点，其右子节点变成旋转节点的父节点，右子节点的左子树变成旋转节点的右子树，右子节点的右子树保持不变，如下图所示
   
   右旋：以某个节点作为支点，其左子节点变成旋转节点的父节点，左子节点的右子节点的右子树变成旋转节点的左子树，左子节点左子树保持不变,如下图所示
   
4. 红黑树查找与二叉树无异
5. 红黑树插入节点：查找插入节点、插入、自平衡

4.2 Hashtable（线程安全）

HashMap和HashTable再实现原理上有一些相似之处，但也有一些重要的区别
相似之处：
1.基于哈希表的数据结构:HashMap和Hashtable都是基于哈希表实现的。它们使用哈希函数将键映射到哈希表的桶(buckets)中，然后在桶中存储键值对。
2.解决哈希冲突的方法：当多个键被哈希到同一个桶时，它们会形成冲突。hashMap和HashTable都使用不同的方法来解决这些冲突，例如链地址法或开放地址法

不同之处：
1.同步性质：这是最显著的区别。hashTable是线程同步的，意味着它是线程安全的，可以在多个线程同时访问。但是，这种同步性质会带来性能开销。而hashMap时非线程安全的，如果hashMap需要线程安全可以使用Collections工具类
2.允许null值和键：HashMap允许键和值都为null，而Hashtable不允许。这意味着在HashMap中，可以将null作为键或值进行存储，但在Hashtable中，如果尝试存储null键或值，会抛出NullPointerException。
3.性能：由于同步性质的不同，HashMap通常比Hashtable具有更好的性能。在单线程环境下，HashMap的性能可能会更优，因为它没有同步开销。

4.3 ConcurrentHashMap（线程安全）

1. concurrentHashMap是一种支持完全并发的检索和更新的哈希表。它遵循Hashtable的功能规范，并提供了和Hashtable相对应的方法
2. concurrentHashMap的锁分离（lock-striping）的技术

在多线程环境下，ConcurrentHashMap 的所有操作都能够正确地处理并发访问的情况，不会导致数据损坏或不一致。在进行检索操作（比如使用 get 方法获取值）时，并不需要使用锁来保护数据的一致性。
这意味着即使有其他线程正在对表格进行更新，检索操作也能够继续进行。ConcurrentHashMap 没有提供一种锁定整个表格以防止所有访问的机制。相反，它采用了一种更精细的锁机制，允许在并发更新的情况下进行并发检索操作。
总结一下，即使有其他线程在对表格进行更新，ConcurrentHashMap 也能够允许并发的检索操作，并且不会由于并发更新而发生阻塞。
其关键在于ConcurrentHashMap 使用了一种锁分离（lock-striping）的技术，将整个哈希表分成了若干个 Segment，每个 Segment 都有自己的锁。
这种设计可以在多线程环境下提供更高的并发性能，因为每个线程在操作时只需要锁定自己所在的 Segment，而不是锁定整个哈希表，从而减少了锁竞争的激烈程度。
默认情况下，ConcurrentHashMap 将 Map 分成 16 个 Segment，因此可以在一定程度上提高约 16 倍的并发性能。这种锁分离的设计在提供相同的线程安全性的同时，大大提高了并发操作的效率。

在 ConcurrentHashMap 中，Segment 是一个内部静态类，它代表了哈希表中的一个分段（segment）。每个Segment 实际上是一个哈希表，负责管理部分键值对的存储和操作。

3. ConcurrentHashMap 在发生冲突时采取的动态扩展策略，以维持哈希表的性能平衡。

在哈希表中，如果两个不同的键映射到了同一个槽位（bin），就会发生冲突。
为了解决冲突，一种常见的方法是使用链表或者树等数据结构来存储冲突的键值对。
然而，如果发生冲突的次数过多，链表或树可能会变得很长，导致哈希表的性能下降。
为了解决这个问题，ConcurrentHashMap采用了动态扩展的策略。当发生冲突的次数超过一定阈值时，ConcurrentHashMap 会自动进行扩容操作，增加哈希表的大小，从而减少冲突的发生概率。并且，它会尽量保持每个哈希桶（bin）中的平均映射数量约为两个，这是为了在维持较低的冲突率的同时，不至于浪费过多的内存空间。
这种动态扩展的策略可以帮助维持 ConcurrentHashMap 的时间和空间效率，使其在处理大量并发操作时依然能够保持较高的性能水平。

4.4 linkedHashMap

1. LinkedHashMap时Map接口的实现之一，结合了哈希表和链表的特性，并且具有可预测的迭代顺序。它与HashMap不同之处在于维护了一个双向链表，这个链表定义了迭代顺序，通常时按照键被插入到映射中的顺序（插入顺序）。这种实现可以避免HashMap提供的不确定和混乱的排序，同事不会增加类似TreeMap的开销。LinkedHashMap可以用来创建一个与原始映射具有相同顺序的副本，这对于需要保持顺序的情况非常有用。

当涉及到需要保持顺序的数据集时，LinkedHashMap可以提供很好的解决方案。例如，假设你正在编写一个在线商店的购物车功能。在购物车中，你可能需要存储商品和它们对应的数量。而且，当你展示购物车内容给用户时，通常希望按照用户添加商品的顺序来显示。
在这种情况下，你可以使用LinkedHashMap来存储购物车中的商品及其数量。每当用户添加新的商品时，你将该商品及其数量插入到LinkedHashMap中。由于LinkedHashMap维护了插入顺序，当你需要展示购物车内容时，你可以确保商品以用户添加的顺序显示出来，而不是以某种随机或未定义的顺序。
举例来说，如果用户首先添加了一本书、然后添加了一件衬衫、最后添加了一双鞋子，那么使用LinkedHashMap存储购物车内容时，书会显示在衬衫的前面，衬衫会显示在鞋子的前面。这样，用户在购物车中看到的商品顺序就与他们添加商品的顺序完全一致。

2. LinkedHashMap提供了一个特殊的构造函数来创建一个链接哈希映射，其迭代顺序是其条目最后一次访问的顺序，从最近访问到最近访问（访问顺序）。这种类型的映射非常适合构建LRU缓存。

就是说，在最近一次访问的对象，对更新其顺序为最后一次访问的顺序（顺序移到最后）。
用一个简单的例子来说明。
假设你正在编写一个网络服务器，它需要缓存最近访问的网页内容以提高响应速度。你想要实现一个LRU（Least Recently Used）缓存，以便在服务器内存有限的情况下，保留最近访问的网页内容，并在需要时从缓存中获取。
你可以使用Java中的LinkedHashMap来实现这个LRU缓存。具体步骤如下：

1. 创建一个LinkedHashMap对象，并设置其访问顺序为true（这是LinkedHashMap的构造函数中的一个参数）。
2. 设置缓存的最大容量，当缓存达到最大容量时，需要移除最不常使用的条目以腾出空间。
3. 每当有新的网页内容被请求时，检查该内容是否已经在缓存中。如果在缓存中，则将该内容标记为最近访问，并更新其在LinkedHashMap中的位置。如果不在缓存中，则从服务器获取该内容，并将其添加到缓存中。如果缓存已满，则移除最久未被访问的内容。
4. 当再次请求已经在缓存中的网页内容时，它会被标记为最近访问，并且其在LinkedHashMap中的位置会更新。

这样，通过使用LinkedHashMap，并根据最近访问的顺序进行迭代，你可以实现一个简单而有效的LRU缓存。这个缓存会自动保留最近访问的网页内容，并在需要时进行更新和替换，以确保服务器能够快速响应用户的请求，同时又不会占用过多的内存。

伪代码如下：

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> {
    private int capacity;
    private LinkedHashMap<K, V> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }

    public V get(K key) {
        return cache.getOrDefault(key, null);
    }

    public void put(K key, V value) {
        cache.put(key, value);
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(2);
        cache.put(1, "Page 1");
        cache.put(2, "Page 2");
        System.out.println(cache.get(1)); // 输出：Page 1
        cache.put(3, "Page 3"); // Page 2被移除
        System.out.println(cache.get(2)); // 输出：null，因为该项已被移除
        System.out.println(cache.get(3)); // 输出：Page 3
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

4. 由于维护链表的额外开销，性能可能略低于HashMap，但有一个例外：在LinkedHashMap的集合视图上进行迭代需要与映射大小成比例的时间，而不管其容量如何。在HashMap上进行迭代可能更昂贵，需要与其容量成比例的时间。
5. 链接哈希映射有两个影响其性能的参数：初始容量和负载因子。它们的定义与HashMap完全相同。但是，请注意，对于此类选择初始容量过高的值的惩罚要小于对HashMap的惩罚，因为此类的迭代时间不受容量的影响。（双向链表，没有容量限制，迭代时间只与插入数据相关）
6. 请注意，此实现未同步。如果多个线程同时访问链接哈希映射，并且至少有一个线程在结构上修改了映射，则必须在外部同步。（非线程安全）

4.5 TreeMap

基于红黑树（Red-Black tree）的 NavigableMap 实现。
TreeMap按照键的自然顺序进行排序，或者根据在创建映射时提供的Comparator进行排序，具体取决于使用的构造方法。这使得TreeMap中的键值对能够按照一定顺序进行排序。
TreeMap的底层数据结构是平衡二叉树，通常是红黑树。红黑树是一种自平衡的二叉搜索树，它能够确保在插入或者删除操作后，树的高度保持在对数级别，从而保证了查找、插入和删除的时间复杂度都是O（logn）

因此，TreeMap具有以下优点
1.键值对按照自然顺序或提供的Comparator进行排序，使得映射的键具有排序属性
2.键的唯一性保证了映射中不会存在重复的键
4.底层结构是平衡二叉树，保证了查找、插入和删除等操作的高效性。

以下是一些常见的应用场景：

1. 字典或词典：当需要存储一组键值对，并且希望按照键的自然顺序或者自定义的比较器进行排序时，可以使用 TreeMap。这在实现字典或词典等功能时非常有用，例如存储单词和对应的释义，可以按照单词的字母顺序进行排序。
2. 日程管理：在日程管理应用程序中，可以使用 TreeMap 来存储日期和对应的日程安排。通过按照日期进行排序，可以方便地查找特定日期的日程安排，也可以快速找到最近的日程。
3. 数据库索引：在数据库中，TreeMap 可以用于实现索引结构，例如 B+ 树。通过将数据库中的键值对按照键排序存储在 TreeMap 中，可以实现高效的范围查询和快速查找操作。
4. 事件调度器：与 TreeSet 类似，TreeMap 也可以用于实现事件调度器。通过按照事件发生的时间进行排序，可以方便地管理和调度一系列事件，例如任务调度器或定时任务管理器。

5 Set

源码中，Set三个比较重要的实现类包括：SortedSet, HashSet, TreeSet。

从源码解释上看，set集合时一个不包含重复元素的无序集合，更正式地说，集合不包含任何一对元素e1和e2使得e1.equals(e2)，并且最多包含一个null元素。而无序则代表取出的顺序和添加的顺序不一样。

5.1. SortedSet（可排序不可重复集合）

1. 不可重复，但可排序。元素按照它们的自然顺序排序，或者按照在创建有序集时通常提供的Comparator排序。SortedSet的迭代器将按照元素的升序顺序遍历集合。
2. 向有序集中插入的所有元素都必须实现Comparable接口（或者被指定的比较器接受）。此外，所有这些元素必须是相互可比较的：对于有序集中的任何元素e1和e2，e1.compareTo(e2)

5.2. HashSet

1. HashSet继承了Set接口，有哈希表（实际上是一个HashMap实例）支持。它不保证集合的迭代顺序；特别是，它不保证顺序会随时间保持不变。该类允许空元素。
2. HashSet提供了基本操作(add、remove、contains、size)的恒定时间性能，假设哈希函数将元素适当地分布在桶中。遍历此集合需要的时间与HashSet实例大小(元素数)家伙是那个支持HashMap实际的”容量“(桶数)的总和成正比例。因此，如果迭代性能很重要，不要将初始容量设置太高(或负载因子设置太低)。

  // 设置初始容量为 16，负载因子为 0.75 的 HashSet
        HashSet<String> setWithLoadFactor = new HashSet<>(16, 0.75f);
1
2

桶数：桶数指的是哈希表内部的桶的数量，也可以理解为哈希表的大小。在哈希集中，元素被根据它们的哈希值分配到不同的桶中，桶数的多少直接影响了哈希集的性能和存储能力。
负载因子：负载因子是指在哈希表中存储的元素数量与桶的数量之间的比率。负载因子越小，哈希表的负载越低，冲突的可能性也越小，但会导致空间浪费。负载因子越大，哈希表的负载越高，但可能会增加冲突的概率。
1
2

• 分析HashSet的扩容和转成红黑树机制（其实就是HashMap的扩容机制）

  1. HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值是 是 16 * 加载因子是0.75 = 12
  2. 如果table数组使用到了临界值12，就会扩容到 16 << 1 = 32 ，新的临界值就是 32 * 0.75 = 24 以此类推
  3. 表里面全部的数据到达了临界值就会扩容，而不是只看某一个链表。扩容时，HashMap 会创建一个新的哈希表，其容量是原来的两倍。然后，HashMap 会将原来哈希表中的所有元素重新计算哈希值，并将它们添加到新的哈希表中。这个过程是比较耗时的，因为需要重新计算哈希值和重新分配存储空间。
  4. 在jdk8中，如果一条链表的元素个数到达 8 并且table的大小 >= 64 就会进行树化(红黑树) ,否则仍然采用数组扩容机制

• HashSet的添加元素底层是如何实现的(hash()+equals())

  1. 先获取元素的哈希值（hash()方法），对哈希值进行运算，得到一个索引值，就是存在哈希表中的位置号
  2. 找到存储数据表table，看这个索引位置是否已经存放元素
  3. 如果没有，直接加入
  4. 如果有，调用equals方法比较，如果相同就放弃添加，如果不相同，就添加到最后

5.3. TreeSet

TreeSet基于 TreeMap 的 NavigableSet 实现，即
TreeSet。元素根据它们的自然顺序进行排序，或者根据在创建集合时提供的 Comparator 进行排序，具体取决于使用的构造方法。

TreeSet 在实际开发中有许多用途，特别是在需要维护一组有序且不重复元素的情况下。以下是一些常见的应用场景：

1. 实现事件调度器：在需要按照时间顺序管理一系列事件的情况下，可以使用 TreeSet 来存储事件对象，并根据事件发生的时间进行排序。这样可以方便地查找最近的事件或者按照一定规则处理事件。

2. 实现缓存的 LRU 算法：LRU（Least Recently Used）算法是一种常见的缓存淘汰策略，它会移除最近最少使用的元素。通过 TreeSet 和 LinkedHashMap 结合使用，可以实现一个高效的 LRU 缓存，其中 TreeSet 用于存储缓存键，并根据访问时间进行排序，而 LinkedHashMap 用于存储缓存键值对，并保持插入顺序。

6.Queue（Extends Collection）

队列是数据结构中比较重要的一种类型（是一种数据结构），它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。

队列是一种比较特殊的线性结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。
java中的Queue接口就实现了队列的功能，Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList虽然是个数组，但是也实现了Queue接口(通过Deque接口间接实现)，因此，可以当做Queue来用。

6.1 Deque

JDK在1.6的时候新增了一个双向队列Deque，用来实现更灵活的队列操作。比如可以在前端插入数据。

队列中最先插入的元素也将最先被删除，对应的最后插入的元素将最后被删除。因此队列又称为“先进先出”（FIFO—first in first out）的线性表，与栈(FILO-first in last out)刚好相反。