Java面试宝典-Java集合02

‌TreeMap和TreeSet在排序时主要通过实现Comparable接口或使用Comparator对象进行比较。‌

在TreeMap中，元素的排序是通过实现元素的Comparable接口或者使用Comparator对象来实现的。如果元素实现了Comparable接口，则使用元素的compareTo()方法进行比较；如果没有实现Comparable接口，则需要提供一个Comparator对象来进行比较。比较的结果决定了元素在TreeMap中的排序顺序‌。

在TreeSet中，元素的排序同样是通过实现元素的Comparable接口或者使用Comparator对象来实现的。如果元素实现了Comparable接口，则使用元素的compareTo()方法进行比较；如果没有实现Comparable接口，则需要提供一个Comparator对象来进行比较。比较的结果决定了元素在TreeSet中的排序顺序‌。

Collections工具类中的sort()方法也通过实现元素的Comparable接口或者使用Comparator对象来进行排序。如果元素实现了Comparable接口，则使用元素的compareTo()方法进行比较；如果没有实现Comparable接口，则需要提供一个Comparator对象来进行比较。比较的结果决定了元素在排序后的顺序‌.

ArrayList和LinkedList都是Java集合框架中的一部分，它们实现了List接口，用于存储元素的动态数组。然而，它们在内部实现、效率、以及 操作特点上有一些显著的区别。

 （1）内部实现 ArrayList是基于数组实现的，其内部维护了一个动态数组来存储元素。数组是一块连续的内存空间，因此ArrayList在随机访问元素时非常高 效，时间复杂度为O(1)。然而，当添加或删除元素时，如果数组已满或需要移动元素，可能需要进行扩容或数据移动操作，这可能会降低效 率。 LinkedList则是基于链表实现的，其内部元素是通过节点（Node）连接在一起的。每个节点包含实际的数据以及指向下一个和上一个节点的 指针。因此，LinkedList在内存中的存储不是连续的。这种结构使得LinkedList在添加或删除元素时效率较高，因为只需要修改相关节点的指 针，而不需要移动大量数据。然而，随机访问元素时，LinkedList需要从头或尾开始遍历，效率较低。

（2）效率 当需要频繁地进行随机访问元素（如通过索引获取元素）时，ArrayList通常比LinkedList更高效，因为ArrayList可以直接通过索引定位到元 素。 而在添加或删除元素时，LinkedList通常比ArrayList更高效，因为LinkedList只需要修改相关节点的指针，而不需要移动其他元素。

（3）控件开销 ArrayList的主要控件开销在于需要在其内部数组中预留一定的空间以存储元素。当元素数量超出当前容量时，ArrayList会自动进行扩容，以 适应更多的元素。这种扩容操作可能会导致一定的性能开销。 LinkedList的主要控件开销在于需要存储每个节点的信息以及节点之间的指针信息。这增加了额外的内存开销，但使得在链表中间添加或删 除元素的操作变得高效。

（4）线程安全 ArrayList和LinkedList都不是线程安全的。如果在多线程环境下使用，需要手动进行同步处理或者使用线程安全的集合类，如 Collections.synchronizedList()或CopyOnWriteArrayList。 综上所述，ArrayList和LinkedList各有其优势和适用场景。在选择使用哪种集合时，应根据具体的应用需求和性能要求来做出决策。如果需 要频繁地进行随机访问元素，ArrayList可能更合适；而如果需要频繁地进行添加或删除元素的操作，LinkedList可能更合适。

ArrayList和Vector都是基于数组实现的List集合类，它们提供了动态数组的功能，可以根据需要自动调整大小以存储对象。

Vector的公共方法大多带有synchronized关键字，确保了方法是同步的，因此Vector是线程安全的。而ArrayList没有这样的同步措施，所以 它是线程不安全的。

 由于Vector的方法是同步的，因此在多线程环境下会涉及锁的获取和释放，这可能导致性能上的开销。相比之下，ArrayList由于没有额外的 同步开销，通常运行得更快。 当底层数组容量不足以容纳新元素时，ArrayList会在原有基础上扩展约0.5倍的容量，而Vector则扩展一倍的容量。这意味着在频繁进行大量 添加操作的情况下，ArrayList可能会有更高的效率。

