Collection

下图中实线表示继承，虚线表示实现：

image-20240207214220622

常用方法：

  1. add：添加元素；
  2. remove：删除元素；
  3. contains：查找元素是否存在；
  4. size：获取元素个数；
  5. isEmpty：判断是否为空；
  6. clear：清空；
  7. addAll：添加多个元素；
  8. containsAll：多个元素是否都存在；
  9. removeAll：删除多个元素。

因为存储的是对象（Object），如果添加元素为基本数据类型会自动装箱。

迭代器

迭代器（iterator）用于遍历 Collection 中的元素。所有实现了 Collection 接口的集合类都有一个 iterator() 方法，用以返回一个迭代器对象。

主要方法：

  1. hasNext：没有指针下移操作，只是判断是否存在下一个元素；
  2. next：指针下移并返回指针所指向的元素；
  3. remove：删除指针指向的元素。
1
2
3
4
5
6
7
8
9
10
Iterator<Integer> iterator = coll.iterator();
while (iterator.hasNext()){
    Integer ele = iterator.next();
    System.out.println(ele);
    if (ele == 3){
        iterator.remove();
    }
}
// 此时指针指向集合末尾元素，如需再次遍历，需进行重置
iterator = coll.iterator();

在调用 next 方法之前必须先调用 hasNext 进行检测。否则如果下一条记录无效，直接调用 next 将抛出 NoSuchElementException 异常。

增强 for 循环，底层使用迭代器实现，写法简便，可以代替 iterator 进行遍历。用于遍历集合或数组。

1
2
3
for (Integer ele : coll) {
    System.out.println(ele);
}

List

List 中元素有序且可重复，支持索引，可根据索引获取元素。

除继承而来的方法外，List 还新增了一些根据索引操作集合元素的方法，常用方法：

  1. void add(int index, Object ele)：在 index 位置插入 ele 元素；
  2. boolean addAll(int index, Collection eles)：从 index 位置开始将 eles 中的所有元素添加进去；
  3. Object get(int index)：获取指定 index 位置的元素；
  4. int indexOf(Object obj)：返回 obj 在集合中首次出现的位置；
  5. int lastIndexOf(Object obj)：返回 obj 在集合中末次出现的位置；
  6. Object remove(int index)：移除 index 位置的元素，井返回此元素；
  7. Object set(int index, Object ele)：设置 index 位置的元素为 ele；
  8. List subList(int fromlndex, int tolndex)：返回从 fromlndex 到 tolndex 位置的子集合。

ArrayList

  1. 使用数组作为数据结构，底层维护了一个 Object[] 类型的数组 elementData；
  2. 当创建 ArrayList 对象时，如果使用无参构造器，则初始 elementData 容量为 0，第 1 次添加时，则扩容 elementData 为 10，如需再次扩容，则扩容为 1.5 倍；若使用有参构造器，初始大小为参数指定大小，之后直接按 1.5 倍进行扩容；
  3. ArrayList 在当前容量不足以容纳新元素时才进行扩容操作，扩容时会创建一个新的数组，并将原有数组中的元素复制到新数组中；
  4. 非线程安全。

Vector

  1. 使用数组作为数据结构，底层同样维护了一个 Object[] 类型的数组 elementData；

  2. 扩容机制与 ArrayList 基本一致，当使用无参构造器创建时，默认初始大小为 10。如果元素数量超过了当前容量，则创建一个为当前容量 2 倍的新数组，然后将原有元素复制到新的数组中；

  3. 线程安全，通过使用 synchronized 修饰方法来实现。但是由于锁住了整个 Vector 对象，效率不高；

    image-20240207201744360

LinkedList

  1. 使用双向链表作为数据结构，它存储了指向头节点和尾节点的引用；

    image-20240207205303291

  2. 不需要扩容机制，添加元素时修改节点之间的引用关系即可；

  3. 非线程安全。

Set

Set 中元素无序且不能包含重复元素，不支持索引。

除了继承自 Collection 接口的方法外，Set 接口没有额外的新增方法。

HashSet

非线程安全。

HashSet 的底层数据结构是哈希表，它实际上通过 HashMap 来实现。HashSet 内部维护了一个 HashMap 实例，HashSet 中的元素被存储在 HashMap 的键中，而 HashMap 中的值则都被设置为同一个类常量，仅仅作为占位存在。

当向 HashSet 添加元素时，会先得到这个元素的 hashCode，再根据 hash规则 将元素存储在指定的数组位置。如果造成 hash冲突，会调用元素的 equals 方法与冲突元素（链表或树中的元素）进行比较，如果某次比较返回 true，则放弃添加，否则将元素添加到链表或红黑树中。

规范：如果两个对象通过 equals 方法比较是相等的，则它们的 hashCode 也应该是相等的。

扩容机制：第一次添加元素时，table 数组扩容到 16，临界值为 16*0.75=12。如果数组单元占用个数超过临界值，会创建一个新数组，其容量为原来的两倍 16*2=32，新临界值为 32*0.75=24，以此类推。如果总元素个数 >=64 并且存在长度达到 8 的链表，则进行树化，将长度达到阈值的链表转换成红黑树。

