概述

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

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

Collection 接口

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

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

常用方法如下

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

List 接口

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

Set 接口

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

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

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 的键值对
线程安全	不安全	不安全	安全	不安全	安全

Collections 工具类

Java 提供了一个操作 List、Set 和 Map 等集合的工具类：Collections，该工具类提供了大量方法对集合进行排序、查询和修改等操作，还提供了将集合对象置为不可变、对集合对象实现同步控制等方法。

这个类不需要创建对象，内部提供的都是静态方法。

思考小结

如何选择集合

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

ArrayList 时间复杂度

插入：

1. 头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)

2. 尾部插入：

   1. 当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；
   2. 当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。

3. 指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)

删除：

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

LinkedList 时间复杂度

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

HashMap 和 HashTable 的异同

1. 相同：两者均实现了 Map 接口，用于存储 key-value 键值对的数据
2. 不同：
   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 若指定容量初始值，直接使用该指定大小

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()方法用来判断对象的相等性

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);
});

版权所有

版权归属：haipeng-lin

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