集合概览

约 2187 字大约 7 分钟

2025-01-15

1.概览

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

	List	Set	Map
存储对象	有序，不唯一	无序，唯一	键值对
读写效率	查找元素效率高，插入删除效率低	查找效率低，删除和插入效率高

2.Collection接口

Collection 接口是层次结构中的根接口。构成 Collection 的单位称为元素。

Collection 接口通常不能直接使用，但该接口提供了添加元素、删除元素、管理数据的方法。由于 List 接口与 Set 接口都继承了 Collection 接口，因此这些方法对 List 集合与 Set 集合是通用的。

常用方法如下

方法	描述
add(E e)	将指定的对象添加到该集合中
remove(Object o)	将指定的对象从该集合中移除
isEmpty()	返回 boolean 值，用于判断当前集合是否为空
iterator()	返回在此 Collection 的元素上进行迭代的迭代器。用于遍历集合中的对象
size()	返回 int 型值，获取该集合中元素的个数

3.List接口

	ArrayList	LinkedList
存储对象	只能存储引用类型数据的对象，对于基本类型数据，需要使用其对应的包装类	LinkedList 可以存储任意类型的对象，包括基本数据类型和引用数据类型
底层数据结构	底层使用 Object[] 存储	双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）
线程安全	不安全	不安全
使用场景	频繁的随机查找操作	频繁的修改删除操作

4.Set接口

Set 接口常用的实现类有 HashSet 、LinkedHashSet、TreeSet

	HashSet	LinkedHashSet	TreeSet
存储对象	存储唯一，不重复元素，根据元素的hashCode()和equals()判断	同 HashSet	存储唯一，不重复元素，通过实现 Comparable 接口判断元素是否重复
底层数据结构	基于HashMap实现	基于 LinkedHashMap 实现	红黑树
null值问题	允许存储一个 null 元素	允许存储一个 null 元素	不允许存储 null 元素
线程安全	不安全	不安全	不安全

5.Map接口

Map接口常见的实现类有HashMap、LinkedHashMap、HashTable、TreeMap、ConcurrentHashMap

	HashMap	LinkedHashMap	HashTable	TreeMap	ConcurrentHashMap
存储对象	键值对（key-value）	键值对（key-value）	键值对（key-value）	键值对（key-value）	键值对（key-value）
底层数据结构	数组+链表+红黑树	数组+双向链表	数组	红黑树	数组+分段锁
null值	一个键为 null 的键值对	一个键为 null 的键值对	不允许	不允许	一个键为 null 的键值对
线程安全	不安全	不安全	安全	不安全	安全

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

7.2 ArrayList时间复杂度

插入：

头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)
尾部插入：
1. 当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；
2. 当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。
指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)

删除：

头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。
尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。
指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

7.3 LinkedList时间复杂度

头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)

7.4 HashMap和HashTable的异同

相同：两者均实现了Map接口，用于存储key-value键值对的数据
不同：
1. 底层数据结构不同：HashMap底层为（数组+链表或者数组+红黑树）、HashTable底层为哈希表（哈希数组）+链表，使用寻址开放法解决哈希冲突
2. null值问题不同：HashMap支持null键（一个）和null值（多个）；HashTable不支持null键和null值
3. 线程安全问题不同：HashMap不安全，HashTable安全
4. 初始化机制和扩容机制不同：
  1. HashMap的初始化容量为16，若容量超出阈值（数组容量16*负载因子0.75=12）的话，则扩容为原来的2倍
  2. HashTable的初始化容量为11，之后每次扩容，容量变为原来的2n+1
  3. HashMap若指定容量初始值，HashMap会将其扩充为最近的2的幂次方大小（HashMap中的tableSizeFor()方法保证）
  4. HashTable若指定容量初始值，直接使用该指定大小

7.5 HashMap和HashSet的异同

ps：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

	`HashMap`	`HashSet`
1. 实现的接口及存储的对象不同	实现了 `Map` 接口，存储键值对	实现 `Set` 接口，仅存储对象
2.添加方法不同	调用 `put()`向 map 中添加元素	调用 `add()`方法向 `Set` 中添加元素
3.比较对象是否相同方法不同	`HashMap` 使用键（Key）计算 `hashcode`	`HashSet` 使用成员对象来计算 `hashcode` 值，对于两个对象来说 `hashcode` 可能相同，所以`equals()`方法用来判断对象的相等性

7.6 HashMap和TreeMap的异同

相同：两者都实现Map接口，存储key-value，线程不安全
不同：
- 底层数据结构不同：TreeMap底层是一棵自平衡的多路查找树（红黑树）
- null值问题不同：TreeMap不能存储null键的数据，因为需要排序
- 排序问题不同：TreeMap强大的功能点在于可以排序

TreeMap自定义排序比较器

public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }


    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

输出：TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了

person1
person4
person2
person3

我们是通过传入匿名内部类的方式实现的，你可以将代码替换成 Lambda 表达式实现的方式：

TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
  int num = person1.getAge() - person2.getAge();
  return Integer.compare(num, 0);
});

版权所有

本文链接：/Java/Java%E9%9B%86%E5%90%88/

许可证：署名 4.0 国际 (CC-BY-4.0)