集合框架篇

Java 中常用的集合框架有哪些？它们之间的区别是什么？

Java 中常用的集合框架主要包括以下几种：List、Set、Map 和 Queue。

List（列表）：
- List 是一个有序的集合，允许存储重复元素。常见的实现类有 ArrayList、LinkedList 和 Vector；
- ArrayList 是基于动态数组实现，适用于随机访问；
- LinkedList 是基于双向链表实现，适用于插入和删除操作频繁的情况；
- Vector 类似于 ArrayList，但线程安全。
Set（集合）：
- Set 是一个不允许存储重复元素的集合。常见的实现类有 HashSet、LinkedHashSet 和 TreeSet；
- HashSet 使用哈希表实现，具有快速的查找性能；
- LinkedHashSet 在 HashSet 的基础上保留了元素的插入顺序；
- TreeSet 使用红黑树实现，具有自然排序和自定义排序的能力。
Map（映射）：
- Map 是一种键值对的数据结构，存储一组关联的对象。常见的实现类有 HashMap、LinkedHashMap 和 TreeMap；
- HashMap 使用哈希表实现，允许一个键对应一个值，但不保证元素的顺序；
- LinkedHashMap 在 HashMap 的基础上保留了元素的插入顺序；
- TreeMap 使用红黑树实现，根据键的自然排序或自定义排序存储键值对。
Queue（队列）：
- Queue 是一种先进先出（FIFO）的数据结构，常用于实现任务调度等场景；常见的实现类有 LinkedList 和 PriorityQueue；
- LinkedList 可以用作队列或双向队列；
- PriorityQueue 使用堆实现，允许根据元素的优先级进行访问。

这些集合框架有着不同的特点和适用场景：

List 适用于需要有序存储且允许重复元素的场景。
Set 适用于需要存储不重复元素的场景。
Map 适用于需要存储键值对的场景，可以快速根据键查找值。
Queue 适用于需要实现先进先出或优先级队列的场景。

选择合适的集合框架取决于具体的需求和数据操作。不同的实现类在性能和特性方面可能存在差异，开发者应根据具体情况做出选择。此外，Java 集合框架还包括了一些其他的接口和类，如迭代器（Iterator）、集合工具类（Collections）等，用于辅助集合操作和管理。

为什么要使用集合？

当我们需要保存一组类型相同的数据时，我们应该使用一个容器来保存，这个容器就是数组。

但是，使用数组存储对象有一定的弊端，因为我们在实际开发中，存储的数据类型是多种多样的。于是就出现了集合的概念，集合同样也是用来存储多组数据的。

数组的缺点是一旦声明过后，长度就不可变了，同时声明时数组的数据类型也决定了该数组存储的数据类型，而且数组存储的数据是有序的、可重复的，特点单一。但是集合提高了存储数据的灵活性，Java 集合不仅可以用来存储不同类型、不同数量的对象，还可以保存具有映射关系的数据。

如何选用集合？

主要根据集合的特点来选用，比如我们需要根据键获取元素的值时就选用 Map 接口下的集合，需要排序时选用 TreeMap，不需要排序就使用 HashMap，需要保证线程安全就使用 ConcurrentHashMap。

当我们只需要存放元素的值时，就选择实现 Collection 接口的集合，需要保证元素唯一时就使用 Set 接口的集合，例如 TreeSet、HashSet，不需要保证元素唯一性就选择 List 接口下的集合，例如 ArrayList、LinkedList，然后再根据实现这些接口的集合特点来选用。

Collections 工具类中的 sort() 方法如何比较元素？

Collections 工具类中的 sort() 方法用于对集合中的元素进行排序。排序是通过元素的自然顺序（natural order）或者通过提供的比较器（Comparator）来进行的，具体取决于调用的方法签名。

如果使用没有提供比较器的 sort() 方法，那么排序将使用元素的自然顺序。要使用自然顺序进行排序，集合中的元素必须实现 Comparable 接口，该接口定义了元素之间的比较规则。在这种情况下，排序将调用元素的 compareTo() 方法来进行比较。

如果使用提供了比较器的 sort() 方法，那么排序将使用指定的比较器。比较器是一个实现了 Comparator 接口的对象，它定义了一种自定义的比较规则。在这种情况下，排序将调用比较器的 compare() 方法来进行比较。

下面是一个示例，展示了如何使用 Collections.sort() 方法来排序一个列表。第一个排序使用了自然顺序（字典顺序），第二个排序使用了自定义的比较器（按字符串长度）。根据需要，可以根据元素的特定属性或标准来选择合适的排序方式。：

java

public class SortingExample {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");

        // 使用自然顺序进行排序
        Collections.sort(names);
        System.out.println("Sorted names: " + names);

        // 使用自定义比较器进行排序（按长度）
        Collections.sort(names, (a, b) -> Integer.compare(a.length(), b.length()));
        System.out.println("Sorted names by length: " + names);
    }
}

Collection 和 Collections 有什么区别？

Collection 和 Collections 是 Java 集合框架中两个不同的概念和类：

Collection：
- Collection 是 Java 集合框架的基本接口，它代表了一组对象的容器。
- Collection 接口派生出了许多子接口，如 List、Set 和 Queue，它们分别表示列表、集合和队列等不同的集合类型。
- Collection 接口定义了许多用于操作集合元素的方法，如添加、删除、查找等。
Collections：
- Collections 是 Java 集合框架中的一个实用类，提供了一组静态方法，用于操作和处理集合。
- Collections 类中的方法包括排序、查找、填充、复制等各种集合操作，以及返回不可修改（不可变）集合的方法。
- Collections 类不是接口，而是一个包含静态方法的工具类。

总结：

Collection 是一个接口，代表集合框架中的集合类型，定义了集合操作的方法。
Collections 是一个实用类，提供了各种静态方法，用于操作和处理集合，例如排序、查找等。

什么是 CopyOnWriteArrayList？

CopyOnWriteArrayList 是 Java 集合框架中的一个线程安全的 List 实现类，它通过在修改操作（如添加、删除元素）时复制整个内部数组来实现线程安全性。即不对原数组进行操作，而是复制一份新的数组，然后在新数组上进行操作，完成后原来的指针指向新数组。

CopyOnWriteArrayList 的优缺点如下：

优点：

线程安全：CopyOnWriteArrayList 是线程安全的，多个线程可以同时读取集合，而不会出现并发修改异常。
无需加锁：CopyOnWriteArrayList 无需加锁，因为写操作是在复制的新数组上进行的，不会影响读操作。
适用于读多写少的场景：CopyOnWriteArrayList 适用于读多写少的场景，因为写操作需要复制整个数组，性能开销较大。

缺点：

内存占用：CopyOnWriteArrayList 在写操作时需要复制整个数组，因此会占用额外的内存空间。
写操作性能：由于写操作需要复制整个数组，因此写操作的性能较低，不适用于写操作频繁的场景。
读操作性能：读操作的性能较高，因为读操作无需加锁，多个线程可以同时读取集合。
一致性问题：CopyOnWriteArrayList 无法保证实时性，即写操作完成后，读操作可能仍然读取到旧数据。

如下面的例子中，在单线程环境下执行可能正常，但是在多线程环境下执行就可能会出现异常。

java

public class Main {

    private static List<String> list = new ArrayList<>();

    public static void main(String[] args) {
        list.add("1");
        list.add("2");
        list.add("3");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            System.out.println(next);
        }
        System.out.println(Arrays.toString(list.toArray()));
    }
}

