Java面向对象（高级）- 集合

bsfc.tech大约 18 分钟JavaJavaSE

Java 类集

类集实际上就是一个动态的对象数组，与一般的对象数组不同，类集中的对象内容可以任意扩充。

Map
- HashMap
- HashTable
- TreeMap
- LinkedHashMap
Collection
- List
  - Vector
  - ArrayList
  - LinkedList
- Set
  - HashSet
  - TreeSet
  - LinkedHashSet
- Queue
  - LinkedList
  - PriorityQueue

Map - HashMap

基于哈希表实现的无序键值对集合。

主要特点：

高效性：通过哈希表进行数据存储，可以实现近乎常数时间复杂度 O(1) 的插入、删除和查找操作（理想情况下）。
存储键值对：HashMap 可以存储任意类型的键值对，其中键 (Key) 和值 (Value) 都可以是任何对象类型。
无序：HashMap 中的元素没有顺序，添加顺序与取出顺序可能不一致。

创建和使用 HashMap 的基本示例：

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // 创建一个 HashMap 实例
        HashMap<String, Integer> map = new HashMap<>();

        // 添加键值对
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Cherry", 3);

        // 获取值
        int appleCount = map.get("Apple");  // 输出：1

        // 判断是否存在某个键
        boolean containsKey = map.containsKey("Banana");  // 输出：true

        // 删除键值对
        map.remove("Cherry");

        // 遍历 HashMap
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

注意

HashMap 在高并发环境下可能会导致数据不一致的问题，此时应考虑使用 ConcurrentHashMap。
如果映射的 Key 不重写 equals() 和 hashCode() 方法，或者方法实现得不好，可能导致无法正常存取或数据丢失等问题。因此，作为 HashMap 的 Key 的类需要正确且一致地实现这两个方法。

HashMap 在不同的JDK版本中有过显著的变化，以下是关于JDK 1.7和1.8版本之间实现差异的概述：

JDK 1.7中的HashMap实现：

结构：HashMap由一个数组和链表组成，每个数组桶(bucket)存储一个链表，当发生哈希冲突时（即多个键映射到同一个数组索引），这些键值对将被链接在这个链表中。
扩容机制：当HashMap中的元素数量超过阈值（threshold）时，会触发扩容操作，扩容后的新容量通常是原容量的两倍加一。
链表处理：对于哈希冲突，采用链地址法解决，也就是拉链法。插入新元素时，如果桶内已经有元素，就将新元素加入链表头部或尾部（取决于JDK版本，1.7之前是头插，1.7开始改为尾插，减少“逆序”的问题）。
性能：在某些情况下，如果链表很长，由于插入和查找都需要遍历链表，性能会退化到O(n)。

JDK 1.8中的HashMap改进：

结构：保留了数组+链表的基本结构，但在链表长度达到一定程度（默认8）后，链表会自动转换为红黑树（Red-Black Tree），从而优化了查找、插入和删除操作的性能，确保了最坏情况下的操作时间复杂度为O(log n)。
扩容机制：同样在元素数量超过阈值时进行扩容，但引入了一个新的概念“负载因子”（load factor），并且扩容后容量总是2的幂次方，这样可以利用位运算快速定位数组索引。
哈希算法：使用了一种称为“二次探测再散列”（double hashing）的技术来分散冲突，增加了高位参与计算索引位置，使得即使在扩容后，原有的键值对依然能够更均匀地分布到新的数组中。
初始化容量与预填充：提供了初始化时直接指定容量以及预填充因子的功能，以尽量避免多次扩容带来的性能损耗。

总结来说，JDK 1.8版本的HashMap相较于1.7版本，在处理大量哈希冲突时有了明显的性能提升，特别是在长期运行且存在大量冲突的情况下，通过红黑树的引入有效降低了操作的复杂度。同时，1.8版还对哈希算法进行了优化，提高了空间利用率和整体性能。

Map - HashTable

与 HashMap 类似，HashTable 也使用哈希表实现，但是有以下几点重要的不同之处：

