• jdk 1.2 开始出现，相关的接口和类都在 java.util 包中，保存的是对象的引用
• jdk 1.2 以前“古老”的集合类：Vector、Hashtable（都是同步的）

Collection 和 Iterator 接口

Collection 接口操作集合元素的方法

• Iterable 的子接口

• 增加

  • boolean add(Object o)：向集合里添加一个元素，如果集合对象被添加操作改变了，则返回 true
  • boolean addAll(Collection c)：把集合 c 里的所有元素添加到指定集合里，如果集合对象被添加操作改变了，则返回 true
• 删除
  • boolean remove(Object o)：删除集合中第一个符合条件的指定元素 o，返回 true
  • boolean removeAll(Collecrion c)：从该集合中删除集合 c 里包含的所有元素，如果删除了一个或一个以上的元素，该方法将返回 true
  • boolean retainAll(Collection c)：使该集合中仅保留集合 c 里包含的元素（求两个集合的交集），如果该操作改变了调用该方法的集合，则该方法返回 true
  • void clear()：清除集合里的所有元素，将集合长度变为 0
• 查询
  • boolean contains(Object o)：判断集合里是否包含指定元素 o
  • boolean containsAll(Collection c)：判断集合里是否包含集合 c 里的所有元素
  • boolean isEmpty()：判断集合是否为空，当集合长度为 0 时返回 true，否则返回 false
  • int size()：返回集合里元素的个数
• 其它操作
  • Iterator<E> iterator()：获取一个 Iterator 对象（迭代器）
  • Object[] toArray()：把集合转换成一个数组，所有的集合元素变成对应的数组元素（转化 Object 数组时，没有必要使用 toArray[new Object[0]]，可以直接使用 toArray()）
  • <T> T[] toArray(T[] a)：返回一个包含此集合中所有元素的数组；返回数组的运行时类型是指定数组的类型。如果指定的数组 a 能容纳该集合，则 a 将在其中返回；否则，将分配一个具有指定数组的运行时类型和此集合大小的新数组（集合转化为类型 T 数组时，尽量传入空数组 T[0]）
• 默认方法
  • Stream<E> stream()
  • Stream<E> parallelStream()
  • boolean removeIf(Predicate<E> filter)：删除满足给定谓词的此集合的所有元素
  • void forEach(Consumer<? super T> action)：对 Iterable 的每个元素执行给定的操作

使用 Iterator 遍历集合元素

• Iterator 接口用于遍历（即迭代访问）Collection 集合中的元素
• 通过把集合元素的值传给了迭代变量
• 在创建 Iterator 迭代器之后，除非通过迭代器自身的 remove() 方法对 Collection 集合里的元素进行修改，否则在对 Collection 集合进行修改后再使用迭代器进行迭代访问时，迭代器会抛出 ConcurrentModificationException

• 实例方法

  • boolean hasNext()：如果集合里仍有元素可以迭代，则返回 true
  • Object next()：返回集合里的下一个元素
  • void remove()：删除集合里上一次 next 方法返回的元素

• 快速失败（fail-fast）

  • 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改，modCount != expectedmodCount），则会抛出 ConcurrentModificationException
  • java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改

使用 foreach 循环遍历集合元素

• 与使用 Iterator 接口迭代访问集合元素类似，foreach 循环中的迭代变量也不是集合元素本身，系统只是依次把集合元素的值赋给迭代变量，所以在遍历时不能对 Collection 集合里的元素进行修改，否则会抛出 ConcurrentModificationException（可以使用特殊的集合 CopyOnWriteArrayList、CopyOnWriteSet、ConcurrentHashMap）

使用 for 循环遍历集合元素

• 在遍历时可以对 Collection 集合里的元素进行修改
• 当删除多个元素时，应从后往前遍历

List 集合

• 记录元素的添加顺序，允许元素重复的集合，列表
• 默认按元素的添加顺序设置元素的索引

List 接口

