集合是什么

集合是在Java开发中经常使用的一种容器，用于存储对象数据。与数组类似，集合可以存储多个元素，但相比数组，集合更灵活、功能更强大。

需要注意的是，集合不能直接存储基本数据类型，而是存储对应的包装类对象；同时，集合中存储的是对象的引用，而非对象本身。

所有的集合类和集合接口都在java.util包下。

集合和数组的区别

1. 数据类型：数组可以存储基本数据类型和对象，而集合只能存储对象。数组只能存储同一种类型的数据，集合可以存储不同类型。

2. 长度：数组的长度是固定的，一旦创建就无法改变；而集合的长度是动态的，可以根据需要动态增加或减少元素。

3. 功能：集合提供了丰富的操作和功能，比如添加、删除、查找、排序等；而数组的功能相对简单，需要自行编写代码实现这些功能。

4. 类型：数组是一个简单的数据结构，而集合是Java中的一种容器类，提供了更多的高级功能和操作。

集合的分类

Java中集合分为两大类：

• 存储单个元素的集合，共同父接口为 java.util.Collection
• 以键值对方式存储元素的集合，共同父接口为 java.util.Map

Collection

Collection接口是Java集合框架中的根接口，它定义了一些适用于所有集合的通用方法。

方法签名	描述
add(E e)	确保此集合包含指定的元素。
clear()	移除此集合中的所有元素。
size()	返回此集合中的元素数。
remove(Object o)	移除此集合中的单个实例（如果存在）。
isEmpty()	如果此集合不包含元素，则返回 true。
contains(Object o)	如果此集合包含指定的元素，则返回 true。
iterator()	返回在此集合的元素上进行迭代的迭代器。
toArray()	返回包含此集合中所有元素的数组。
equals(Object o)	比较指定的对象与此集合是否相等。
hashCode()	返回此集合的哈希码值。
addAll(Collection<? extends E> c)	将指定集合中的所有元素添加到此集合。
containsAll(Collection<?> c)	如果此集合包含指定集合中的所有元素，则返回 true。
removeAll(Collection<?> c)	移除此集合中包含在指定集合中的所有元素。
retainAll(Collection<?> c)	仅保留此集合中包含在指定集合中的元素。

Collection接口的主要实现类有List, Set和Queue。

List

List是Collection的子接口，它表示一个有序的集合，可以包含重复的元素。

List接口提供了一些额外的方法来操作列表中的元素，如get(int index), set(int index, E element), add(int index, E element)等，这些方法允许我们根据元素的索引来访问或修改列表。

1. get(int index): 返回此列表中指定位置的元素。
2. set(int index, E element): 用指定的元素替换此列表中指定位置的元素。
3. indexOf(Object o): 返回此列表中首次出现的指定元素的索引，如果此列表不包含该元素，则返回 -1。
4. subList(int fromIndex, int toIndex): 返回此列表中指定的 fromIndex（包含）和 toIndex（不包含）之间的视图。

以上方法都是List接口的一部分，具体的实现会依赖于List的具体实现类，如ArrayList，LinkedList等。

LinkedList

LinkedList是List接口的一个实现类，它底层使用双向链表实现。每个元素（节点）都包含数据和两个指针，分别指向前一个和后一个元素。LinkedList除了实现List接口中的方法外，还提供了一些额外的方法，如addFirst(E e), addLast(E e), removeFirst(), removeLast()等，这些方法允许我们在列表的头部或尾部添加或删除元素。LinkedList 的方法都是线程不安全的。

LinkedList的特点是插入、删除元素的时间复杂度为O(1)，但访问元素的时间复杂度为O(n)。因此，LinkedList适合用于频繁插入、删除元素的场景，而不适合用于频繁访问元素的场景。

以下是LinkedList的一些主要方法：