线程安全性：HashTable 是线程安全的，这意味着在多线程环境下可以直接使用，而不需要外部同步控制。其内部的方法调用都会进行必要的锁操作来保证线程安全，但这也会导致其性能相比 HashMap 有所下降。
不允许 null 值：HashTable 不允许插入 null 键或 null 值，而 HashMap 允许键和值都为 null，但只能有一个 null 键。
设计年代较早：相比于 HashMap，HashTable 是一个较早的设计，从 Java 1.0 就已存在，而 HashMap 出现在 Java 1.2 版本中。因此，HashTable 并未使用 Java 5 引入的泛型。
迭代器：HashTable 返回的 Enumeration 在遍历时并不支持 remove() 操作，而 HashMap 返回的 Iterator 支持。

实践中，通常建议优先使用 ConcurrentHashMap（并发环境）或 HashMap（单线程环境）替代 HashTable，因为它们在性能和易用性上具有优势。只有在需要兼容老代码或特别关注线程安全但又不想使用 ConcurrentHashMap 的场景下，才可能会选择使用 HashTable。

Map - TreeMap

与 HashMap 和 HashTable 不同的是，TreeMap 使用红黑树（Red-Black Tree）作为底层数据结构。

主要特点：

排序特性：TreeMap 的键是根据键的自然顺序（如果键实现了 Comparable 接口）或自定义比较器（通过构造函数传递 Comparator 对象）进行排序的。因此，它始终按照排序顺序维护元素，并提供了如 firstKey()、lastKey()、lowerKey()、higherKey() 等用于获取排序范围内的键的方法。
访问性能：对于包含 n 个元素的 TreeMap，插入、删除和查找的时间复杂度大致为 O(log n)，这是因为红黑树的平衡特性保证了查询效率。
键值对操作：除了常规的增删查改操作外，TreeMap 还支持按照键的顺序进行遍历。

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();

        // 添加键值对
        treeMap.put("Apple", 1);
        treeMap.put("Banana", 2);
        treeMap.put("Cherry", 3);

        // 自然排序
        System.out.println(treeMap);  // 输出按字典顺序排序的键值对

        // 定义自定义比较器
        TreeMap<Integer, String> customSortedMap = new TreeMap<>(Collections.reverseOrder());
        customSortedMap.put(3, "Three");
        customSortedMap.put(1, "One");
        customSortedMap.put(2, "Two");

        // 按自定义顺序排序
        System.out.println(customSortedMap);  // 输出按降序排列的键值对

        // 获取最小和最大键
        System.out.println("First key: " + treeMap.firstKey());
        System.out.println("Last key: " + treeMap.lastKey());
    }
}

Map - LinkedHashMap

继承自 HashMap 类，同时实现了 Map 接口。LinkedHashMap 继承了 HashMap 的所有特性，但增加了一个特性——维护插入顺序或访问顺序。

主要特点：

双向链表：LinkedHashMap 内部使用哈希表和双向链表相结合的方式来存储数据，因此它可以记住元素的插入顺序或最近访问顺序。
- 插入顺序模式：默认情况下，LinkedHashMap 会按照插入顺序维护元素的顺序，即先插入的元素在迭代时会先出现。
- 访问顺序模式：可以通过设置构造函数参数 accessOrder 为 true 来启用访问顺序模式。在这种模式下，每当访问（get 或 put）一个元素时，该元素就会移动到链表的末尾，因此迭代输出的顺序就是最近访问过的元素顺序。
性能：由于额外维护了一个双向链表，所以相对于 HashMap，LinkedHashMap 的插入、删除和查找操作可能会稍慢一些，但在大多数情况下，这种性能影响是可以接受的。

使用示例：

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