按照上面的例子，再多线程环境下执行迭代的同时对该集合进行增删操作，就会出现 ConcurrentModificationException 异常。

java

public class Main2 {

    private static List<String> list = new ArrayList<>();

    public static void main(String[] args) {
        list.add("1");
        list.add("2");
        list.add("3");

        // 开启线程池
        ExecutorService service = Executors.newFixedThreadPool(10);
        for (int i = 0; i < 10; i++) {
            service.execute(() -> {
                for (int j = 0; j < 5; j++) {
                    list.add("5");
                }
            });
        }

        // 读取 list
        Iterator<String> iterator = list.iterator();
        for (int i = 0; i < 10; i++) {
            service.execute(() -> {
                while (iterator.hasNext()) {
                    String next = iterator.next();
                    System.out.println(next);
                    try {
                        Thread.sleep(10);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
        }

        // 关闭线程池
        service.shutdown();
    }
}

bash

Exception in thread "pool-1-thread-4" Exception in thread "pool-1-thread-1" Exception in thread "pool-1-thread-3" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
	at com.hyd.demo.Main2.lambda$main$1(Main2.java:38)

原因是在多线程场景下，一个线程在迭代集合的同时，另一个线程对集合进行了增删操作，导致了集合的结构发生了变化，从而抛出了并发修改异常。

在 CopyOnWriteArrayList 源码中，add(E e) 方法在写操作时先使用 synchronized 关键字加锁，然后复制一份新的数组，最后将新数组赋值给原数组。

java

public boolean add(E e) {
   synchronized (lock) {
      Object[] es = getArray();
      int len = es.length;
      es = Arrays.copyOf(es, len + 1);
      es[len] = e;
      setArray(es);
      return true;
   }
}

而读操作则不需要加锁，直接读取原数组的数据。

java

@SuppressWarnings("unchecked")
public E next() {
   if (!hasNext())
      throw new NoSuchElementException();
   return (E) snapshot[cursor++];
}

解决例子里的 ConcurrentModificationException 异常的方法就是使用 CopyOnWriteArrayList 类。

java

private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

Arrays.asList()

Arrays.asList() 方法是 Java 集合框架中的一个工具方法，用于将数组转换为 List 集合。它的作用是将数组转换为一个固定长度的 List，这个 List 的长度是不可变的，即不能添加或删除元素。

例如下面的例子中，将一个数组转换为 List 集合：

java

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        List list = Arrays.asList(arr);
        System.out.println("size: " + list.size());
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

可以看到运行结果报错：

查看 Arrays.asList() 方法的源码可以发现，该方法的参数是一个泛型可变参数，而 int[] 类型是一个基本数据类型数组，不能作为泛型参数。

java

@SafeVarargs
@SuppressWarnings("varargs")
public static <T> List<T> asList(T... a) {
   return new ArrayList<>(a);
}

解决方法是将基本类型数组转换为包装类型数组，如下所示：

java

Integer[] arr = {1, 2, 3, 4, 5};

紧接着，对于 Arrays.asList() 方法返回的 List 集合，它的长度是固定的，不能添加或删除元素，但可以修改元素的值。

例如下面的例子，尝试向 List 集合中添加元素，会抛出 UnsupportedOperationException 异常。

java

public class Main {
    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5};
        List list = Arrays.asList(arr);
        System.out.println("size: " + list.size());
        list.add(6);
    }
}

查看 Arrays.asList() 方法的源码可以发现，返回的 List 集合是 Arrays 的内部类 ArrayList 而不是我们通常使用的 java.util 包下的 ArrayList，它继承自 AbstractList 类，但没有实现 add() 方法。

java

private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable {
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }

    public E set(int index, E element) {
        E oldValue = a[index];
        a[index] = element;
        return oldValue;
    }

    public E get(int index) {
        return a[index];
    }

    public int size() {
        return a.length;
    }
}

既然没有实现 add() 方法，那代码是如何编译通过的呢？这是因为 Arrays.asList() 方法返回的 List 集合是一个抽象类 AbstractList 的子类，而 AbstractList 类中实现了 add() 方法，但是抛出了 UnsupportedOperationException 异常。

同样，remove() 方法也会抛出 UnsupportedOperationException 异常。

java

public void add(int index, E element) {
   throw new UnsupportedOperationException();
}

public E remove(int index) {
   throw new UnsupportedOperationException();
}

除了上面介绍的问题外，Arrays.asList() 方法还有一个需要注意的地方，那就是对原数组的修改会影响到返回的 List 集合。

java

public class Main {
    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5};
        List list = Arrays.asList(arr);
        System.out.println("添加前：");
        list.forEach(i -> System.out.print(i + " "));
        System.out.println();
        System.out.println("添加后：");
        arr[0] = 6;
        list.forEach(i -> System.out.print(i + " "));
    }
}

这是因为 Arrays.asList() 方法返回的 List 集合是 ArrayList 的一个视图 a，它持有原数组的引用，对原数组的修改会影响到返回的 List 集合。

解决方法是将返回的 List 集合转换为 ArrayList 集合，如下所示：

java

List list = new ArrayList(Arrays.asList(arr));

ArrayList.subList()

ArrayList.subList() 方法是 Java 集合框架中 ArrayList 类的一个方法，用于获取 ArrayList 集合的子列表。它的作用是返回一个包含指定范围元素的视图，即返回一个新的 List 集合，包含从 fromIndex 到 toIndex 的元素。

如下示例中，将 ArrayList.subList() 方法值强转为 ArrayList 类型，会抛出 ClassCastException 异常。

java

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<String>() {{
            add("Tom");
            add("Jerry");
            add("Spike");
        }};
        ArrayList list = (ArrayList) names.subList(0, 1);
        System.out.println(list);
    }
}

同样查看 subList() 方法的源码可以发现是一个接口方法，点击跳转到其实现类 ArrayList 的 subList() 方法，可以看到返回的是一个内部类 SubList。

由于 SubList 实际上并没有创建一个新的 List 集合，而是使用 this.parent = parent; 将原 ArrayList 的引用赋值给了 SubList，因此无法强转为 ArrayList 类型。

并且引用的是原 ArrayList 的引用，对 SubList 的添加、删除和修改操作会影响到原 ArrayList。

红黑树

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树（Binary Search Tree）数据结构，它在插入和删除操作后会通过一系列的旋转和重新着色来维持树的平衡，以保证树的高度近似于对数时间复杂度，从而保证了树的查找、插入和删除等操作的高效性能。

红黑树具有以下性质：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（NIL 节点，通常表示空节点）都是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的（不能有两个相邻的红色节点）。
从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（黑色高度相等）。

这些性质保证了红黑树的平衡性，使得最长路径不会超过最短路径的两倍，从而保证了树的查找、插入和删除操作的时间复杂度稳定在对数级别。

红黑树在计算机科学中被广泛应用，特别是在实现数据库索引、平衡查找树（如 C++ 中的 std::map 和 std::set、Java 中的 TreeMap 和 TreeSet）以及其他需要高效插入、删除和查找操作的场景中。虽然红黑树的操作相对复杂，但由于其平衡性能，它在大多数情况下都能保持高效的性能。

有了二叉搜索树，为什么还需要平衡二叉树？

虽然二叉搜索树（Binary Search Tree，BST）是一种有效的数据结构，能够支持快速的插入、删除和查找操作，但在某些情况下，普通的二叉搜索树可能会出现不平衡的情况，导致操作的性能退化。这时，平衡二叉树（Balanced Binary Tree）应运而生，它是一种特殊类型的二叉搜索树，保持了树的平衡性，从而确保操作的时间复杂度始终保持在较低的水平。