1
2
3
4
5
6
7
HashSet<Object> hashSet = new HashSet<>();
hashSet.add("scarf"); // 添加成功
hashSet.add(new String("scarf")); // 添加失败
hashSet.add(new String("scarf")); // 添加失败
hashSet.add(new User("scarf")); // 添加成功
hashSet.add(new User("scarf")); // 添加成功
System.out.println(hashSet);
1
[com.scarf.User@29453f44, scarf, com.scarf.User@5cad8086]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 原因是 String 重写了 hashcode 以及 equals 方法
User user1 = new User("scarf");
User user2 = new User("scarf");
System.out.println("user1哈希码: " + user1.hashCode());
System.out.println("user2哈希码: " + user2.hashCode());
System.out.println(user1.equals(user2));
String s = "scarf";
String s1 = new String("scarf");
String s2 = new String("scarf");
System.out.println("s 哈希码: " + s.hashCode());
System.out.println("s1哈希码: " + s1.hashCode());
System.out.println("s2哈希码: " + s2.hashCode());
System.out.println(s.equals(s1));
System.out.println(s1.equals(s2));
1
2
3
4
5
6
7
8
user1哈希码: 1588970020
user2哈希码: 1407343478
false
s 哈希码: 109251077
s1哈希码: 109251077
s2哈希码: 109251077
true
true

LinkedHashSet

LinkedHashSet 底层通过 LinkedHashMap 实现，通过在 HashSet 的基础上新增双向链表用于维护元素的顺序。能够保留元素插入的顺序，因此它是有序的集合。LinkedHashSet 的扩容机制与 HashSet 一致，同时也是非线程安全的。

image-20240208155250694

数组单元是可以存储元素的，为了方便起见将数组中的元素提到外面。

TreeSet

  1. 使用红黑树作为数据结构，底层使用 TreeMap 来实现，元素存储在 key 中，value 同样使用类常量占位；
  2. 非线程安全；
  3. 特点是能够按照指定的比较器（Comparator）进行排序，并且支持快速的集合操作，比如范围查询、查找最小/最大元素等。
1
2
3
4
5
TreeSet<String> treeSet = new TreeSet<>(String::compareTo); // 按字母表顺序排序
treeSet.add("sc");
treeSet.add("ar");
treeSet.add("f");
System.out.println(treeSet); // [ar, f, sc]
1
2
3
4
5
6
// 按长度进行排序
TreeSet<String> treeSet = new TreeSet<>(Comparator.comparingInt(String::length)); 
treeSet.add("sc");
treeSet.add("ar"); // 加入失败，因为和 sc 长度一致，底层认为是同一个元素
treeSet.add("f");
System.out.println(treeSet); // [f, sc]

Map

下图中实线表示继承，虚线表示实现：

image-20240207131807749

Map 中 key 不能重复，如果添加相同的 key，会覆盖原来的值。

常用方法：

  1. put：添加元素；
  2. remove：根据键删除元素；
  3. get：根据键获取值；
  4. size：获取元素个数；
  5. isEmpty：判断元素个数是否为空；
  6. clear：清除元素；
  7. containsKey：查找键是否存在；
  8. keySet：获取所有的键；
  9. entrySet：获取所有键值对；
  10. values：获取所有值。

HashMap

  1. 底层数据结构采用数组+链表+红黑树，使用 key 进行 hash 和 equals 判断，与 value 无关；
  2. 扩容机制在 HashSet 中已阐述；
  3. 非线程安全。

对于 LinkedHashMap，它同样在 HashMap 的基础上新增了双向链表来使元素有序。

HashTable

  1. 键和值都不能为 null，否则将抛出 NullPointerException 空指针异常；
  2. 使用数组+链表的方式来处理哈希冲突，链表并不会被转成红黑树；
  3. 默认数组初始大小为 11，装载因子还是 0.75，扩容时会创建一个新数组，其容量为原来的 2 倍 + 1；
  4. 线程安全，通过使用 synchronized 修饰方法来实现。

Properties

主要用于操作配置文件。

  1. 继承自 HashTable，使用键值对的形式保存数据，键和值同样都不能为 null；
  2. 数据结构以及扩容机制和 HashTable 一致；
  3. 使用了 synchronized 修饰了 setProperty() 和 load() 等方法。如果只是调用这些同步的方法，那么在多线程环境下是安全的。

TreeMap

相关已在 TreeSet 中阐述。

1
2
3
4
5
6
// 按字母表排序 key
TreeMap<String, String> treeMap = new TreeMap<>(String::compareTo);
treeMap.put("sc","1");
treeMap.put("ar","2");
treeMap.put("f","3");
System.out.println(treeMap); // {ar=2, f=3, sc=1}
1
2
3
4
5
6
// 按 key 长度排序
TreeMap<String, String> treeMap = new TreeMap<>(Comparator.comparingInt(String::length));
treeMap.put("sc","1");
treeMap.put("ar","2"); // 添加失败
treeMap.put("f","3");
System.out.println(treeMap); // {f=3, sc=2}

Collections

Collections 是一个可以操作 Set、List 和 Map 的工具类。

常用方法：

  1. reverse(List)：反转 List 中元素的顺序；
  2. shuffle(List)：对 List 元素进行随机排序；
  3. sort(List)：根据元素的自然顺序对 List 进行排序；
  4. sort(List, Comparator)：根据指定的 Comparator 排序规则对 List 进行排序；
  5. swap(List, int, int)：交换 List 集合中两个指定位置的元素；
  6. max(Collection)：根据元素的自然顺序，返回集合中的最大元素；
  7. max(Collection, Comparator)：根据 Comparator 指定的顺序，返回集合中的最大元素；
  8. min(Collection)、min(Collection, Comparator)；
  9. frequency(Collection, Object)：返回集合中指定元素的出现次数；
  10. copy(List dest, List src)：将 src 中的内容复制到 dest 中；
  11. replaceAll(List list, Object oldVal, Object newVal)：使用 newVal 替换 List 中的所有 oldVal。