（1）队列先进先出，栈先进后出。

（2）遍历数据速度不同。

 栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前 的一致性； 队列则不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像 数据结构，速度要快的多。

Queue以及Deque都是继承于Collection，Deque是Queue的子接口。

Queue是FIFO的单向队列，Deque是双向队列。

Queue有一个直接子类PriorityQueue，而Deque中直接子类有两个：LinkedList以及ArrayDeque。 PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的。 ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。

PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。 ArrayDeque通常作为栈或队列使用，但是栈的效率不如LinkedList高。 LinkedList通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。

（1）offer()和add()区别： 增加新项时，如果队列满了，add会抛出异常，offer返回false。

（2）poll()和remove()区别： poll()和remove()都是从队列中删除第一个元素，remove抛出异常，poll返回null。

（3）peek()和element（）区别： peek()和element（）用于查询队列头部元素，为空时element抛出异常，peek返回null。

优先队列中的元素可以按照任意的顺序插入，但会按照有序的顺序获取。

优先队列常用结构是PriorityQueue和ArrayDeque。

也就是在调用remove时，总是删除队列中最小的元素。

优先队列使用堆作为存储数据结构，堆是一个自组织的二叉树，其添加和删除操作会让最小的元素移动到根，而不必花费时间对元素进行排 序。 优先队列的主要用途是调度。每个任务有一个优先级，任务以随机顺序插入到队列中，每当启动一个新的任务时，将从队列中删除优先级最 高的任务。

双端队列是一种特殊的队列，它的两端都可以进行插入和删除操作。这种队列的实现方式是使用两个指针，一个指针指向队列的头部，另一 个指针指向队列的尾部。当需要插入或删除元素时，只需要移动指针即可。

双端队列的主要优点是可以在队列的两端进行操作，因此具有较高的效率。此外，双端队列还具有一些其他的优点，例如可以在队列的两端 进行查询操作，因此具有较高的查询效率。

双端队列的缺点是插入和删除操作的时间复杂度都是O(1)，因此在处理大量数据时可能会导致性能问题。此外，双端队列的空间复杂度也是 O(1)，因此在插入和删除元素时需要使用额外的空间。

 CopyOnWriteArrayList是Java并发包java.util.concurrent下提供的一个线程安全的ArrayList实现，它是写时复制（Copy-On-Write）的容 器。

 CopyOnWriteArrayList的核心特性在于，当修改容器（例如添加、删除元素）时，不是直接修改当前容器，而是先复制当前容器的副本，然 后在副本上进行修改。修改完成后，再将原容器的引用指向新的容器。这种策略使得读操作可以完全不用加锁，因此读取性能极高。同时， 写入操作也不会阻塞读取操作，只有写入和写入之间需要进行同步等待。

 由于CopyOnWriteArrayList的这些特性，它特别适用于以下场景：

1. 读多写少的场景：当对数据的读操作次数远远高于写操作时，使用CopyOnWriteArrayList可以有效提升系统性能。因为每次修改操作 都会创建底层数组的副本，从而避免了读取操作受到写入操作的干扰。

2. 数据更新要求不频繁的场景：由于每次添加、修改或删除列表中的元素时，CopyOnWriteArrayList都需要重新创建一个新的底层数 组，因此在实现上会消耗更多的内存空间。因此，它更适用于数据更新不频繁的场景。

3. 互斥访问数据不方便的场景：在多线程环境下，如果需要对一个ArrayList实例进行访问，通常需要加锁以保证数据一致性。但在某些场 景下，加锁可能会给程序带来额外的复杂度和延迟。此时，可以考虑使用CopyOnWriteArrayList。

