计算机基础

Appearance

集合概述 ​

Java 集合概览 ​

Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。

Java 集合框架如下图所示：

Java 集合框架概览

说说 List, Set, Queue, Map 四者的区别？ ​

  • List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
  • Set(注重独一无二的性质): 存储的元素不可重复的。
  • Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
  • Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，"x" 代表 key，"y" 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

集合框架底层数据结构总结 ​

先来看一下 Collection 接口下面的集合。

List ​

  • ArrayList：Object[] 数组。

    • 无参构造的 ArrayList 对象时，默认长度是 10 。

    • 如果初始容量小于10，那么第一次添加元素默认增加到10

    • 之后扩容每次都会变为原来的 1.5 倍左右

  • Vector：Object[] 数组。

  • LinkedList：双向链表。详细可以查看：LinkedList 源码分析。

Set ​

  • HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
  • LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
  • TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)。

Queue ​

再来看看 Map 接口下面的集合。

Map ​

  • HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。详细可以查看：HashMap 源码分析。
  • LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：LinkedHashMap 源码分析
  • Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
  • TreeMap：红黑树（自平衡的排序二叉树）。

如何选用集合? ​

我们主要根据集合的特点来选择合适的集合。比如：

  • 我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。
  • 我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

List ​

ArrayList 和 Vector 的区别?（了解即可） ​

  • ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全 。
  • Vector 是 List 的古老实现类，底层使用Object[] 存储，线程安全。

Vector 和 Stack 的区别?（了解即可） ​

  • Vector 和 Stack 两者都是线程安全的，都是使用 synchronized 关键字进行同步处理。
  • Stack 继承自 Vector，是一个后进先出的栈，而 Vector 是一个列表。

随着 Java 并发编程的发展，Vector 和 Stack 已经被淘汰，推荐使用并发集合类（例如 ConcurrentHashMap、CopyOnWriteArrayList 等）或者手动实现线程安全的方法来提供安全的多线程操作支持。

ArrayList 可以添加 null 值吗？ ​

ArrayList 中可以存储任何类型的对象，包括 null 值。不过，不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。

RandomAccess 接口 ​

java
public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。 标识实现这个接口的类具有随机访问功能。

在 binarySearch() 方法中，它要判断传入的 list 是否 RandomAccess 的实例，如果是，调用indexedBinarySearch()方法，如果不是，那么调用iteratorBinarySearch()方法

java
    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

Set ​

Comparable 和 Comparator 的区别 ​

Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口，它们在实现类对象之间比较大小、排序等方面发挥了重要作用：

  • Comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
  • Comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序
  • 想要实现排序，需要重写上面两个方法其中之一，其中Comparable是创建类时直接implement即可
java
// Comparable , 用 this 和新对象进行比较
@Override  
public int compareTo(Student other) {  
    return Integer.compare(this.age, other.age); // 按照年龄从小到大排序  
} 

// Comparator , 用 this 和新对象进行比较 
(s1, s2) -> Integer.compare(s1.getAge(), s2.getAge()); // 直接比较两个方法

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

  • 无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
  • 不可重复性是指添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。

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

  • HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
  • HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
  • 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

Queue ​

Queue 与 Deque 的区别 ​

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Queue 接口抛出异常返回特殊值
插入队尾add(E e)offer(E e)
删除队首remove()poll()
查询队首元素element()peek()

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

Deque 接口抛出异常返回特殊值
插入队首addFirst(E e)offerFirst(E e)
插入队尾addLast(E e)offerLast(E e)
删除队首removeFirst()pollFirst()
删除队尾removeLast()pollLast()
查询队首元素getFirst()peekFirst()
查询队尾元素getLast()peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

ArrayDeque 与 LinkedList 的区别 ​

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

  • ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。

  • ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。

  • ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。

  • ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

什么是 BlockingQueue？ ​

BlockingQueue （阻塞队列）是一个接口，继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。

java
public interface BlockingQueue<E> extends Queue<E> {
  // ...
}

BlockingQueue 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。

BlockingQueue

BlockingQueue 的实现类有哪些？ ​

BlockingQueue 的实现类

Java 中常用的阻塞队列实现类有以下几种：

  1. ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。
  2. LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。和ArrayBlockingQueue不同的是， 它仅支持非公平的锁访问机制。
  3. PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。
  4. SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。
  5. DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。
  6. ……

日常开发中，这些队列使用的其实都不多，了解即可。

ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？ ​

ArrayBlockingQueue 和 LinkedBlockingQueue 是 Java 并发包中常用的两种阻塞队列实现，它们都是线程安全的。不过，不过它们之间也存在下面这些区别：

  • 底层实现：ArrayBlockingQueue 基于数组实现，而 LinkedBlockingQueue 基于链表实现。
  • 是否有界：ArrayBlockingQueue 是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue 创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。
  • 锁是否分离： ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock，这样可以防止生产者和消费者线程之间的锁争夺。
  • 内存占用：ArrayBlockingQueue 需要提前分配数组内存，而 LinkedBlockingQueue 则是动态分配链表节点内存。这意味着，ArrayBlockingQueue 在创建时就会占用一定的内存空间，且往往申请的内存比实际所用的内存更大，而LinkedBlockingQueue 则是根据元素的增加而逐渐占用内存空间。

正在精进

Copyright © 2025 菜鸟