主要原因如下：

避免退化为链表：在某些情况下，普通的二叉搜索树可能会退化成类似链表的结构，使得树的高度接近于节点数量，导致操作的平均时间复杂度从理论上的 O(log N) 变为 O(N)。平衡二叉树通过维护平衡性，确保树的高度保持在较低水平，从而避免了这种退化。
保持高效操作：平衡二叉树的平衡性保证了树的高度相对较低，因此插入、删除和查找等操作的时间复杂度仍然保持在 O(log N) 的水平，即使是在较大规模的数据集中也能保持较高的性能。
应对数据分布变化：数据集的动态性质可能导致普通的二叉搜索树变得不平衡，而平衡二叉树能够自动适应数据分布的变化，保持树的平衡性。
支持高效的范围查询：平衡二叉树的平衡性使得范围查询（如查找某个范围内的所有元素）更加高效，而普通的二叉搜索树可能需要更多的遍历操作。

常见的平衡二叉树包括红黑树、AVL 树等。这些数据结构通过旋转、调整节点等操作来维护树的平衡性，从而保证了高效的操作性能。总之，平衡二叉树的引入是为了解决普通二叉搜索树在某些情况下可能出现的性能问题，确保操作始终能够保持在较低的时间复杂度。

有了平衡二叉树，为什么还需要红黑树？

红黑树（Red-Black Tree）是一种特殊类型的平衡二叉树，它具有一些特定的性质，使得在插入、删除和查找等操作时能够保持树的平衡性。尽管平衡二叉树可以解决某些不平衡树的问题，但红黑树仍然有其独特的优势和用途，这是因为红黑树具有更加严格的平衡性和性能保证。

以下是为什么还需要红黑树的原因：

更加严格的平衡性：红黑树在平衡性方面比一般的平衡二叉树更加严格。红黑树通过遵循一些特定的规则，保证了树的高度保持在相对较小的范围内，从而提供了更高效的插入、删除和查找操作。
操作性能保证：红黑树在最坏情况下的插入、删除和查找操作的时间复杂度都是 O(log N)，这对于实时系统、数据库、编译器等对性能要求较高的应用非常重要。红黑树的性能保证使得它在这些应用中具有优势。
简单而高效的操作：红黑树的操作规则相对简单，不同于其他平衡二叉树如 AVL 树需要更复杂的平衡操作。这使得红黑树在实现上相对较为容易，并且在性能方面仍然具有优越性。
广泛的应用：红黑树被广泛用于许多标准库、数据库、操作系统内核等领域，因为它提供了稳定的性能和较低的操作复杂性。

尽管红黑树在某些操作上可能相对于其他平衡二叉树来说会稍微昂贵一些（例如，与 AVL 树相比），但其性能保证和广泛的应用领域使得它仍然是一个重要且有价值的数据结构。总之，红黑树是一种具有特定优势和特性的平衡二叉树，它填补了普通平衡二叉树在某些应用中的性能和稳定性要求。

有数组了为什么还要 ArrayList 呢？

通常我们在使用 Array 的时候，如果在不明确要插入多少数据的情况下，普通数组因为不知道需要初始化数组大小为多少，而 ArrayList 可以使用默认的大小，当元素个数到达一定程度后，会自动扩容。

可以这么来理解：我们常说的数组是定死的数组，ArrayList 却是动态数组。

Array 和 ArrayList 有什么区别？

Array（数组）和 ArrayList（动态数组）都是用来存储一组元素的数据结构，但它们之间有一些重要的区别：

Array（数组）：

数组是一种固定长度的数据结构，一旦创建后，其长度是不可改变的。
数组可以存储基本数据类型（如 int、char 等）和对象类型（如 String、自定义类等）。
访问数组元素的时间复杂度是 O(1)，即常数时间，因为数组的元素在内存中是连续存储的，可以通过索引直接访问。
在需要频繁访问元素、且元素数量固定的情况下，数组是一个有效的选择。

ArrayList（动态数组）：

ArrayList 是 Java 集合框架中的一个实现类，是基于数组实现的动态数组。
ArrayList 的长度是可以动态增长和缩小的，可以根据需要自动调整大小。
ArrayList 只能存储对象类型（即类对象），而不能存储基本数据类型，但可以使用对应的包装类（如 Integer、Double）。
访问 ArrayList 中的元素的时间复杂度是 O(1)，但在需要扩容时可能会有一定的性能开销。
ArrayList 提供了丰富的方法来方便地添加、删除、查找和遍历元素，适用于需要动态改变长度的情况。

总结：

Array 是固定长度的数据结构，适用于元素数量已知且不需要频繁改变的情况。
ArrayList 是动态数组，可以自动调整大小，适用于元素数量不确定或需要频繁改变的情况。

ArrayList 和 LinkedList 之间的区别是什么？

ArrayList 和 LinkedList 都是 Java 集合框架中常用的列表（List）实现类，它们有一些重要的区别：

线程安全性：ArrayList 和 LinkedList 都是同步的，因此都是线程不安全的。
内部实现：
- ArrayList 使用动态数组（数组）实现，元素在内存中是连续存储的。
- LinkedList 使用双向链表（链表）实现（JDK1.6 之前为循环链表，JDK1.7 取消了循环），元素在内存中不是连续存储的，每个节点包含了元素本身和指向前一个和后一个节点的引用。
访问和查找效率：
- ArrayList 支持随机访问，可以通过索引直接访问元素，时间复杂度为 O(1)。
- LinkedList 不支持随机访问，访问元素需要从链表头或链表尾开始遍历，时间复杂度为 O(n)。
插入和删除效率：
- ArrayList 在尾部插入元素的效率较高，因为无需移动其他元素。在中间或头部插入元素时，需要移动后续元素，时间复杂度为 O(n)。
- LinkedList 在任意位置插入元素的效率较高，因为只需要修改前后节点的引用，时间复杂度为 O(1)。但在大部分情况下，链表的插入和删除操作也需要 O(n) 的时间，因为需要先定位到指定位置。
空间占用：
- ArrayList 在一开始分配一块连续的内存空间，可能会导致一些空间浪费。但在不断添加元素时，会自动扩展数组的大小。
- LinkedList 每个元素都是一个独立的对象，除了存储元素本身的值，还需要存储前后节点的引用，因此占用的内存会更多。
适用场景：
- 当需要频繁随机访问元素时，ArrayList 更适合，例如通过索引快速获取元素。
- 当需要频繁插入、删除元素时，LinkedList 更适合，例如需要频繁地在中间位置插入元素。

综合考虑，在特定的场景下选择合适的列表实现类很重要。如果只涉及到顺序访问，而没有频繁的插入和删除操作，ArrayList 通常更具优势。如果需要频繁地插入、删除元素，或者需要双向迭代，那么选择 LinkedList 可能更合适。

ArrayList 和 Vector 的区别？

ArrayList 和 Vector 都是 Java 集合框架中的可变大小的动态数组实现，它们有一些相似之处，但也有一些区别：