public class Main {
    public static void main(String[] args) {
        // 插入顺序示例
        LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("Apple", 1);
        linkedHashMap.put("Banana", 2);
        linkedHashMap.put("Cherry", 3);

        // 遍历输出，按插入顺序
        for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 访问顺序示例
        LinkedHashMap<String, Integer> accessOrderedMap = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderedMap.put("Apple", 1);
        accessOrderedMap.put("Banana", 2);
        accessOrderedMap.put("Cherry", 3);

        // 访问元素，然后再次遍历输出，按访问顺序
        System.out.println(accessOrderedMap.get("Banana"));
        for (Map.Entry<String, Integer> entry : accessOrderedMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

总结来说，LinkedHashMap 在需要维持元素插入顺序或访问顺序的应用场景下非常有用，比如缓存系统（LRU策略）等。

Collection - List - Vector

在 Java 中，java.util.Vector 是早期版本集合框架的一部分，也是基于数组实现的，它除了具备类似 ArrayList 的特性外，还自带线程安全机制，这意味着它在多线程环境下的操作会自动同步，但这也会带来一定的性能开销。从 Java 1.2 开始，推荐使用 ArrayList 代替 Vector，除非确实需要线程安全功能。

Collection - List - ArrayList

基于动态数组实现的，能够以对象引用的形式存储一系列元素，并且这些元素在 ArrayList 中是有序的，可以通过索引进行访问。

主要特点：

动态扩容：当向 ArrayList 中添加元素，如果当前容量不足以容纳新元素时，ArrayList 会自动扩展其内部数组的大小，通常是扩大为原来的 1.5 倍（默认策略）。
可变大小：ArrayList 的大小不是固定的，可以根据需要增加或减少元素的数量。
访问速度快：由于 ArrayList 内部采用数组存储，因此通过索引访问元素的时间复杂度为 O(1)，即常数时间访问。
插入和删除操作：在 ArrayList 的中间位置插入或删除元素时，需要移动后续元素，所以插入和删除操作（非尾部）的时间复杂度一般为 O(n)。
允许重复元素：ArrayList 可以包含重复的元素，并且保持元素的插入顺序。
不是线程安全的：在多线程环境下，如果不采取额外的同步措施，直接对 ArrayList 进行读写操作可能会导致数据不一致。若需要线程安全的 List，可以使用 Collections.synchronizedList(new ArrayList<...>()) 方法将其包装成线程安全的 List。

使用示例：

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        System.out.println(list.get(0));  // 输出 "Apple"
        list.remove(1);  // 删除第二个元素 "Banana"
        list.add(1, "Durian");  // 在索引1的位置插入"Durian"
        System.out.println(list);  // 输出 ["Apple", "Durian", "Cherry"]
    }
}

自动扩容：

初始容量：默认初始容量为10。
扩容条件：添加元素，超过ArrayList的大小，就需要进行扩容。
扩容策略：数组扩容通过ensureCapacity(int minCapacity)方法来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量。通常扩容当前容量翻倍（实际上大约增加50%，即原容量的1.5倍），该操作代价很高，实际使用时，应该尽量避免数组容量的扩张。

快速失败（Fail-Fast）机制：

Fail-Fast机制是Java集合(Collection)的一种错误传播机制，当多个线程对集合进行结构上的改变时，有可能会产生Race Condition（竞态条件），当出现这种情况时，ArrayList会尽快的抛出ConcurrentModificationException异常。

错误示例

public class FailFastExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            if (item.equals("B")) {
                list.remove(item); // 错误方式，会引发Fail-Fast机制
            }
        }
    }
}

正确示例

public class FailFastExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            if (item.equals("B")) {
                iterator.remove(); // 正确方式，使用Iterator的remove方法
            }
        }
    }
}

Collection - List - LinkedList

一种链表结构，由一系列节点（Node）组成，每个节点包含一个元素和指向下一个节点的引用。

主要特点：

结构特性：LinkedList 分为双向链表和单向链表两种形式。Java 中的 LinkedList 实现的是双向链表，每个节点都有前驱和后继节点的引用。相比于 ArrayList 使用连续的内存空间存储元素，LinkedList 的元素在内存中分布不一定连续。
动态增长：与 ArrayList 类似，LinkedList 的大小也是可变的，可以在任意位置添加或删除元素。
访问速度：访问 LinkedList 中的元素需要从头或尾节点开始沿着引用逐个查找，所以通过索引访问元素的时间复杂度为 O(n)。但在首尾节点处的添加和删除操作（addFirst(), addLast(), removeFirst(), removeLast()）的时间复杂度为 O(1)。
插入和删除操作：在 LinkedList 中插入或删除元素（不仅仅是首尾），不需要像 ArrayList 那样移动其他元素，所以在非首尾位置插入和删除元素的时间复杂度也仅为 O(1)。
允许重复元素：LinkedList 同样可以包含重复的元素，并且保持元素的插入顺序。
不是线程安全的：和 ArrayList 一样，在多线程环境下，如果不采取额外的同步措施，直接对 LinkedList 进行读写操作可能会导致数据不一致。