• addFirst(E e): 在此列表的开头插入指定的元素。
• addLast(E e): 在此列表的末尾插入指定的元素。
• removeFirst(): 移除并返回此列表的第一个元素。
• removeLast(): 移除并返回此列表的最后一个元素。

ArrayList

ArrayList是基于动态数组（ 底层使用数组Object[]）实现的，它支持快速的随机访问，也就是说，获取指定索引位置的元素的时间复杂度为O(1)。但是，如果需要在列表的中间位置插入或删除元素，那么需要移动后面的所有元素，所以时间复杂度为O(n)。

ArrayList的容量会自动增长，当添加元素时，如果当前数组已满，那么ArrayList会创建一个新的数组，新的ArrayList 的容量会增加大约一半，即原容量的1.5倍，并将旧数组的内容复制到新数组中，这个过程的时间复杂度为O(n)。

ArrayList 不是线程安全的，如果多个线程同时访问 ArrayList，并且至少有一个线程在结构上修改了列表（添加、删除元素等），则必须外部同步。

Vector

Vector和ArrayList类似，底层都是使用数组（Object[]）来实现的。但是，Vector的方法都是同步的（synchronized），这意味着它是线程安全的。

在多线程环境下，如果一个线程正在修改Vector，其他线程则必须等待，这可以防止同时修改导致的数据不一致。但是，这种线程安全的保证会带来一定的性能开销。

Set

List和Set都是Java集合框架中的接口，它们都继承自Collection接口，因此它们都具有Collection接口的特性，例如可以添加元素，删除元素，检查元素是否存在等。

List接口表示一个有序的集合，可以包含重复的元素。List接口提供了一些额外的方法来操作列表中的元素，这些方法允许我们根据元素的索引来访问或修改列表。

Set接口表示一个无序的集合，不可以包含重复的元素。Set接口没有提供额外的方法，它的所有方法都来自于Collection接口。因此，Set接口主要用于存储不重复的元素，并进行快速的查找。

HashSet

HashSet是Set接口的一个实现类，它使用哈希表（实际上是一个HashMap实例）来存储元素。HashSet允许存储null值。HashSet不保证元素的顺序，特别是它不保证该顺序恒久不变。

HashSet 的clone()方法只是返回此 HashSet 实例的浅表副本：元素本身没有被克隆。

• 底层实现：HashSet 底层是由 HashMap 实现的。它存储元素实际上是将元素作为 HashMap 的键，而值则是一个固定的对象 PRESENT，它是一个空的 Object 实例。
• 特点：HashSet 不保证元素的顺序，并且允许包含一个 null 元素。
• 性能：HashSet 提供了常数时间性能的添加、删除和包含操作，假设哈希函数将元素正确地分散到各个桶中。

TreeSet

HashSet是基于哈希表实现的，它支持快速的查找，添加和删除操作，时间复杂度都是O(1)。但是，HashSet不保证元素的顺序。

TreeSet 底层是由 TreeMap 实现的。它使用红黑树（一种自平衡的二叉搜索树）来存储元素，每个元素都是树中的一个节点。TreeSet中的元素按照自然顺序排序，或者按照创建TreeSet时提供的Comparator进行排序。TreeSet的查找，添加和删除操作的时间复杂度都是O(log n)。

TreeSet实现了NavigableSet接口，因此它具有NavigableSet接口的所有方法，因此提供了一些额外的方法，如first(), last(), lower(), higher()等，这些方法在HashSet中是不支持的。

以下是TreeSet的一些主要方法：