线程安全性：
- ArrayList 是非线程安全的，多个线程同时修改一个 ArrayList 实例可能会导致并发问题，需要额外的同步措施来确保线程安全性。
- Vector 是线程安全的，它的方法都是同步的，因此可以在多线程环境下使用。但是，这也可能导致一些性能开销。
性能：
- ArrayList 通常比 Vector 性能更好，因为 ArrayList 不进行同步操作，适用于单线程环境或者不需要频繁的增删操作。
- Vector 在进行增删操作时需要进行同步，会有一些性能开销，适用于多线程环境。
增长策略：
- ArrayList 的默认初始容量为 10，当容量不够时会增加 50% 的容量。
- Vector 的默认初始容量也为 10，当容量不够时会增加 100% 的容量。
迭代器支持：
- ArrayList 提供了迭代器（Iterator）支持，用于遍历集合。
- Vector 也提供了迭代器支持，与 ArrayList 类似。
推荐用法：
- 由于现代 Java 程序通常使用更高级的并发控制机制，ArrayList 在绝大多数情况下更常见且更推荐使用。
- Vector 可以在需要线程安全性的特定场景下使用，但是通常更好的做法是使用 java.util.concurrent 包提供的并发集合类。

总之，选择 ArrayList 还是 Vector 取决于你的需求。如果你需要线程安全性，可以考虑使用 Vector，否则在单线程环境或者合适的并发控制下使用 ArrayList。

ArrayList 的自动扩容机制？

ArrayList 是 Java 中常用的动态数组（可变长度数组）实现，它会自动扩容以容纳更多元素。ArrayList 的自动扩容机制如下：

初始容量：ArrayList 在创建时会分配一个初始容量（默认为 10），表示可以存储的元素数量的初始估计值。初始容量是 ArrayList 内部数组的长度。
添加元素：当你向 ArrayList 中添加元素（使用 add 方法）时，它会检查当前元素数量是否达到了容量上限。如果元素数量等于或超过容量上限，就会触发自动扩容。
自动扩容：自动扩容是通过创建一个新的数组来实现的，新数组的长度通常是原数组的 1.5 倍。然后，将原数组中的元素复制到新数组中。这个过程涉及到内存分配和数据复制，因此会有一定的性能开销。
设置新容量：一旦创建了新数组，ArrayList 将更新它的内部容量，以反映新数组的长度。
继续添加元素：现在，你可以继续向 ArrayList 中添加元素，它会继续检查容量，如果需要，再次触发自动扩容。

这个自动扩容机制确保了 ArrayList 可以动态地增加容量，以适应不断增长的元素数量，而不需要手动管理容量。然而，自动扩容也会导致性能开销，因为需要创建新数组并复制数据。

如果你知道 ArrayList 需要存储的元素数量的上限，可以使用构造函数指定初始容量，以减少自动扩容的次数，从而提高性能。例如：

ArrayList<Integer> list = new ArrayList<>(1000); // 指定初始容量为1000

需要注意的是，过度估计初始容量可能会浪费内存，因此在选择初始容量时需要权衡性能和内存消耗。

Java 中的 Map 可以被遍历吗？怎么遍历？

Java 中的 Map 接口可以被遍历。

Map 接口提供了几个方法用于遍历，包括 keySet()、entrySet() 和 values()。

下面是几个例子：

使用 keySet() 遍历 Map 的键：

java

Map<String, Integer> map = new HashMap<>();  
// 添加一些元素到 map  
map.put("one", 1);  
map.put("two", 2);  
map.put("three", 3);  
  
for (String key : map.keySet()) {  
    System.out.println(key);  
}

使用 values() 遍历 Map 的值：

java

Map<String, Integer> map = new HashMap<>();  
// 添加一些元素到 map  
map.put("one", 1);  
map.put("two", 2);  
map.put("three", 3);  
  
for (Integer value : map.values()) {  
    System.out.println(value);  
}

使用 entrySet() 遍历 Map 的键值对：

java

Map<String, Integer> map = new HashMap<>();  
// 添加一些元素到 map  
map.put("one", 1);  
map.put("two", 2);  
map.put("three", 3);  
  
for (Map.Entry<String, Integer> entry : map.entrySet()) {  
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());  
}

注意，以上代码在遍历的过程中，如果尝试修改 Map（例如：添加或删除元素），可能会抛出 ConcurrentModificationException。如果你需要在遍历的过程中修改 Map，可以使用 Iterator，或者创建一个新的 Map 进行操作。

什么是哈希冲突？

哈希冲突是指在哈希表中不同的键映射到了相同的哈希桶（bucket）或位置的情况。哈希表是一种常用的数据结构，用于存储键值对，并通过哈希函数将键映射到特定的位置，以便快速地插入、查找和删除操作。然而，由于哈希函数通常会将不同的键映射到有限的桶或位置上，可能会导致多个键映射到同一个位置，从而产生哈希冲突。哈希冲突可能会对哈希表的性能和正确性产生影响，因为哈希表需要确保不同的键能够正确地映射到不同的位置。如果多个键映射到了同一个位置，那么哈希表需要解决这些冲突，以便能够正确地插入、查找和删除键值对。解决哈希冲突的方法通常有以下几种：

开放寻址法：在发生冲突时，继续寻找下一个可用的位置，直到找到一个空桶。这可能会导致聚集现象，即冲突的键在哈希表中会聚集在一起。
链式哈希法：每个哈希桶都连接一个链表或其他数据结构，所有映射到同一位置的键值对都存储在链表中。这样，不同的键可以共享同一个位置。
再哈希法：使用不同的哈希函数进行再次哈希，以便将冲突的键重新映射到不同的位置。
建立更复杂的数据结构：例如，Java 中的 HashMap 使用了红黑树来管理冲突，当链表长度过长时会转换为红黑树，以提高查找效率。

总之，哈希冲突是在使用哈希表时常见的现象，合理的解决哈希冲突方法可以保证哈希表的性能和正确性。不同的解决方法适用于不同的情况和需求。

HashMap 的长度为什么是 2ⁿ 呢？

HashMap 的长度（容量）为 2ⁿ 的设计是为了提高散列的性能和均匀性。具体来说，采用 2ⁿ 作为长度有以下几个优点：

散列均匀性：使用 2ⁿ 作为长度，可以使得哈希值在桶的位置上分布更加均匀。因为对于任意整数 x，x & (2ⁿ - 1) 的结果等于 x 对 2ⁿ 取模的结果，这种取模操作有助于保持键的均匀分布。
提高性能：使用 2ⁿ 作为长度，可以将取模操作转换为位运算，这比一般的取模操作更快速。这有助于提高插入、查找和删除操作的性能。
减少碰撞：碰撞是指多个键映射到同一个桶的情况。使用 2ⁿ 作为长度可以降低碰撞的概率，因为哈希函数的分布更加均匀。
扩容方便：当 HashMap 需要扩容时，新的容量通常是当前容量的两倍。因此，容量是 2ⁿ 可以更方便地进行扩容操作。

需要注意的是，虽然 2ⁿ 的长度有很多优点，但在某些情况下可能会导致内存浪费。如果实际的键值对数量较小，而容量很大，可能会导致空间的浪费。因此，在使用 HashMap 时，需要根据实际情况选择合适的初始容量和负载因子，以平衡性能和内存消耗。

HashMap 和 HashTable 的区别是什么？

HashMap 和 HashTable 都是 Java 集合框架中用于存储键值对的数据结构，但它们之间存在一些重要的区别：