使用示例：

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        System.out.println(list.peek());  // 输出 "Apple"，查看但不移除第一个元素
        list.removeFirst();  // 移除并返回第一个元素 "Apple"
        list.add("Durian");  // 添加到末尾
        list.add(1, "Elderberry");  // 在索引1的位置插入"Elderberry"
        System.out.println(list);  // 输出 ["Banana", "Elderberry", "Cherry", "Durian"]
    }
}

Collection - Set - HashSet

不允许存储重复元素，并且没有元素的顺序性保证。

主要特点：

存储唯一性：HashSet 使用哈希表（HashMap）的方式来存储元素，通过元素的 hashCode() 方法计算哈希值并确定存储位置，如果有两个元素的hashCode相同且equals方法也认为它们相等，则只存储其中一个。
无序性：HashSet 不保证元素的迭代顺序，每次遍历的结果可能不同，特别是当集合被修改后。
查找速度快：由于 HashSet 采用了哈希算法，因此对于插入、删除和查找操作具有较好的性能，理想情况下，这些操作的时间复杂度接近 O(1)。
不是线程安全的：如同大多数 Java 集合类，HashSet 在多线程环境下如果不做额外同步处理，直接进行读写操作可能会引发数据不一致的问题。如果需要线程安全的 Set，可以使用 Collections.synchronizedSet(new HashSet<...>()) 封装得到。

使用示例：

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Apple");  // 尝试添加已存在的元素不会成功

        System.out.println(set.contains("Cherry"));  // 输出 false，集合中不含 "Cherry"
        set.add("Cherry");
        System.out.println(set);  // 输出 [Apple, Banana, Cherry]，注意元素的顺序可能变化
    }
}

Collection - Set - TreeSet

基于红黑树（Red-Black Tree）数据结构的。支持有序性操作。

主要特点：

排序性：TreeSet中的元素是自动排序的，可以按照元素的自然顺序（如Integer、String等），也可以通过提供自定义的Comparator来进行排序。
无重复元素：作为集合的一种，TreeSet不允许存储重复的元素。
高效查找：由于内部采用红黑树的数据结构，对于添加、删除和查找操作的时间复杂度都是O(log n)。
导航方法：由于实现了NavigableSet接口，所以提供了丰富的导航方法，如 ceiling(), floor(), higher(), lower() 等，可以根据给定元素获取其上界、下界以及相邻的更大或更小的元素。

使用示例：

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Cherry");

        // 自动排序
        System.out.println(treeSet);  // 输出：[Apple, Banana, Cherry]

        // 添加重复元素无效
        treeSet.add("Apple"); 
        System.out.println(treeSet);  // 输出不变

        // 查找元素
        if (treeSet.contains("Banana")) {
            System.out.println("找到了Banana");
        }
    }
}

如果需要自定义排序，可以在创建TreeSet时传入一个Comparator对象：

TreeSet<String> treeSet = new TreeSet<>(new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();  // 按字符串长度排序
    }
});

Collection - Set - LinkedHashSet

同时实现了 Set 和 Map 接口，结合了 HashSet 和 LinkedList 的特性。 LinkedHashSet 存储的元素是无序且唯一的，但它维护了一个元素插入的顺序，即插入的顺序与迭代输出的顺序一致。

主要特点：

唯一性：同 HashSet 一样，LinkedHashSet 也不允许存储重复元素，通过调用元素的 hashCode() 和 equals() 方法确保元素的唯一性。
有序性：虽然不像 List 那样严格保持插入顺序，但是 LinkedHashSet 通过链接每个元素（使用双向链表）来维护元素的插入顺序。这意味着当你遍历 LinkedHashSet时，元素将会按照它们被添加到集合中的顺序出现。
查找速度：由于它底层依赖于哈希表（HashMap）和双向链表，插入、删除和查找操作的平均时间复杂度接近 O(1)。
不是线程安全的：LinkedHashSet 同样不是线程安全的，如果需要在多线程环境下使用，需要自行进行同步控制。

使用示例：

import java.util.LinkedHashSet;

public class Main {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Apple");  // 尝试添加已存在的元素不会成功
        set.add("Cherry");

