计算机基础

Appearance

集合概述 ​

也叫容器，顶层是两大接口：一般都允许 null 值，但是无意义，线程安全的很多不支持

  • Collection ：存放单一元素

    • List：存储的元素是有序的、可重复的
      • 底层由 Object[] 数组实现，默认长度是 10
      • 扩容时每次增加为原来的 1.5 倍
      • ArrayList：线程不安全，支持 null 值
        • CopyOnWriteArrayList：写时复制（不是原地修改），读时不做任何动作
          • 每次写入一个元素，扩容 1，时间复杂度 O(n)，需要全量复制
          • 读取直接读，弱一致性（可能读到旧值），类似于数据库主从
          • 删除会将后续元素往前移动，也是复制操作
          • 判定元素是否存在时间复杂度O(n)
      • Vector：线程安全（弃用）
    • Set：存储的元素不可重复的
      • 底层由 Map 实现
      • HashSet、LinkedHashSet、TreeSet
    • Queue：按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的
      • PriorityQueue： Object[] 数组实现小顶堆
      • DelayQueue：优先队列
      • ArrayDeque：双向数组

  • Map：存放键值对，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

    • HashMap：
      • 线程不安全，允许有 null 作为 key（一般不建议，没意义，可以用空 object 代替，且）
      • 容量一定是 2 的幂次方，因为需要对哈希值进行取余，而取余如果除数是 2 的倍数等价于与除数减一的 & 操作，性能更好
      • 底层使用链表和红黑树
        • 1.8 之前使用数组和链表：hashcode 取余后放在数组对应位置，如果已经有了，并且equals不相同，那么通过拉链法，放在后面
        • 1.8 之后，当链表大于阈值（默认 8） 之后，将链表转换为红黑树（一个哈希桶一个）
          • 如果当前数组小于 64，会先进行数组扩容
      • LinkedHashMap：继承自 HashMap，增加了一条双向链表，维护元素插入顺序，迭代顺序就是插入顺序一致，可以用来实现 LRU
      • ConcurrentHashMap：并发安全的 HashMap，一个哈希桶一把锁
        • 不允许 null 作为 value 和 key，
          • value：通过 get 获取的时候，当返回 null 时，无法确定值没有在集合中，还是值本身就是 null（二义性），如果这个时候修改，可能导致问题
          • 可以通过 putIfAbsent 这种原子方法保证插入的原子操作，如果先判定存在再确定是否插入，可能被打断
    • HashTable：（已淘汰），数组+链表组成
      • 线程安全，不允许 null 作为 key，会报错
      • 全局使用同一把锁保证线程安全，性能比较低，ConcurrentHashMap使用一个哈希桶一把锁，性能更好
    • TreeMap：
      • 相较于前面两个支持元素根据键排序，并支持集合内元素搜索的能力，基于红黑树数据结构实现
    • 以上保证 key 无序都是通过 hashcode和equals()方法联合实现，如果 hashcode 相同，会再调用 equals() 比较，确保不会丢失数据，都相同判定为相同数据

使用建议

  • 集合判空用 isEmpty() 方法，而不是 size()==0 的方式，可读性更好，且时间复杂度一定是 O(1)
  • 集合去重用 Set 而不是List 的 contains() ，contains复杂度O(n)
  • 集合转数组用toArray(T[] array)
  • 数组转集合用List.of()，但是不能修改集合的元素数量，可以手动实现工具类或者 Stream 流

其他集合使用 ​

  • Queue：单端队列，FIFO
    • 常用方法：
      • add/offer
      • remove/poll
      • element/peek
    • 常用实现类
    • 扩展类：
      • BlockingQueue：阻塞队列
        • 当队列满了放入会阻塞
        • 当队列空了取出会阻塞
        • 通过可重入锁确保单位时间内只有一个线程可以操作阻塞队列，通过Condition 实现线程间的等待和唤醒操作
      • DelayQueue：延迟队列
        • 按照到期时间升序排列任务
        • 采用小顶堆保证元素排序，通过可重入锁确保单位时间内只有一个线程可以操作延迟队列，线程安全，通过Condition 实现线程间的等待和唤醒操作
  • Deque：双端队列
    • 常用方法：
      • 基本就是在 Queue 的基础上加上 First/Last
    • 常用实现类：ArrayDeque 和 LinkedList ，总体来说前者性能更好
  • Stack：
    • 一般使用 Deque，通过 push 和 pop 实现

集合遍历 ​

foreach 语法底层依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法，因此循环中直接 remove/add 会抛出并发修改异常（fail-fast 机制），需要使用Iterator 方式/Collection#removeIf()，如果并发，需要对Iterator 对象加锁。

fail-fast 机制：多个线程对 fail-fast 集合进行修改的时候，可能会抛出ConcurrentModificationException。 即使是单线程下也有可能会出现这种情况。

除了上面介绍的直接使用 Iterator 进行遍历操作之外，你还可以：

  • 使用普通的 for 循环
  • 使用 fail-safe 的集合类。java.util包下面的所有的集合类都是 fail-fast 的，而java.util.concurrent包下面的所有的类都是 fail-safe 的。
  • ……

Collections 工具类（不重要） ​

Collections 工具类常用方法:

  • 排序
  • 查找,替换操作

排序操作 ​

java
void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

查找,替换操作 ​

java
int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

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()); // 直接比较两个方法

正在精进

Copyright © 2025 菜鸟