线程安全性：
- HashMap 是非线程安全的，多个线程可以同时访问和修改一个 HashMap 实例，可能会导致并发问题。
- HashTable 是线程安全的，内部的方法都使用了同步（synchronized）来保证多个线程之间的访问安全。
性能：
- 由于 HashTable 在方法上使用了同步，它的性能通常会比 HashMap 差。在单线程环境下，HashMap 的性能往往更好。
- 在多线程环境下，由于 HashTable 使用了同步，可以保证线程安全，但可能会带来性能下降。
允许空键值：
- HashMap 允许使用一个键为 null 的条目，也允许多个值为 null 的条目。
- HashTable 不允许键或值为 null，在尝试插入 null 键或值时会抛出异常。
初始容量大小和每次扩容量大小的不同：
- 创建时如果不指定容量的初始值，HashMap 的默认容量初始值为 16，之后每次扩容，容量变为原来的 2 倍。HashTable 的默认容量初始值为 11，之后每次扩容，容量变为原来的 2n+1。
- 创建时如果给定容量的初始值，那么 HashTable 会使用给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（由 HashTable 中的 tableSizeFor() 保证）。也就是说 HashMap 总是使用 2 的幂次方作为哈希表的大小。
底层数据结构：JDK1.8 后的 HashMap 在解决哈希冲突时有了很大的变化，当链表长度大于阈值（默认为 8）时，将链表转换成红黑树（将链表长度转换成红黑树前会判断，如果当前数组长度小于 64 会选择先进性数组扩容，而不是转换成红黑树），以减少搜索时间。HashTable 没有这样的机制。
迭代器：
- HashMap 的迭代器是快速失败（fail-fast）的，意味着在迭代过程中如果其他线程对集合进行修改，会抛出 ConcurrentModificationException 异常。
- HashTable 的迭代器是安全的，不会抛出 ConcurrentModificationException 异常。
继承关系：
- HashMap 继承自 AbstractMap 类，并实现了 Map 接口。
- HashTable 继承自 Dictionary 类（已过时），并实现了 Map 接口。
性能调优：
- 由于 HashMap 的非线程安全性，如果需要在多线程环境下使用，可以通过 Collections.synchronizedMap() 方法将 HashMap 转换为线程安全的版本。
- 在性能要求较高的场景中，可以考虑使用 HashMap。在需要线程安全性的场景中，可以使用 ConcurrentHashMap 来替代 HashTable，它是更高效的线程安全的哈希表实现。

总之，HashMap 和 HashTable 在线程安全性、性能和空键值的处理等方面存在差异，开发者应根据具体的需求和场景选择适合的实现类。在现代 Java 中，推荐使用 HashMap 或 ConcurrentHashMap，因为它们在性能和灵活性方面更具优势。

HashMap 中的 hash 方法为什么要右移 16 位异或？

HashMap 中的 hash 方法使用右移 16 位异或（XOR）的原因是为了增加散列码（哈希码）的混合性，减少哈希冲突的概率。在早期版本的 Java 中，hash 方法的实现可能较为简单，只是直接使用对象的 hashCode() 方法。这样的实现在某些情况下可能会导致哈希冲突较为频繁，因为不同对象的 hashCode 可能会有相同的低位。为了改善哈希码的混合性，Java 8 中的 HashMap 实现引入了一个称为“扰动函数”的概念。这个扰动函数会对原始哈希码进行一系列操作，其中包括右移16位异或。具体来说，hash 方法的计算过程如下：

首先，使用对象的 hashCode() 方法获取原始哈希码（32 位整数）。
接着，将原始哈希码右移 16 位，将高位的 16 位与低位的 16 位进行异或操作。这个过程称为“扰动”。

java

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

这个操作有助于将高位的哈希码信息混合到低位，减少哈希冲突的可能性。

最后，将扰动后的哈希码与容量减1（通常是 2 的幂次方减 1）进行与操作，以确保哈希码在合法范围内。

java

int index = hash & (table.length - 1);

这个哈希算法的目标是尽量均匀地分布键的哈希码，以减少桶（bucket）的冲突。它在一定程度上提高了 HashMap 的性能和可靠性。不同版本的 Java 可能有不同的优化和改进，但基本思想是相似的。

HashMap 什么时候扩容？为什么扩容？

HashMap 在存储键值对时会根据一些条件进行扩容。扩容的目的是为了维持 HashMap 的性能和均衡，减少哈希冲突的概率，同时确保哈希表的装载因子保持在一个合理的范围内。以下是触发 HashMap 扩容的主要条件和原因：

装载因子（Load Factor）：HashMap 维护了一个装载因子，默认情况下为 0.75。装载因子表示了哈希表已被占用的比例。当键值对的数量超过了装载因子与当前容量的乘积时，HashMap 就会触发扩容。
例如，如果装载因子是 0.75，当前容量是 16，当键值对数量超过 16 * 0.75 = 12 时，就会触发扩容。
扩容操作：当触发扩容时，HashMap 会创建一个新的哈希表（通常是原来容量的两倍），然后将所有旧表中的键值对重新分布到新表中。这个过程涉及到重新计算哈希码、重新散列、复制键值对等操作。
均衡性和性能：扩容的主要目的是维护哈希表的均衡性，确保桶中的键值对数量相对均匀分布，减少哈希冲突的概率。这有助于保持 HashMap 的性能，因为哈希冲突较少，查找、插入和删除操作的时间复杂度仍然近似为 O(1)。
避免链表过长：如果哈希表中的链表过长（即某个桶中有太多的键值对），查找某个键值对的效率会降低，因为需要遍历链表。通过扩容，可以使链表长度变短，提高性能。

需要注意的是，虽然扩容操作会增加一定的开销，但它是为了维护 HashMap 的性能和均衡而必要的。开发者可以通过适当调整初始容量来减少扩容的次数，从而提高性能。在合理的情况下，HashMap 的扩容操作不会对性能产生明显的负面影响。

HashMap 如何解决 hash 冲突？

HashMap 使用开放地址法（Open Addressing）解决哈希冲突。开放地址法是一种解决哈希冲突的方法，它在哈希表中查找空槽位来存放冲突的键值对，而不是使用链表或其他数据结构来处理冲突。下面是 HashMap 如何使用开放地址法来解决哈希冲突的基本过程：

计算哈希码：当要插入或查找一个键值对时，首先计算该键的哈希码，这个哈希码决定了键值对应存放在哈希表中的哪个位置。
查找槽位：通过哈希码计算出哈希表的索引位置（通常是通过取余数操作得到），如果该位置为空（即没有键值对），则直接将键值对存放在该位置。
处理冲突：如果哈希表的该位置已经被占用，发生了哈希冲突，开放地址法会尝试找到下一个可用的槽位。这通常通过一种探测序列（Probing Sequence）的方式进行，例如，线性探测、二次探测、双重散列等。
- 线性探测：依次查找下一个槽位，直到找到一个空槽位为止。
- 二次探测：根据某种规则查找下一个槽位，通常是跳过固定的步长。
- 双重散列：使用第二个哈希函数计算下一个槽位的位置。
插入或查找：一旦找到了空槽位，就可以插入新的键值对或在查找时找到相应的键值对。
扩容：如果哈希表的装载因子（已占用槽位数与总槽位数之比）超过了某个阈值（通常是 0.75），HashMap 会触发扩容操作，创建一个更大的哈希表，并将已有的键值对重新散列到新的表中，以保持性能。

总的来说，开放地址法通过线性探测、二次探测等方式来解决哈希冲突，它会尽量寻找下一个可用的槽位，直到找到空槽位或遍历整个哈希表。这种方法在维护哈希表的性能和空间效率方面有一定优势，但需要注意的是，探测序列的选择和扩容策略会影响 HashMap 的性能和行为。因此，Java 的 HashMap 实现经过了精心的设计和优化，以提供高性能的哈希表操作。

如果使用 Object 作为 HashMap 的 Key，应该怎么办呢？