• List 判断两个对象相等的标准：两个对象相等通过 equals() 方法比较返回 true
• 增加
  • void add(int index, Object element)：将元素 element 插入到 List 集合的 index 处，索引范围 [0, size)
  • boolean addAll(int index, Collection c)：将集合 c 所包含的所有元素都插入到 List 集合的 index 处
• 删除
  • Object remove(int index)：删除并返回 index 索引处的元素
• 修改
  • Object set(int index, Object element)：将 index 索引处的元素替换成 element 对象，返回被替换的旧元素
• 查询
  • Object get(int index)：返回集合 index 索引处的元素
  • int indexOf(Object o)：返回对象 o 在 List 集合中第一次出现的位置索引
  • int lastIndexOf(Object o)：返回对象 o 在 List 集合中最后一次出现的位置索引
• 其它
  • List subList(int fromlndex, int tolndex)：返回从索引 fromlndex（包含）到索引 tolndex（不包含）处所有集合元素组成的子集合，返回的列表由此列表支持，因此返回列表中的非结构性更改将反映在此列表中，反之亦然
  • ListIterator<E> listIterator(int index)：返回一个 ListIterator 对象（双向的迭代器），从列表的指定位置开始

• 默认方法

  • void replaceAll(UnaryOperator<E> operator)：对列表中的每一个元素执行特定的操作，并用处理的结果替换该元素
  • void sort(Comparator<E> c)：使用提供的 Comparator 来比较元素排序该列表

• 常用构造器

  • ArrayList()：构造一个初始容量为 10 的空列表
  • ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的
  • HashSet()：构造一个新的空 set，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75
  • HashSet(Collection<? extends E> c)：构造一个包含指定 collection 中的元素的新 set

Listlterator 接口

• List 还可以使用普通的 for 循环、listIterator() 方法来遍历集合元素

• Listlterator 接口继承了 Iterator 接口，额外的方法：

  • boolean hasPrevious()：判断该迭代器关联的集合是否还有上一个元素
  • Object previous()：返回该迭代器的上一个元素
  • void add(Object o)：在指定位置插入一个元素
  • void set(E e)：用指定元素替换 next 或 previous 返回的最后一个元素

ArrayList<String> ls = new ArrayList<>();
// 普通 for 循环
for (int i = 0; i < ls.size(); i++) {
    System.out.println(ls.get(i));
}
// 增强 for 循环（底层采用 Iterator 迭代器）
for (String str : ls) {
    System.out.println(str);
}
// for 循环迭代器
for (Iterator<String> it = ls.iterator(); it.hasNext();) {
    System.out.println(it.next());
}
// while 循环迭代器
Iterator<String> it = ls.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}
// 自定义类中重写 equals() 方法
public class Point {
    private int x;
    private int y;
    // 此处省略 x 和 y 的 setter 和 getter 方法
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + x;
        result = prime * result + y;
        return result;
    }
    public boolean equals(Object obj) {
        // 是否同一对象
        if (this == obj) return true;
        // 是否为空
        if (obj == null) return false;
        // 类型是否相同
        if (getClass() != obj.getClass()) return false;
        Point other = (Point) obj; // 强转
        if (x != other.x) return false;
        if (y != other.y) return false;
        return true;
    }
}

ArrayList 和 Vector 实现类

• 基于 Object[] 的 List 接口的实现类，查询元素较快
• RandomAccess （标识接口，支持快速随机访问）的实现类
• 使用 initialCapacity 参数来设置该数组的长度，并且会自动增加（默认为 10）
• ArrayList 以 1.5 倍的方式扩容，Vector 以 2 倍的方式扩容
• Vector 的子类 Stack（用于模拟栈）中的额外方法（数组的最后一个元素位置作为栈顶）：void push(Object item)、Object pop()、Object peek()

LinkedList 实现类

• 基于双向链表的 List、Deque 接口的实现类，添加删除元素比较快
• 双向链表、单向队列、双向队列、栈（链表的第一个节点位置作为栈顶）

Queue 集合

• 队列，“先进先出”（FIFO）的容器