4. 需要保证数据一致性的场景：由于每个线程都在自己的副本上进行操作，因此不存在读取过程中数据被其他线程修改的问题，从而保证 了数据的一致性。

（1）内存占用问题 由于CopyOnWriteArrayList的写时复制机制，当进行写操作时，内存中会同时驻扎两个对象的内存，旧的对象和新写入的对象。在复制时只 复制容器里的引用，在写时才会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存。

（2）数据一致性问题 CopyOnWriteArrayList只能保证数据的最终一致性，不能保证数据的实时一致性。因为复制和操作元素需要一些时间，所以会有延迟。如果 希望写入的数据马上能读到，要求数据强一致性的话，建议不要使用CopyOnWriteArrayList。

（3）线程安全 CopyOnWriteArrayList是写同步，读非同步的。多个线程对CopyOnWriteArrayList进行写操作是线程安全的，但是在读操作时是非线程安 全的。如果在for循环中使用下标的方式去读取数据，可能会报错ArrayIndexOutOfBoundsException。

（4）不支持add()、set()、remove()方法 CopyOnWriteArrayList的迭代器实现了ListIterator接口，但是add()、set()、remove()方法都直接抛出了UnsupportedOperationException 异常，所以应该避免使用迭代器的这几个方法。

从数组中间删除一个元素开销很大，其原因是向数组中插入元素时，此元素之后的所有元素都要向后端移动，删除时也是，数组中位于被删 除元素之后的所有元素都要向数组的前端移动。

此时，在Java中，可以通过链表解决这个问题。 数组是在连续的存储位置上存放对象引用，而链表则是将每个对象存放在单独的链接link中。每个链接还存放着序列中下一个链接的引用。 在Java中，所有的链表都是双向链接，即每个链接还存储前驱的引用。

散列表，也叫哈希表，是根据关键码值(Key value)直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以此来加快查找的速度。这个映射函数就是散列函数，存放记录的数组就是散列表。

在Java中，散列表通常由HashMap和HashSet实现。HashMap存储键值对，HashSet存储独立的元素。散列表的实现原理基于散列函数和处理冲突的方法。

Java中HashMap的实现原理：

1. 使用一个Node数组作为存储数据的数据结构。
2. 通过key的hashCode()方法计算出哈希值，然后通过某种散列算法转换成数组下标。
3. 如果出现不同key计算出相同数组下标的情况，则采用链表的方式将Node链接在一起。
4. 如果链表长度超过阈值（链表转红黑树的阈值），则将链表转换为红黑树。
5. 在插入和查询时，重复上述步骤。

   
   public class HashMap<K, V> {
       // 存储数据的数组
       Node<K, V>[] table;
       // 阈值，数组大小超过这个值时会进行扩容
       int threshold;
       // 加载因子
       float loadFactor;
   
       public V put(K key, V value) {
           // 计算key的hash值
           int hash = hash(key.hashCode());
           // 转换为数组下标
           int index = indexFor(hash, table.length);
           // 遍历链表，如果已存在相同的key，则替换value
           for (Node<K, V> e = table[index]; e != null; e = e.next) {
               if (e.key.equals(key)) {
                   V oldValue = e.value;
                   e.value = value;
                   return oldValue;
               }
           }
           // 如果key不存在，则添加到链表的头部
           table[index] = new Node<>(key, value, table[index]);
           // 检查是否需要扩容
           if (size++ >= threshold)
               resize(2 * table.length);
           return null;
       }
   
       public V get(K key) {
           // 计算key的hash值
           int hash = hash(key.hashCode());
           // 转换为数组下标
           int index = indexFor(hash, table.length);
           // 遍历链表，查找key对应的value
           for (Node<K, V> e = table[index]; e != null; e = e.next) {
               if (e.key.equals(key))
                   return e.value;
           }
           return null;
       }
   
       // 散列算法
       static int hash(int h) {
           h ^= (h >>> 20) ^ (h >>> 12);
           return h ^ (h >>> 7) ^ (h >>> 4);
       }
   
       // 计算数组下标
       static int indexFor(int h, int length) {
           return h & (length - 1);
       }
   
       // 扩容方法
       void resize(int newCapacity) {
           // ...
       }
   
       // 内部类Node，表示链表节点
       static class Node<K, V> {
           final K key;
           V value;
           Node<K, V> next;
   
           Node(K key, V value, Node<K, V> next) {
               this.key = key;
               this.value = value;
               this.next = next;
           }
       }
   }

 Java中的映射视图是指一种将Map转换为Set或Collection的机制，以便于更方便地操作Map中的元素。