使用 Object 作为 HashMap 的键需要注意一些重要的事项，因为 Object 是所有类的基类，这可能会导致一些问题。在使用 Object 作为键时，需要特别注意以下几点：

正确实现 hashCode() 和 equals() 方法：由于 HashMap 使用哈希值来确定键的存储位置，并通过 equals() 方法来比较键是否相等，所以确保 hashCode() 和 equals() 方法正确地实现是非常重要的。如果不正确实现，可能会导致键无法正确地存储或查找。
避免不稳定的哈希值：如果 Object 子类的 hashCode() 方法在不同的运行时调用返回不同的值，会导致键的哈希值不稳定，进而影响到 HashMap 的性能和正确性。确保 hashCode() 方法在对象生命周期内返回的哈希值是稳定的。
避免频繁的键值改变：由于 Object 是可变的，如果使用可变对象作为键，并在放入 HashMap 后频繁地修改键的状态，可能会导致在哈希表中无法正确地找到该键。
性能考虑：HashMap 在存储大量数据时，性能可能会受到 hashCode() 方法的调用次数影响。如果 hashCode() 方法的计算成本较高，可能会影响到整体的性能。

总之，虽然可以使用 Object 作为 HashMap 的键，但需要格外小心，确保正确实现了 hashCode() 和 equals() 方法，以及避免在键的生命周期内频繁地改变键的状态。如果可能的话，最好使用稳定且不可变的键来避免潜在的问题。

为什么 HashMap 中 String、Integer 这样的包装类适合作为 Key ？

String、Integer 等包装类的特性能够保证 Hash 值的不可更改性和计算准确性，能够有效减少 Hash 冲突的概率。

都是 final 类型，即不可变性，保证 key 的不可变性，不会存在获取 hash 值不同的情况。
内部已经重写了 equals()、hashCode() 等方法，遵守了 HashMap 内部的规范，不容易出现 hash 计算错误的情况。

ConcurrentHashMap 线程安全的具体实现方式是什么样的？

ConcurrentHashMap 在多线程环境下实现线程安全的方式是通过采用分段锁（Segment-Based Locking）的机制。具体来说，ConcurrentHashMap 将内部的数据结构分为一系列的段（segments），每个段都类似于一个小的哈希表，具有自己的锁。每个段内的操作在锁的保护下进行，不同的段之间可以并发地进行操作，从而实现了更高的并发性能。

以下是 ConcurrentHashMap 线程安全实现的关键点：

分段锁：ConcurrentHashMap 内部的数据结构被分为多个段，每个段都有自己的锁。不同的段之间可以并发地访问，从而提高了并发性能。
操作锁定：当进行操作时，只有涉及的段会被锁定，而不是整个 ConcurrentHashMap。这样可以在多线程环境下保证一部分的线程可以并发执行。
扩容：ConcurrentHashMap 在扩容时，只需要扩容其中的某个段，而不需要整个集合进行重新分配。这减少了扩容操作对整个集合的影响。
操作的选择：ConcurrentHashMap 提供了多种操作的方式，包括不加锁的读操作和需要加锁的写操作。这样可以根据实际需求选择合适的操作方式，平衡性能和线程安全性。

总之，ConcurrentHashMap 通过分段锁的方式将并发操作限制在不同的段上，从而实现了高效的多线程并发性能。这使得在高并发环境下，不同线程可以同时访问和修改不同的段，提高了整体的并发性能。

HashMap 和 ConcurrentHashMap 的区别？

HashMap 和 ConcurrentHashMap 都是 Java 集合框架中的实现类，用于存储键值对。它们在多线程环境下的性能和线程安全性方面有一些重要的区别：

线程安全性：

HashMap 是非线程安全的，多个线程同时修改一个 HashMap 实例可能会导致并发问题，需要额外的同步措施来确保线程安全性。
ConcurrentHashMap 是线程安全的，它使用了多个锁（分段锁）来支持并发访问，从而实现了更高的并发性能。不同的段（分段）在不同的锁上，可以并发地访问不同的段。

性能：

在低并发的情况下，HashMap 的性能可能更好，因为它不需要额外的同步开销。
在高并发的情况下，ConcurrentHashMap 的性能通常优于 HashMap，因为它支持更高的并发度，不同的段可以被不同的线程同时访问，减少了竞争。

迭代器：

HashMap 的迭代器是快速失败（fail-fast）的，即如果在迭代过程中有其他线程修改了集合，会抛出 ConcurrentModificationException 异常。
ConcurrentHashMap 的迭代器是弱一致（weakly consistent）的，不会抛出 ConcurrentModificationException 异常，但在迭代时可能会反映部分或全部修改。

允许空值：

HashMap 允许使用 null 作为键和值。
ConcurrentHashMap 不允许使用 null 作为键或值，如果插入 null 值会抛出 NullPointerException。

扩容：

HashMap 在需要扩容时会重新分配内部数组，可能会导致性能抖动。
ConcurrentHashMap 使用分段锁，每个段在需要扩容时会进行局部扩容，不会对整个集合进行大规模的重新分配。

总结：

HashMap 适用于单线程环境或者在合适的并发控制下使用，性能较好。
ConcurrentHashMap 适用于多线程环境，可以提供更高的并发性能，但不支持 null 值，迭代器是弱一致的。

HashTable 和 ConcurrentHashMap 的区别？

HashTable 和 ConcurrentHashMap 都是用于存储键值对的实现类，但它们在多线程环境下的性能和线程安全性方面有一些重要的区别：

线程安全性：

HashTable 是线程安全的，所有的方法都是同步的，可以在多线程环境下使用。但是，这也可能导致一些性能开销。
ConcurrentHashMap 也是线程安全的，它使用了多个锁（分段锁）来支持并发访问，从而实现了更高的并发性能。不同的段（分段）在不同的锁上，可以并发地访问不同的段。

性能：

在低并发的情况下，HashTable 的性能可能较好，因为它不需要额外的同步开销。
在高并发的情况下，ConcurrentHashMap 的性能通常优于 HashTable，因为它支持更高的并发度，不同的段可以被不同的线程同时访问，减少了竞争。

扩容：

HashTable 在需要扩容时会重新分配内部数组，可能会导致性能抖动。
ConcurrentHashMap 使用分段锁，每个段在需要扩容时会进行局部扩容，不会对整个集合进行大规模的重新分配。

迭代器：

HashTable 的迭代器是安全的，不会抛出 ConcurrentModificationException 异常，但在迭代时可能会反映部分或全部修改。
ConcurrentHashMap 的迭代器是弱一致（weakly consistent）的，不会抛出 ConcurrentModificationException 异常，但在迭代时可能会反映部分或全部修改。

允许空值：

HashTable 不允许使用 null 作为键或值，如果插入 null 值会抛出 NullPointerException。
ConcurrentHashMap 不允许使用 null 作为键或值，如果插入 null 值会抛出 NullPointerException。

总结：

HashTable 适用于多线程环境，但在性能方面可能受到同步开销的影响。
ConcurrentHashMap 适用于多线程环境，可以提供更高的并发性能，但不支持 null 值，迭代器是弱一致的。在性能要求较高且需要支持多线程的场景下，通常推荐使用 ConcurrentHashMap。

如何优雅地删除 HashMap 中的元素？

在 Java 中，可以通过以下几种方式来优雅地删除 HashMap 中的元素：

使用增强 for 循环删除：

通过 HashMap 的 entrySet() 方法获取键值对集合，然后使用增强 for 循环遍历集合，判断条件后删除元素。