方法签名	描述
first()	返回此 set 中当前第一个（最低）元素。
last()	返回此 set 中当前最后一个（最高）元素。
lower(E e)	返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。
floor(E e)	返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。
ceiling(E e)	返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。
higher(E e)	返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。
pollFirst()	移除并返回此 set 中当前第一个（最低）元素；如果此 set 为空，则返回 null。
pollLast()	移除并返回此 set 中当前最后一个（最高）元素；如果此 set 为空，则返回 null。
descendingSet()	返回此 set 中的元素的逆序视图。返回 set 的迭代器遍历元素的顺序与此 set 相反。
descendingIterator()	返回在此 set 中的元素上以逆序进行迭代的迭代器。
subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	返回此 set 的部分视图，其元素从 fromElement（包含）到 toElement（包含）。如果 fromElement 和 toElement 相等，返回的 set 为空，除非 fromInclusive 和 toInclusive 都为 true。
headSet(E toElement, boolean inclusive)	返回此 set 的部分视图，其元素小于（或等于，如果 inclusive 为 true）toElement。
tailSet(E fromElement, boolean inclusive)	返回此 set 的部分视图，其元素大于（或等于，如果 inclusive 为 true）fromElement。

LinkedHashSet

LinkedHashSet 底层是由 HashMap 和一个双向链表（LinkedList）实现的。每个元素既存储在哈希表中，也存储在双向链表中，链表定义了迭代顺序，即元素插入集合的顺序。

LinkedHashSet 维护了元素的插入顺序，因此迭代器会按照元素插入集合的顺序来遍历元素。

LinkedHashSet 提供了与 HashSet 相似的常数时间性能的添加、删除和包含操作，但由于维护了双向链表，它的性能略低于 HashSet。

Queue

Queue接口表示一个队列，它是一种特殊的线性表，只允许在表的前端（head）进行删除操作，和在表的后端（tail）进行插入操作。Queue接口提供了一些额外的方法，如offer(E e), poll(), peek()等，这些方法允许我们在队列的尾部添加元素，从队列的头部删除或检查元素。

以下是Queue接口的一些主要方法：

方法签名	描述
offer(E e)	将指定的元素插入到此队列中（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。
remove()	获取并移除此队列的头，如果此队列为空，则抛出 NoSuchElementException。
poll()	获取并移除此队列的头，如果此队列为空，则返回 null。
peek()	获取但不移除此队列的头，如果此队列为空，则返回 null。

Queue接口的主要实现类有LinkedList，PriorityQueue，ArrayDeque等。

• LinkedList：它是一个双向链表，实现了List和Deque接口，可以作为FIFO（先进先出）队列或者LIFO（后进先出）堆栈使用。
• PriorityQueue：它是一个优先队列，元素按照自然顺序或者提供的Comparator进行排序。头部元素是最小的元素（按照指定的排序方式）。
• ArrayDeque：它是一个基于数组的双端队列，可以作为FIFO（先进先出）队列或者LIFO（后进先出）堆栈使用，比Stack和LinkedList更高效。

PriorityQueue

PriorityQueue实现了Queue接口，具有Queue接口的所有特性。

PriorityQueue是一个优先队列，它的特点是每次取出的元素都是队列中权值最小的。元素的权值通过元素的自然顺序或者构造队列时传入的Comparator来确定。

PriorityQueue不允许插入null元素。队列的头部是按指定排序方式确定的最小元素。如果多个元素的排序相等，那么它们的顺序是不确定的。

以下是PriorityQueue的一些主要方法：

• comparator(): 返回用于对队列元素进行排序的比较器，或者如果此队列按照其元素的自然顺序进行排序，则返回null。

自定义比较

除了布尔型外，Java中的七种基本数据类型都可以使用小于号<、大于号>等进行比较。

一些Java类自带了比较方法compareTo()。compareTo()方法有且只有一个参数，该参数必须和使用该方法的类是同类的。

在自定义的Comparator比较过程中，遵循以下规范：

• 返回负数时，第一个参数应该排在前面，表示不需要交换位置，o1排在o2前面（升序排列）。
• 返回正数时，第二个参数应该排在前面，表示需要交换位置，o1排在o2后面（降序排列）。
• 返回0时，表示两个参数相等，无需交换位置。

在自定义的Comparator中：