1. keySet()：返回包含Map中所有键的Set；

2. values()：返回包含Map中所有值的Collection；

3. entrySet()：返回包含Map中所有键值对的Set；

通过这些映射视图，可以方便地遍历Map中的元素、检查某个键是否存在、删除指定键等操作。 在使用时需要注意，映射视图只是一个视图，即对原Map进行的修改会反映到相应的映射视图中，反之亦然，因此要谨慎使用。 另外，由于映射视图是基于Map实现的，因此对映射视图的修改也可能影响到原Map中的元素。

以下是一个简单的例子，展示了如何使用HashMap来添加和获取键值对：

import java.util.HashMap;

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

        // 添加键值对
        map.put("key1", 1);
        map.put("key2", 2);
        map.put("key3", 3);

        // 获取并打印键为"key2"的值
        Integer value = map.get("key2");
        System.out.println("key2的值为: " + value);

        // 删除键为"key2"的键值对
        map.remove("key2");

        // 检查键"key2"是否存在
        if(map.containsKey("key2")) {
            System.out.println("key2存在");
        } else {
            System.out.println("key2不存在");
        }
    }
}

Java中的弱散列映射指的是一种特殊的Map实现，即WeakHashMap类。和普通HashMap不同WeakHashMap中的键是弱引用，即当某个 键不再被外部对象引用时，该键及其对应的值会被自动清除掉，以避免内存泄漏问题。

通过使用WeakHashMap，可以将某些对象与其他应用逻辑分离开来，使得它们的生命周期仅由其它对象的引用决定，当没有任何对象引用 时，这些对象会被自动清除，从而释放系统资源。在Java中，常用WeakHashMap来实现缓存、事件通知等场景。需要注意的是，由于弱引 用的存在，WeakHashMap无法保证元素的顺序，因此在遍历时应该谨慎。

WeakHashMap是一种基于红黑树实现的有序映射，它的常用方法包括：

 1. put(K key, V value)：将一个键值对添加到弱散列映射中；

 2. get(K key)：返回一个键值对，如果键不存在则返回null；

3. remove(K key)：从弱散列映射中删除一个键值对；

4. containsKey(K key)：检查一个键是否存在于弱散列映射中；

5. size()：返回弱散列映射中键值对的数量； 这些方法都是基于红黑树实现的，因此它们的时间复杂度都是O(log n)，其中n是Map中元素的数量。

import java.util.WeakHashMap;
import java.util.Map;

    public class WeakHashMapExample {
        public static void main(String[] args) {
            Map<String, String> weakHashMap = new WeakHashMap<>();

            // 添加键值对
            weakHashMap.put("key1", "value1");
            weakHashMap.put("key2", "value2");

            // 检查WeakHashMap的大小
            System.out.println("WeakHashMap Size: " + weakHashMap.size());

            // 做一些操作来触发垃圾收集器
            System.gc(); // 显式调用垃圾收集器

            // 再次检查WeakHashMap的大小
            System.out.println("WeakHashMap Size after GC: " + weakHashMap.size());
        }
    }

Java中的链接散列映射指的是HashMap和LinkedHashMap这两个键值对映射集合实现类。它们都是基于哈希表实现的，链式散列是解决哈 希冲突的一种方法。