需要注意的是，增强 for 循环底层使用的是迭代器 Iterator，而 HashMap 的错误机制是 fail-fast 原则，因此遍历删除元素会抛出 ConcurrentModificationException 异常。可以使用 CopyOnWriteArraySet 来解决这个问题。

fail-fast 原则：当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。例如：当一个线程在遍历集合，而另一个线程修改了集合的结构，那么就会抛出 ConcurrentModificationException 异常。
目的是为了将错误或异常尽早暴露出来，以便尽快修复，避免潜在的问题在后续的代码中蔓延，提高系统的稳定性和可靠性。

java

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>() {{
            put("name1", "Tom");
            put("name2", "Jerry");
            put("name3", "Alice");
        }};

        CopyOnWriteArraySet<Map.Entry<String, String>> entries = new CopyOnWriteArraySet<>(map.entrySet());
        for (Map.Entry<String, String> entry : entries) {
            if ("Tom".equals(entry.getValue())) {
                map.remove(entry.getKey());
            }
        }
        System.out.println(map);
    }

}

使用 forEach 方法删除：

Java 8 引入了 forEach 方法，可以使用 lambda 表达式来遍历集合，然后删除元素。

java

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>() {{
            put("name1", "Tom");
            put("name2", "Jerry");
            put("name3", "Alice");
        }};

        map.forEach((key, value) -> {
            if ("Tom".equals(value)) {
                map.remove(key);
            }
        });
        System.out.println(map);
    }
}

使用迭代器删除：

通过迭代器遍历 HashMap，然后使用迭代器的 remove() 方法删除元素。

java

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>() {{
            put("name1", "Tom");
            put("name2", "Jerry");
            put("name3", "Alice");
        }};

        Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, String> entry = iterator.next();
            if ("Tom".equals(entry.getValue())) {
                iterator.remove();
            }
        }
        System.out.println(map);
    }
}

使用 removeIf 方法：

Java 8 引入了 removeIf 方法，可以使用 lambda 表达式来删除元素。

java

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>() {{
            put("name1", "Tom");
            put("name2", "Jerry");
            put("name3", "Alice");
        }};

        map.entrySet().removeIf(entry -> "Tom".equals(entry.getValue()));
        System.out.println(map);
    }
}

使用 Stream API 删除：

Java 8 引入了 Stream API，可以使用 filter 方法来过滤元素，然后使用 collect 方法将结果收集到新的 Map 中。

java

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>() {{
            put("name1", "Tom");
            put("name2", "Jerry");
            put("name3", "Alice");
        }};

        Map<String, String> result = map.entrySet().stream()
                .filter(entry -> !"Tom".equals(entry.getValue()))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
        System.out.println(result);
    }
}

比较 HashSet、LinkedSet 和 TreeSet 三者的异同？

HashSet、LinkedHashSet 和 TreeSet 都是 Java 集合框架中的实现类，用于存储集合元素，但它们在底层数据结构、性能和行为方面有一些异同点。

HashSet：

使用哈希表（散列桶）作为底层数据结构，使用哈希函数来确定元素在集合中的位置。
元素是无序的，不保证插入顺序。
允许使用 null 元素。
添加、删除和查找操作的平均时间复杂度为 O(1)，但具体性能取决于哈希函数的质量和哈希冲突的处理。
适用于需要高效查找和去重的场景。

LinkedHashSet：

在 HashSet 的基础上，使用双向链表来维护元素的插入顺序，因此保留了插入顺序。
元素的遍历顺序与插入顺序相同。
允许使用 null 元素。
添加、删除和查找操作的平均时间复杂度为 O(1)，与 HashSet 类似，但增加了维护插入顺序的开销。
适用于需要保留插入顺序的场景。

TreeSet：

使用红黑树（一种平衡二叉搜索树）作为底层数据结构，保持元素有序。
元素按照自然顺序或指定的比较器顺序进行排序。
不允许使用 null 元素。
添加、删除和查找操作的平均时间复杂度为 O(log n)，其中 n 是集合的大小。
适用于需要有序集合的场景，支持范围查询等操作。

总结：

HashSet 适用于需要高效的查找和去重的场景，不关心元素顺序。
LinkedHashSet 在 HashSet 基础上保留了插入顺序，适用于需要保留元素插入顺序的场景。
TreeSet 适用于需要有序集合的场景，提供了排序和范围查询等功能。

选择使用哪种集合取决于你的具体需求，例如是否需要元素有序，是否需要高效的插入和查找，以及是否需要支持空元素等。

HashSet 如何检查重复？

HashSet 通过使用哈希表（散列桶）的数据结构来检查重复元素。当元素被添加到 HashSet 中时，它会经过以下步骤来检查是否重复：

计算哈希值：首先，HashSet 会调用元素的 hashCode() 方法来计算元素的哈希值。哈希值是一个整数，用于确定元素在哈希表中的位置。
定位桶：根据哈希值，HashSet 计算出元素应该存储在哪个桶（bucket）中。
比较元素：如果该桶中已经存在元素，HashSet 将调用元素的 equals() 方法来比较新元素和已存在的元素是否相等。如果 equals() 方法返回 true，则表示元素重复，不会被添加到 HashSet 中。

如果两个元素的哈希值相等，但 equals() 方法返回 false，则 HashSet 不会认为它们相等，因为哈希值相等只是一个快速的筛选步骤，而实际的比较是通过 equals() 方法来进行的。需要注意的是，为了保证 HashSet 正确地工作，添加到 HashSet 中的元素必须正确实现 hashCode() 和 equals() 方法。这两个方法在判断元素是否重复时起到关键作用。如果不正确实现，可能会导致重复元素被错误地添加到 HashSet 中，或者在查找元素时出现错误的结果。

TreeMap 和 TreeSet 在排序时如何比较元素？

TreeMap 和 TreeSet 都是基于红黑树（一种平衡二叉搜索树）实现的，用于存储有序的元素。它们在排序时都是通过比较元素的方式来确定元素的位置。

TreeMap：

在 TreeMap 中，元素是以键值对（key-value pair）的形式存储的，其中键（key）用于比较和排序元素。
当插入或查找元素时，TreeMap 会根据元素的键值来进行比较，根据比较结果将元素插入到合适的位置。
默认情况下，TreeMap 使用键的自然顺序进行比较，如果要自定义比较规则，可以通过构造函数传入一个实现了 Comparator 接口的比较器。

TreeSet：

在 TreeSet 中，只存储元素而不存储键值对，元素本身就用于比较和排序。
当插入或查找元素时，TreeSet 会根据元素的值来进行比较，根据比较结果将元素插入到合适的位置。
默认情况下，TreeSet 使用元素的自然顺序进行比较，如果要自定义比较规则，可以通过构造函数传入一个实现了 Comparator 接口的比较器。

需要注意的是，元素必须实现 Comparable 接口或者在构造 TreeMap 和 TreeSet 时提供一个比较器（Comparator），以便在排序时进行比较。否则，在插入元素时可能会抛出 ClassCastException。自然顺序和自定义比较器的选择取决于元素的类型和排序要求。

Sorted Set 和 List 异同点？

SortedSet 和 List 都是 Java 集合框架中的接口，用于存储一组元素，但它们在一些方面有明显的异同点。

异同点：

有序性：
- SortedSet：是一个有序集合，它根据元素的自然顺序或指定的比较器来维护元素的顺序。元素在集合中按照升序（自然顺序）或根据比较器的规则进行排序。
- List：也是有序集合，元素在列表中的顺序由元素插入的顺序决定。
允许重复元素：
- SortedSet：不允许存储重复元素，每个元素在集合中是唯一的。
- List：允许存储重复元素，即可以在列表中多次包含相同的元素。
访问元素：
- SortedSet：通常不提供按索引访问元素的方法，而是提供了根据元素值的比较来获取元素的方法。
- List：支持按索引访问元素，可以使用 get(int index) 方法来获取列表中特定位置的元素。