• 返回负数或者-1，表示不需要交换位置，o1排在o2前面（升序排列）。
• 返回正数或者1，表示需要交换位置，o1排在o2后面（降序排列）。

ArrayDeque

PriorityQueue是一个优先队列，它的特点是每次取出的元素都是队列中权值最小的。元素的权值通过元素的自然顺序或者构造队列时传入的Comparator来确定。PriorityQueue 不允许存储 null 元素，相对于 ArrayDeque 而言，性能更多地侧重于维护元素的优先级顺序。

ArrayDeque是一个双端队列（deque，即double ended queue的缩写），它允许我们在队列的头部和尾部添加或删除元素。ArrayDeque内部使用一个动态数组来存储元素，当数组满时，它会自动增长。它也不允许存储 null 元素，并且不是线程安全的。

Map

Map 是 Java 中的一个接口，用于存储键值对映射关系的数据结构。它表示一种抽象的映射，其中每个键都唯一，并且可以通过键来获取对应的值。

同一个键不能重复出现在 Map 中，但值可以重复。如果将相同的键插入到 Map 中，新的值会覆盖原来的值。

在 Map 接口中，键和值都可以是任意对象，因此可以实现各种不同类型的映射关系。

Map 接口定义了常用的方法，如：

方法签名	描述
put(K key, V value)	向 Map 中添加键值对。
get(K key)	根据键获取对应的值。
containsKey(K key)	检查 Map 中是否包含指定的键。
remove(K key)	根据键移除对应的键值对。
keySet()	获取 Map 中所有的键集合。
values()	获取 Map 中所有的值集合。
entrySet()	获取包含键值对的集合。

Map接口的主要实现类有HashMap, TreeMap, LinkedHashMap和Hashtable等。

HashMap

HashMap是基于哈希表实现的，通过键的 hashCode 来快速定位值的存储位置，它允许存储null键和null值。HashMap不保证元素的顺序，特别是它不保证该顺序恒久不变。

HashMap是非同步的，它不支持多线程环境下的并发修改。HashMap 可以说是 Hashtable 的轻量级替代品，不具备同步特性，因此在单线程环境下性能更好。

Hashtable

Hashtable也是基于哈希表实现的，但是它不允许存储null键和null值。Hashtable也不保证元素的顺序。不同于HashMap，Hashtable是线程安全的，它支持多线程环境下的并发修改。

Hashtable 是 Java 早期版本中提供的一个线程安全的映射表实现。它的线程安全性是通过在每个公共方法上使用同步关键字 synchronized 来实现的。这意味着任何时候只有一个线程能够执行 Hashtable 的任何一个同步方法。这些方法包括 put, get, remove, size 等。内部锁机制确保了当一个线程正在执行这些方法时，其他线程必须等待直到锁被释放。

由于 Hashtable 使用了全局锁，这可能导致性能瓶颈。当一个线程占用锁时，其他所有需要访问 Hashtable 的线程都会被阻塞，即使是操作不同的数据项。因此，Hashtable 的并发性能并不理想，特别是在读多写少的场景下。

ConcurrentHashMap

ConcurrentHashMap 通过在内部使用分段锁技术（在 JDK 1.7 版本中）和利用 CAS 操作及 volatile 关键字（在 JDK 1.8 版本中）来实现线程安全。

ConcurrentHashMap 作为 Java 集合框架中的一个重要组成部分，解决了传统 HashMap 在并发环境下的线程安全问题。这种线程安全的实现方式不仅提高了并发操作的性能，还避免了显式同步带来的开销。

JDK 1.7版本的实现