• Queue 接口中的方法

  • void add(Objecte)：将指定元素加入此队列的尾部
  • Object element()：获取队列头部的元素，但是不删除该元素
  • boolean offer(Objecte)：将指定元素加入此队列的尾部。当使用有容量限制的队列时，此方法通常比 add(Object e) 方法更好
  • Object peek()：获取队列头部的元素，但是不删除该元素。如果队列为空，则返回 null
  • Object poll()：获取队列头部的元素，并删除该元素。如果队列为空，则返回 null
  • Object remove()：获取队列头部的元素，并删除该元素

Deque 子接口

• 双端队列，支持在两端插入和移除元素
• 队列，将元素添加到双端队列的末尾，从双端队列的开头移除元素
• 栈，双端队列的开头作为栈顶

• 实现类：ArrayDeque、LinkedList

  
  图 1 Deque接口方法

• Iterator descendingIterator()：返回该双端队列对应的迭代器，该迭代器将以逆向顺序来迭代队列中的元素

PriorityQueue 优先队列

• 基于二叉堆实现

Set 集合

• 不记录元素的添加顺序，不允许元素重复的集合
• 尽量不要修改 Set 集合元素中判断两个元素相等的方法用到的实例变量，否则将会导致 Set 无法正确操作这些集合元素；Set 存储的对象必须覆写 hashCode 和 equals

HashSet 类

• 根据元素的 hashCode 值来计算其存储位置（哈希表），内部采用 HashMap 实现（将该元素作为 key，new Object() 作为 value 放入 HashMap 中）
• 最多包含一个 null 元素，其索引为 0
• HashSet 集合判断两个元素相等的标准：两个对象的 hashCode() 方法返回值相等，并且两个对象通过 equals() 方法比较也相等
• 链地址法解决 hash 冲突：如果两个对象的 hashCode() 方法返回的 hashCode 值相同，但通过 equals() 方法比较返回 false 时（hash 冲突），HashSet 会在这个位置（桶 bucket）用链表来保存这些对象（jdk 1.8 中，如果某位置碰撞的数量超过 8 就会将链表置为红黑树）
• 如果需要把某个类的对象保存到 HashSet 集合中，重写这个类的 equals()、hashCode() 方法时，应该尽量保证两个对象通过 equals() 方法比较返回 true 时，它们的 hashCode() 方法返回值也相等
• 当程序把可变对象添加到 HashSet 中之后，尽量不要去修改该集合元素中参与计算 hashCode()、equals() 的实例变量，否则将会导致 HashSet 无法正确操作这些集合元素

LinkedHashSet 类

• HashSet 的子类
• 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素添加的次序

TreeSet 类

• NavigableSet 接口（SortedSet 的子接口）的实现类，元素处于排序状态
• 根据红黑树结构确定元素的存储位置
• TreeSet 支持两种排序方法：自然排序（默认）和定制排序
• TreeSet 集合判断两个元素相等的标准：元素的 compareTo(Object obj) 方法或 Comparator 对象的 compare(T o1, T o2) 方法的返回值为 0
• 只能添加同一种类型的对象（需要比较大小），否则会引发 ClassCastException 异常

• 当需要把一个对象放入 TreeSet 中，重写该对象对应类的 equals() 方法时，应保证该方法与 compareTo(Object obj) 方法有一致的结果

• 额外的方法

  • 查询
    • Object first()：返回集合中的第一个元素
    • Object last()：返回集合中的最后一个元素
    • Object lower(Object e)：返回集合中位于指定元素之前的元素（即小于指定元素的最大元素，参考元素不需要是 TreeSet 集合里的元素）
    • Object higher (Object e)：返回集合中位于指定元素之后的元素（即大于指定元素的最小元素，参考元素不需要是 TreeSet 集合里的元素）
  • 其它
    • SortedSet subSet(Object fromElement, Object toElement)：返回此 Set 的子集合（部分视图），范围从 froraElement（包含）到 toElement （不包含），返回的 Set 受此 Set 支持，所以在返回 Set 中的更改将反映在此 Set 中，反之亦然
    • SortedSet headSet(Object toElement)：返回此 Set 的子集（部分视图），由小于 toElement 的元素组成，返回的 Set 受此 Set 支持，所以在返回 Set 中的更改将反映在此 Set 中，反之亦然
    • SortedSet tailSet(Object fromElement)：返回此 Set 的子集（部分视图），由大于或等于 fromElement 的元素组成，返回的 Set 受此 Set 支持，所以在返回 Set 中的更改将反映在此 Set 中，反之亦然
    • Comparator comparator()：如果 TreeSet 采用了定制排序，则该方法返回定制排序所使用的 Comparator；如果 TreeSet 采用了自然排序，则返回 null