        System.out.println(set);  // 输出 [Apple, Banana, Cherry]，按插入顺序排列
    }
}

Collection - Queue - LinkedList

采用链表（Linked List）的方式来存储元素。 LinkedList 可分为双端链表和单端链表，Java 中的 LinkedList 类实现的是双端链表，每个节点（Node）包含元素和指向前后节点的引用。

主要特点：

结构特性：LinkedList 中的元素在内存中并非连续存储，而是分散存储，每个元素（节点）之间通过引用相连。
动态增长：LinkedList 的大小是可变的，可以在头部、尾部或任何位置方便地添加或删除元素。
访问速度：由于链表的特性，访问 LinkedList 中的元素需要从头节点或尾节点开始沿着引用遍历，因此通过索引访问元素的时间复杂度为 O(n)。但在首尾节点处的添加和删除操作（addFirst(), addLast(), removeFirst(), removeLast()）的时间复杂度为 O(1)。
插入和删除操作：在 LinkedList 中，无论在哪一个位置插入或删除元素，只需要改变相应节点的前后引用，所以插入和删除操作（非首尾位置）的时间复杂度也为 O(1)，相比数组（如 ArrayList）在中间位置插入或删除更高效。
允许重复元素：LinkedList 同样可以存储重复的元素，并且根据元素加入的顺序形成链式结构。
不是线程安全的：LinkedList 对象在多线程环境下直接进行读写操作时同样可能存在线程安全问题，需要用户自行进行同步控制。

使用示例：

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.addFirst("Apple");  // 在头部添加元素
        list.addLast("Banana");  // 在尾部添加元素
        list.add(1, "Cherry");  // 在索引为1的位置插入元素

        System.out.println(list.pollFirst());  // 输出并移除第一个元素 "Apple"
        System.out.println(list.peekLast());  // 输出但不移除最后一个元素 "Banana"

        list.removeLastOccurrence("Cherry");  // 移除最后一个出现的"Cherry"
        System.out.println(list);  // 输出 ["Banana"]
    }
}

Collection -Queue - PriorityQueue

实现了 Queue 接口，主要用于存储优先级队列中的元素。在这个队列中，元素被赋予优先级，每次取出的元素都是具有最高优先级（或者说最低优先级，取决于如何定义优先级顺序）的元素。

主要特点：

排序原则：PriorityQueue 默认按自然顺序（Comparable 自然排序）或提供的 Comparator 来对元素进行排序。这意味着元素必须实现 Comparable 接口，或者在创建 PriorityQueue 时提供一个 Comparator。
堆结构：PriorityQueue 在内部采用了一种称为“堆”的数据结构来组织元素，堆是一种特殊的完全二叉树，满足父节点的值总是小于（或大于）其子节点的值，这确保了队列顶部始终是优先级最高的元素。
插入与删除操作：插入操作（add 或 offer）将元素放在正确的位置以维持堆的性质，删除操作（poll 或 remove）会移除并返回优先级最高的元素。
无界与有界：默认情况下，PriorityQueue 是无界的，但如果在构造时提供了初始容量和最大容量参数，那么它可以变为有界的队列。
非线程安全：和许多 Java 集合类一样，PriorityQueue 本身不是线程安全的，如果需要在多线程环境中使用，需要外部进行同步控制。

使用示例：

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // 创建一个优先级队列，元素按照升序排序
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 添加元素
        pq.offer(3);
        pq.offer(1);
        pq.offer(5);

        // 按优先级（升序）取出元素
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());  // 输出顺序将是 1, 3, 5
        }
    }
}

如果你想自定义优先级顺序，可以创建一个实现了 Comparator 的类，然后在构造 PriorityQueue 时传入这个 Comparator：

import java.util.Comparator;
import java.util.PriorityQueue;

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" + "name='" + name + '\'' + ", age=" + age + '}';
    }
}

Comparator<Person> personComparator = Comparator.comparingInt(Person::getAge);

PriorityQueue<Person> queue = new PriorityQueue<>(personComparator);

queue.offer(new Person("Alice", 25));
queue.offer(new Person("Bob", 30));
queue.offer(new Person("Charlie", 20));

while (!queue.isEmpty()) {
    System.out.println(queue.poll());  // 根据年龄从小到大输出
}