具体来说，HashMap和LinkedHashMap内部使用哈希表来存储键值对，当多个键经过哈希函数计算后产生同一个索引位置时，就会产生哈 希冲突。为了解决哈希冲突，HashMap和LinkedHashMap使用链式散列技术，即在哈希表每个索引位置上维护一个链表，将所有哈希值相 同的键值对存放在同一个链表中，从而实现快速查找和添加元素。

HashMap和LinkedHashMap的区别在于，前者是无序键值对集合，而后者是有序键值对集合。具体来说，LinkedHashMap内部使用一个双 向链表来维护键值对的插入顺序，因此遍历LinkedHashMap时可以按照键值对插入的顺序进行。需要注意的是，在使用HashMap和 LinkedHashMap时，应根据具体的业务需求和性能要求选择合适的实现类。

Java中的链接散列集指的是HashSet和LinkedHashSet这两个集合实现类。它们都是基于哈希表（Hash Table）实现的，链式散列是解决哈希冲突的一种方法。

HashSet和LinkedHashSet内部使用哈希表来存储元素，当多个元素经过哈希函数计算后产生同一个索引位置时，就会产生哈希冲突。为了解决哈希冲突，HashSet和LinkedHashSet使用链式散列技术，即在哈希表每个索引位置上维护一个链表，将所有哈希值相同的元素存放在同一个链表中，从而实现快速查找和添加元素。

HashSet和LinkedHashSet的区别在于，前者是无序集合，而后者是有序集合。具体来说，LinkedHashSet内部使用一个双向链表来维护元素的插入顺序，因此遍历LinkedHashSet时可以按照元素插入的顺序进行。需要注意的是，在使用HashSet和LinkedHashSet时，应根据具

体的业务需求和性能要求选择合适的实现类。

LinkedHashMap的常用方法包括：

1. put(K key, V value)：将一个键值对添加到链接散列集中；

2. get(K key)：返回一个键值对，如果键不存在则返回null；

3. remove(K key)：从链接散列集中删除一个键值对；

4. containsKey(K key)：检查一个键是否存在于链接散列集中；

5. size()：返回链接散列集中键值对的数量；

这些方法都是基于链表实现的，因此它们的时间复杂度都是O(1)，其中n是Map中元素的数量。

Java中的枚举集指的是基于枚举类型实现的集合类，即EnumSet。

它是一个专门用于存储枚举类型值的高效集合实现类，可以实现基本操作（如添加、删除、查找等）和集合运算（如交、并、补等），同时还提供了高性能的迭代器，可以按照枚举类型常量在内存中出现的顺序进行遍历。

EnumSet使用位向量（bit vector）实现，即将每个枚举类型常量映射到一个二进制位上，从而快速进行集合运算。由于EnumSet只能存储枚举类型值，因此它具有类型安全性、性能高效、空间利用率高等优点。

EnumSet是一个抽象类，不能直接实例化，但可以通过EnumSet的静态工厂方法创建实例，例如EnumSet.of()、EnumSet.range()等。此外，EnumSet也支持各种集合转换操作，可以与其他集合实现类进行互相转换。

Java中的枚举映射指的是基于枚举类型实现的键值对集合类，即EnumMap。它是一个专门用于存储枚举类型作为键的键值对集合实现类，

可以实现基本操作（如添加、删除、查找等）和集合运算（如交、并、补等），同时还提供了高性能的迭代器，可以按照枚举类型常量在内存中出现的顺序进行遍历。

EnumMap使用数组实现，数组的长度等于枚举类型常量数目，每个位置上存储的是该枚举类型常量所对应的值。由于EnumMap只能存储枚举类型作为键，因此它具有类型安全性、性能高效、空间利用率高等优点。

需要注意的是，EnumMap也是一个抽象类，不能直接实例化，但可以通过EnumMap的构造方法或静态工厂方法创建实例，例如new EnumMap<>(MyEnum.class)、EnumMap.copyOf()等。此外，EnumMap也支持各种集合转换操作，可以与其他集合实现类进行互相转换。