自然排序

• 要求添加的对象的类必须实现 Comparable 接口
• 调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序排列
• java.lang.Comparable 接口：int compareTo(T o)：如果该对象小于、等于或大于指定对象，则分别返回负整数、0 或正整数
  
  
  图 2 不同类型的自然排序规则

定制排序

• 在创建 TreeSet 集合对象时，提供一个 Comparator 对象（比较器）与该 TreeSet 集合关联，由该 Comparator 对象负责集合元素的排序逻辑 new TreeSet(Comparator c)

• java.util.Comparator 接口：int compare(T o1, T o2)：如果第一个参数小于、等于或大于第二个参数，则分别返回负整数、0 或正整数

Map 集合

• 用于保存具有映射关系的数据，元素是 key-value 对（Entry），key 不允许重复
• 本质 Map.Entry[]
• 尽量不要修改作为 key 的可变对象的关键实例变量；自定义对象作为 key 必须覆写 hashCode 和 equals
• 增加 / 修改
  • Object put(Object key, Object value)：添加一个 key-value 对，如果当前 Map 中已有一个与该 key 相等的 key-value 对，则新的 key-value 对会覆盖原来的 key-value 对，返回被覆盖的 value，否则返回 null
  • void putAll(Map m)：将指定 Map 中的 key-value 对复制到本 Map 中
• 删除
  • Object remove(Object key)：删除指定 key 所对应的 key-value 对，返回被删除 key 所关联的 value，如果该 key 不存在，则返回 null
  • boolean remove(Object key, Object value)：删除指定 key、value 所对应的 key-value 对（Java 8 新增）
  • void clear()：删除该 Map 对象中的所有 key-value 对
• 查询
  • Object get(Object key)：返回指定 key 所对应的 value；如果此 Map 中不包含该 key，则返回 null
  • boolean containsKey(Object key)：査询 Map 中是否包含指定的 key，如果包含则返回 true
  • boolean containsValue(Object value)：查询 Map 中是否包含一个或多个 value，如果包含则返回true
  • boolean isEmpty()：查询该 Map 是否为空（即不包含任何 key-value 对），如果为空则返回 true
  • int size()：查询该 Map 里的 key-value 对的个数
• 其它
  • Set<K> keySet()：返回该 Map 中所有 key 组成的 Set 集合（相应实现类中的内部类，不支持 add 或 addAll 操作）
  • Collection<V> values()：返回该 Map 里所有 value 组成的 Collection（相应实现类中的内部类，不支持 add 或 addAll 操作）
  • Set<Map.Entry<K, V>> entrySet()：返回 Map 中包含的 key-value 对所组成的 Set 集合，每个集合元素都是 Map.Entry 对象（不支持 add 或 addAll 操作）
• 默认方法
  • void forEach(BiConsumer<K, V> action)：对此映射中的每个条目执行给定的操作
  • V computeIfAbsent(K key, Function<K, V> mappingFunction)：如果 key 不存在或者对应的值是 null，则调用 mappingFunction 来产生一个值，然后将其放入 Map，再返回这个值；否则的话返回 Map 已存在的对应的值
  • V putIfAbsent(K key, V value)：如果 key 不存在或者对应的值是 null，则将 value 设置进去，然后返回 null；否则返回 Map 中对应的值，而不做其它操作
  • V getOrDefault(Object key, V defaultValue)：如果 key 不存在或者对应的值是 null，则返回 defaultValue
  • boolean remove(Object key, Object value)：仅当指定的 key 当前映射到指定的值时删除该条目
  • boolean replace(K key, V oldValue, V newValue)：仅当当前映射到指定的值时，才替换指定键的条目
  • V merge(K key, V value, BiFunction<V, V, V> remappingFunction)：如果指定的 key 尚未与值相关联或与 null 相关联，则将其与给定的非空 value 相关联，否则将关联值替换为给定重映射函数的结果