1. 分段锁的结构：在 JDK 1.7 版本中，ConcurrentHashMap 采用数组加链表的形式实现，并且引入了 Segment 的概念。每一个 Segment 都可以看作是一个更小的哈希表，这些 Segment 本身是利用 ReentrantLock 进行加锁的。
2. 锁的精细化管理：通过分段锁技术，ConcurrentHashMap 将一个大锁分解为多个小锁，每个锁管理哈希表的一个段。这样，不同段上的操作可以由不同线程独立进行，减少了线程间的竞争，提高了并发性能。
3. 线程安全的保证：在进行 put 操作时，首先根据 key 的 hashcode 定位到具体的 Segment。一旦找到了对应的 Segment，线程就会对该 Segment 加锁，保证了在该 Segment 内的操作是原子性的，从而确保线程安全。

JDK 1.8版本的改进

1. 结构优化：在 JDK 1.8 版本中，ConcurrentHashMap 进行了结构上的优化，引入了红黑树结构。当链表长度过长时（默认超过 8），链表会转化为红黑树，以提高搜索性能。

2. 锁的粒度细化：与 JDK 1.7 显著不同的是，1.8 版本不再使用分段锁，而是直接对节点进行加锁。通过使用 volatile 关键字和 CAS (Compare-And-Swap) 操作来保证节点数据的可见性和操作的原子性。

3. 线程安全的进一步保证：在这个版本中，每次 put 操作都会通过 CAS 将自己的节点设置成当前键对应的值。如果多个线程同时执行 put 操作，只有其中一个能够成功执行 CAS 操作，其它线程则会失败并重新尝试，从而确保了线程安全。

4. 分桶锁:

   虽然 Java 8 版本的 ConcurrentHashMap 不再使用显式的分段锁，但它使用了一种称为分桶锁的技术来减少锁的范围。

   当需要对某个桶进行修改时，只锁定该桶，而不是整个表。

TreeMap

TreeMap 继承自 AbstractMap 类，实现了 NavigableMap 接口，提供了有序的键值对集合。

具体的，TreeMap是基于红黑树实现的，它的元素按照自然顺序排序，或者按照创建TreeMap时传入的Comparator进行排序。TreeMap不允许插入null键，但是允许插入null值。TreeMap是非同步的，它不支持多线程环境下的并发修改。

以下是TreeMap的一些主要方法：

• firstKey(): 返回此映射中当前第一个（最低）键。
• lastKey(): 返回此映射中当前最后一个（最高）键。
• subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive): 返回此映射的部分视图，其键的范围从fromKey（包含）到toKey（包含）。
• headMap(K toKey, boolean inclusive): 返回此映射的部分视图，其键的范围小于（或等于，如果 inclusive 为 true）toKey。
• tailMap(K fromKey, boolean inclusive): 返回此映射的部分视图，其键的范围大于（或等于，如果 inclusive 为 true）fromKey。

迭代器Iterator

迭代器是 Java 集合框架中的一种对象，用于遍历集合中的元素。通过迭代器，可以依次访问集合中的每个元素，而不需要了解集合的内部结构。

所有实现了 Collection 接口的集合类，都可以通过调用 iterator() 方法获取对应的迭代器对象。对于 Map 类型的集合，可以通过 keySet().iterator()、values().iterator()、entrySet().iterator() 等方法获取迭代器。

迭代器提供了三个基本的方法：hasNext()、next() 和 remove()。

• hasNext() 用于判断集合中是否还有下一个元素，如果有，则返回 true；否则返回 false。
• next() 用于获取下一个元素，并将迭代器的位置向后移动一个元素。
• remove() 用于从集合中安全地删除迭代器当前指向的元素，通常在使用 next() 方法之后调用。

通过迭代器，可以使用循环结构来遍历集合中的所有元素，在循环体内部可以使用 iterator.next() 来获取迭代器当前指向的元素。

while(iterator.hasNext()) { 
    ... 
    iterator.next();
    ... 
    iterator.remove();
}

迭代器的 remove() 方法可以在遍历集合的过程中安全地删除集合中的元素，而不会影响遍历的结果。使用 remove() 方法之前必须先调用 next() 方法，否则会抛出异常。

迭代器是单向的，只能从前向后遍历集合中的元素，不能逆向操作。