主要异点：

排序：
- SortedSet：元素是按照顺序排列的，无论是自然顺序还是通过比较器定义的顺序。
- List：虽然 List 也维护元素的顺序，但元素的顺序是由插入顺序决定的，没有默认的排序规则。
重复元素：
- SortedSet：不允许存储重复元素，如果尝试插入相同的元素会被忽略。
- List：允许存储重复元素，可以在列表中多次包含相同的元素。
接口继承：
- SortedSet：继承自 Set 接口，是 Set 的子接口。
- List：继承自 Collection 接口，是 Collection 的子接口。

选择使用 SortedSet 还是 List 取决于你的需求。如果需要按照某种顺序对元素进行管理，并且不需要存储重复元素，那么可以考虑使用 SortedSet。如果需要按照插入顺序存储元素，或者允许存储重复元素，那么 List 可能更合适。

试比较 Queue 和 Deque 的区别？

Queue（队列）和 Deque（双端队列）都是 Java 集合框架中用于存储一组元素的接口，它们在元素添加和移除的方式上有一些区别，以及对队列和双端队列操作的支持程度不同。

Queue（队列）：

Queue 是一个接口，它表示一个典型的先进先出（FIFO）的队列。
Queue 接口扩展了 Collection 接口，它包括了添加、移除和检查元素的方法，如 add()、remove()、peek() 等。
常用的 Queue 实现类有 LinkedList、ArrayDeque 等。
适用于典型的队列场景，如任务调度、消息传递等。

Deque（双端队列）：

Deque 是一个接口，它表示一个允许在两端添加和移除元素的队列，支持先进先出和后进先出等操作。
Deque 接口扩展了 Queue 接口，并增加了一些方法，如 offerFirst()、offerLast()、pollFirst()、pollLast() 等。
常用的 Deque 实现类有 LinkedList、ArrayDeque 等。
适用于需要在队列两端进行添加和移除元素的场景，如双向队列、栈等。

总结：

Queue 主要用于典型的先进先出队列场景，支持从一端添加元素，从另一端移除元素。
Deque 是在 Queue 基础上扩展而来，支持在队列两端添加和移除元素，可以用作双端队列、栈等数据结构。
ArrayDeque 是 Deque 接口的常见实现，可以高效地支持队列和栈操作。

无序性和不可重复性的含义是什么？

在集合（Collection）的概念中，"无序性"（Unordered）和"不可重复性"（Distinct）是两个重要的特性，它们分别表示以下含义：

无序性 (Unordered)：

无序性表示集合中的元素没有明确的顺序关系，即元素的存储和访问顺序是不确定的。
在无序的集合中，元素的排列顺序可能会随着操作的不同而变化，不同的实现可能会以不同的方式组织元素。

不可重复性 (Distinct)：

不可重复性表示集合中的元素不能重复出现，每个元素只能在集合中出现一次。
在不可重复的集合中，尝试插入重复元素会被忽略，集合会确保每个元素只存在一次。

这些特性在不同的集合类型中有不同的体现：

Set 接口是不可重复且无序的集合，它保证了元素不会重复出现，但不保证元素的存储顺序。HashSet 是 Set 接口的一个实现，它使用哈希表来实现不可重复性和无序性。
List 接口是有序且可重复的集合，它允许元素按照特定的顺序排列，并可以包含重复的元素。ArrayList 和 LinkedList 是 List 接口的两个常见实现。

需要根据具体的需求选择合适的集合类型，以满足无序性和不可重复性的要求。

集合框架篇 ​

Java 中常用的集合框架有哪些？它们之间的区别是什么？ ​

为什么要使用集合？ ​

如何选用集合？ ​

Collections 工具类中的 sort() 方法如何比较元素？ ​

Collection 和 Collections 有什么区别？ ​

什么是 CopyOnWriteArrayList？ ​

Arrays.asList() ​

ArrayList.subList() ​

红黑树 ​

有了二叉搜索树，为什么还需要平衡二叉树？ ​

有了平衡二叉树，为什么还需要红黑树？ ​

有数组了为什么还要 ArrayList 呢？ ​

Array 和 ArrayList 有什么区别？ ​

ArrayList 和 LinkedList 之间的区别是什么？ ​

ArrayList 和 Vector 的区别？ ​

ArrayList 的自动扩容机制？ ​

Java 中的 Map 可以被遍历吗？怎么遍历？ ​

什么是哈希冲突？ ​

HashMap 的长度为什么是 2n 呢？ ​

HashMap 和 HashTable 的区别是什么？ ​

HashMap 中的 hash 方法为什么要右移 16 位异或？ ​

HashMap 什么时候扩容？为什么扩容？ ​

HashMap 如何解决 hash 冲突？ ​

如果使用 Object 作为 HashMap 的 Key，应该怎么办呢？ ​

为什么 HashMap 中 String、Integer 这样的包装类适合作为 Key ？ ​

ConcurrentHashMap 线程安全的具体实现方式是什么样的？ ​

HashMap 和 ConcurrentHashMap 的区别？ ​

HashTable 和 ConcurrentHashMap 的区别？ ​

如何优雅地删除 HashMap 中的元素？ ​

比较 HashSet、LinkedSet 和 TreeSet 三者的异同？ ​

HashSet 如何检查重复？ ​

TreeMap 和 TreeSet 在排序时如何比较元素？ ​

Sorted Set 和 List 异同点？ ​

试比较 Queue 和 Deque 的区别？ ​

无序性和不可重复性的含义是什么？ ​

集合框架篇

Java 中常用的集合框架有哪些？它们之间的区别是什么？

为什么要使用集合？

如何选用集合？

Collections 工具类中的 sort() 方法如何比较元素？

Collection 和 Collections 有什么区别？

什么是 CopyOnWriteArrayList？

Arrays.asList()

ArrayList.subList()

红黑树

有了二叉搜索树，为什么还需要平衡二叉树？

有了平衡二叉树，为什么还需要红黑树？

有数组了为什么还要 ArrayList 呢？

Array 和 ArrayList 有什么区别？

ArrayList 和 LinkedList 之间的区别是什么？

ArrayList 和 Vector 的区别？

ArrayList 的自动扩容机制？

Java 中的 Map 可以被遍历吗？怎么遍历？

什么是哈希冲突？

HashMap 的长度为什么是 2ⁿ 呢？

HashMap 和 HashTable 的区别是什么？

HashMap 中的 hash 方法为什么要右移 16 位异或？

HashMap 什么时候扩容？为什么扩容？

HashMap 如何解决 hash 冲突？

如果使用 Object 作为 HashMap 的 Key，应该怎么办呢？

为什么 HashMap 中 String、Integer 这样的包装类适合作为 Key ？

ConcurrentHashMap 线程安全的具体实现方式是什么样的？

HashMap 和 ConcurrentHashMap 的区别？

HashTable 和 ConcurrentHashMap 的区别？

如何优雅地删除 HashMap 中的元素？

比较 HashSet、LinkedSet 和 TreeSet 三者的异同？

HashSet 如何检查重复？

TreeMap 和 TreeSet 在排序时如何比较元素？

Sorted Set 和 List 异同点？

试比较 Queue 和 Deque 的区别？

无序性和不可重复性的含义是什么？