• 常用构造器
  • HashMap()：构造一个具有默认初始容量（16）和默认加载因子（0.75）的空 HashMap
  • HashMap(Map<? extends K,? extends V> m)：构造一个映射关系与指定 Map 相同的新 HashMap
    

内部类 Map.Entry

• 内部类 Map.Entry ，封装了一个 key-value 对

• 静态方法

  • Comparable<K>, V> Comparator<Map.Entry<K, V>> comparingByKey()：返回一个比较器，按自然顺序比较 Map.Entry 中的 key
  • Comparator<Map.Entry<K, V>> comparingByKey(Comparator<K> cmp)：返回一个比较器，使用给定的 Comparator 比较 Map.Entry 中的 key
  • Comparator<Map.Entry<K, V>> comparingByValue()：返回一个比较器，按自然顺序比较 Map.Entry 中的 value
  • Comparator<Map.Entry<K, V>> comparingByValue(Comparator<V> cmp)：返回一个比较器，使用给定的 Comparator 比较 Map.Entry 中的 value

• 实例方法
  • Object getKey()：返回该 Entry 里包含的 key 值
  • Object getValue()：返回该 Entry 里包含的 value 值
  • Object setValue(V value)：设置该 Entry 里包含的 value 值，并返回新设置的 value 值

// 通过 keySet
Set<String> keySet = map.keySet();
for (String key : keySet) {
    System.out.println(key + "<=>"+map.get(key));
}
// (推荐)通过 entrySet
Set<Entry<String, Integer>> entrySet = map.entrySet();
for (Map.Entry<String, Integer> entry : entrySet) {
    System.out.println(entry.getKey() + "<=>" + entry.getValue());
}
// (推荐)通过 Map.forEach
properties.forEach((key, value) -> {
    System.out.println(key + "<=>" + value);
});
List<Map<String, Object>> list = new ArrayList<>();

HashMap 和 Hashtable 实现类

• HashMap 可以使用 null 作为 key 或 value，Hashtable 不允许

• 无序，底层采用数组（Node[] table）和链表来存储 key-value 对

• 保证 key 唯一的原理和 HashSet 一样：首先 hash(key) 得到 key 的 hashcode，hashmap 根据获得的 hashcode 找到要插入的位置所在的链，在这个链里面放的都是 hashcode 相同的 Entry 键值对，在找到这个链之后，会通过 equals() 方法判断是否已经存在要插入的键值对，而这个 equals 比较的其实就是 key

• 默认的初始容量（capacity）为 16

• 当通过构造器指定集合初始容量时，实际初始化时的容量为大于指定参数且最近的 2 的整数次幂的数（tableSizeFor() 方法），即 2->2、3->4、7->8、13->16

• 建议 initialCapacity = (int) (expectedSize / 0.75f + 1)（com.google.common.collect.Maps#capacity 或 newHashMapWithExpectedSize）或 initialCapacity = (int) Math.ceil(expectedSize / 0.75f)

  
  图 3 Maps.newHashMapWithExpectedSize

• 负载因子（load factor）等于“size/capacity’’，默认的负载极限为 0.75，表明当该 hash 表的 3/4 已经被填满，再添加 key-value 对时，hash 表会发生 rehashing，即 hash 表会自动成倍地增加容量（桶的数量），并将原有的对象重新分配，放入新的桶内

• 较高的“负载极限”可以降低 hash 表所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的操作（HashMap 的 get() 与 put() 方法都要用到查询）；较低的“负载极限”会提高查询数据的性能，但会增加 hash 表所占用的内存开销

LinkedHashMap 类

• HashMap 的子类，使用双向链表来维护 key-value 对的添加顺序
• 可用来构建 LRU 缓存