Comparator与Comparable在Java中都是用于比较对象大小的接口。

‌Comparator与Comparable的主要区别在于它们的使用场景和实现方式。‌

‌Comparable‌：Comparable是一个接口，定义在java.lang包中。实现Comparable接口的类必须实现compareTo方法，该方法用于比较当前对象与另一个对象的大小。Comparable被称为内比较器，因为它被封装在实现它的类内部。实现了Comparable接口的类可以直接使用Collections.sort()或Arrays.sort()等方法进行排序。compareTo方法的返回值是int，有三种情况：负整数表示当前对象小于比较对象，零表示相等，正整数表示当前对象大于比较对象。

‌Comparator‌：Comparator也是一个接口，位于java.util包中。与Comparable不同，Comparator可以作为外比较器使用，即它不需要修改原类，而是通过实现Comparator接口来定义比较规则。Comparator接口定义了一个compare方法，用于比较两个对象的大小。Comparator的返回值也是int，与Comparable的返回值相同，表示小于、等于或大于比较对象‌。

‌使用场景的区别‌：

‌Comparable‌：适用于那些自然排序的场景，即对象本身具有明确的排序规则。例如，String类和Integer类都实现了Comparable接口，因此它们可以直接使用排序方法进行排序。

‌Comparator‌：适用于那些没有自然排序规则或者需要自定义排序规则的场景。通过实现Comparator接口，可以为任何类提供自定义的比较规则，而不需要修改类本身。这在处理复杂对象或需要多种排序方式时非常有用‌。

为了方便的处理集合中的元素,Java中出现了一个对象,该对象提供了一些方法专门处理集合中的元素.例如删除和获取集合中的元素.该对象就叫做迭代器(Iterator)。

Iterator 接口源码中的方法：

1. java.lang.Iterable 接口被 java.util.Collection 接口继承，java.util.Collection 接口的 iterator() 方法返回一个 Iterator 对象

2. next() 方法获得集合中的下一个元素

3. hasNext() 检查集合中是否还有元素

4. remove() 方法将迭代器新返回的元素删除

（1）ListIterator 继承 Iterator

（2）ListIterator 比 Iterator多方法

add(E e) 将指定的元素插入列表，插入位置为迭代器当前位置之前

set(E e) 迭代器返回的最后一个元素替换参数e

hasPrevious() 迭代器当前位置，反向遍历集合是否含有元素

previous() 迭代器当前位置，反向遍历集合，下一个元素

previousIndex() 迭代器当前位置，反向遍历集合，返回下一个元素的下标

nextIndex() 迭代器当前位置，返回下一个元素的下标

（3）使用范围不同，Iterator可以迭代所有集合；ListIterator 只能用于List及其子类

ListIterator 有 add 方法，可以向 List 中添加对象；Iterator 不能

ListIterator 有 hasPrevious() 和 previous() 方法，可以实现逆向遍历；Iterator不可以

ListIterator 有 nextIndex() 和previousIndex() 方法，可定位当前索引的位置；Iterator不可以

ListIterator 有 set()方法，可以实现对 List 的修改；Iterator 仅能遍历，不能修改。

快速失败（fail-fast）策略的核心在于一旦发现数据结构在迭代过程中被修改，系统会立即停止迭代并通过抛出ConcurrentModificationException异常来报告错误。这样做的目的是尽早地发现错误，防止错误的扩散，从而保证软件的稳定性和可靠性。例如，在使用ArrayList或HashMap等集合类进行迭代时，如果尝试在迭代过程中修改集合内容，就会触发这种快速失败的行为。

安全失败（fail-safe）策略则相对宽容，它允许在迭代过程中对数据结构进行修改，而不会立即抛出异常。这种策略通常通过使用额外的措施，如迭代器复制、锁或其他同步机制，来确保即使在多线程环境下也能安全地进行操作。这样可以减少因并发修改导致的问题，提高程序的容错性。

原文地址：https://blog.csdn.net/qq_38105536/article/details/142823239

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！