Properties 类

• Hashtable 类的子类，可以用来读写配置文件（xml 文件、ini 文件、properties 文件）

• key、value 都是 String 类型

• 修改 Properties 里的 key、value 值的方法：

  • Object setProperty(String key, String value)：设置属性值，类似于 Hashtable 的 put() 方法
  • String getProperty(String key)：获取指定属性名对应的属性值，类似于 Map 的 get(Object key) 方法
  • String getProperty(String key, String defaultValue)：获取指定属性名对应的属性值，如果不存在指定的 key 时，则该方法返回指定默认值

• 读写属性文件的方法：

  • void load(InputStream inStream)：从属性文件（以输入流表示）中加载 key-value 对，把加载到的 key-value 对追加到该 Properties 里
  • void store(OutputStream out, String comments)：将注释 comments 及该 Properties 中的 key-value 对输出到指定的属性文件（以输出流表示）中
• 获取当前工程路径：System.getProperty("user.dir")

SortedMap 接口和 TreeMap 实现类

• 底层采用红黑树来管理 key-value 对（ 红黑树的节点）
• TreeMap 存储 key-value 对（节点）时，需要根据 key 对节点进行排序（自然排序、定制排序）

• 保证 key 唯一的原理和 TreeSet 一样

  
  图 4 Java_8集合类和接口中新增的方法

操作集合的工具类 Collections

java.util.Collections 中常用的类方法：

• 排序操作void reverse(List list)：反转指定 List 集合中元素的顺序void shuffle(Listlist)：对 List 集合元素进行随机排序void sort(List list)：根据元素的自然顺序对指定 List 集合的元素按升序进行排序（底层是调用 Arrays.sort()）sort(List<T> list, Comparator<? super T> c)：根据指定比较器产生的顺序对指定 List 集合的元素进行排序void swap(List list, int i, int j)：将指定 List 集合的 i 处元素和 j 处元素进行交换

• 查找、替换、添加操作int binarySearch(List list, Object key)：使用二分搜索法搜索指定对象在 List 集合中的索引（调用该方法时要求 List 中的元素已经处于有序状态）Object min(Collection coll)：根据元素的自然顺序， 返回给定集合中的最小元素Object max(Collectioncoll)：根据元素的自然顺序， 返回给定集合中的最大元素boolean replaceAll(List list, Object oldVal, Object newVal)：使用一个新值 newVal 替换 List 对象的所有旧值 oldValboolean addAll(Collection<? super T> c, T… elements)：将所有指定元素添加到指定 collection 中

• 创建空集对象

// 创建 List 空集对象
List<Object> list1 = Collections.EMPTY_LIST; // 返回的是不可变的空集合
List<Object> list2 = Collections.emptyList(); // 返回的是不可变的空集合
List<Object> list3 = new ArrayList(); // 从 jdk 1.7 开始 ArrayList 的构造器默认创建的是空集

• 创建不可变的单元素集合Set<T> singleton(T o)：返回一个只包含指定对象的不可变 setList<T> singletonList(T o)：返回一个只包含指定对象的不可变列表Map<K, V> singletonMap(K key, V value)：返回一个不可变的映射，它只将指定键映射到指定值

• 返回不可修改的集合视图 List<T> unmodifiableList(List<T> list)：返回指定列表的不可修改视图Set<T> unmodifiableSet(Set<T> s)：返回指定 set 的不可修改视图 Map<K, V> unmodifiableMap(Map<K, V> m)：返回指定映射的不可修改视图

• 同步控制：将集合对象包装成线程同步的集合

// 创建线程安全的集合对象
List<Object> lsit = Collections.synchronizedList(new ArrayList<Object>());
Set<Object> set = Collections.synchronizedSet(new HashSet<Object>());
Map<String, Object> map = Collections.synchronizedMap(new HashMap<String, Object>());
// 在返回的集合对象上进行迭代时，需要手动同步 
synchronized (list) {
    Iterator it = list.iterator();
    while (it.hasNext())
        it.next();
}