Java 集合

1. Java 集合类简介

1.1 集合概览

Java 集合类主要都是从 Collection 和 Map 两个接口派生而成，其中 Collection 又包含 List、Set 和 Queue，如下图。Java 集合就像容器，能够将多个同类型的对象装进该容器中，所以又叫容器。其中各集合含义如下：

• Map：代表具有映射关系的集合，通过 key-value 存储，其中 key 是不可重复的，用于标识集合中的每项数据；
• List：代表有序、可重复的集合；
• Set：代表无序、不可重复的集合；
• Queue：队列集合实现；

// jdk 1.8 中 Collection 的源码

public interface Collection<E> extends Iterable<E> {
    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    boolean add(E e);

    boolean remove(Object o);

    boolean containsAll(java.util.Collection<?> c);

    boolean addAll(java.util.Collection<? extends E> c);

    boolean removeAll(java.util.Collection<?> c);

    ... //省略了其他方法
}

// jdk 1.8 中 Map 源码，其中内部接口 Entry<K, V> 对应 Map 的键值对

public interface Map<K,V> {
    int size();

    boolean containsKey(Object key);

    boolean containsValue(Object value);

    V get(Object key);

    V put(K key, V value);

    V remove(Object key);

    void putAll(java.util.Map<? extends K, ? extends V> m);

    void clear();

    Set<K> keySet();

    Collection<V> values();

    Set<java.util.Map.Entry<K, V>> entrySet();

    interface Entry<K,V> {
        K getKey();

        V getValue();

        V setValue(V value);

        boolean equals(Object o);

        int hashCode();

        ...
    }

    boolean equals(Object o);

    int hashCode();

}

1.2 集合选用技巧

主要根据集合的特点来进行选择：

1. 如果需要存放元素值：
   • 要保证元素唯一，选用实现 Set 接口的集合 HashSet 或 TreeSet；
   • 不用保证元素唯一，选择实现 List 接口的集合 ArrayList 或 LinkedList；
2. 如果需要存放键值对：
   • 需要排序：选用 Map 接口下的 TreeMap；
   • 无需排序：选用 Map 接口下的 HashMap；
   • 保证线程安全：选用 Map 接口下的 ConcurrentHashMap；

2. 集合 vs 数组

集合和数组都是 Java 中重要的数据结构，两者之间的区别主要有如下两点：

3. Collection

Collection 是 Set、List、Queue 的父接口，主要提供了如下方法供子类实现，从而实现数据操作。

其中 iterator() 方法的返回值 Iterator 接口类叫做 迭代器，主要用于遍历集合元素，定义了如下两个方法：

public class Main(){
    public static void main(String[] args){
        Collection<Integer> list = new ArrayList<>();
        for(int i = 0; i < 10; i++){
            list.add(i);
        }

        // 获取迭代器
        Iterator<Integer> iterator = list.iterator();
        // 遍历集合
        while(iterator.hasNext()){
            Integer value = iterator.next();
            System.out.print("t" + value);
        }
    }
}

4. Collection 之 Set

Set 集合继承于 Collection，用于 Collection 有的所有方法，未提供额外方法。Set 不允许包含重复元素，如果试图将两个相同元素加入同一 Set 中，将导致失败。

4.1 HashSet 类

1. HashSet 的特点

• 无法保证元素的排列顺序；
• HashSet 不是同步的，若多个线程同时访问一个 HashSet，则必须通过代码来保证其同步；
• 集合元素值可以是 null；

1. LinkedHashSet

LinkedHashSet 是 HashSet 的子类，同样是根据元素的 hashCode 来决定元素的存储位置，同时用链表维护元素顺序，从而保证元素以插入的顺序来保存。

1. HashSet 中判断集合元素相等

不同的对象进行比较，可以有如下四种情况：

• 若两元素通过 equal() 方法比较返回 false，但两者的 hashCode() 返回不相等，则将其存储在不同位置；
• 若两元素通过 equal() 方法比较返回 true，但两者的 hashCode() 返回不相等，则将其存储在不同位置；
• 若两元素通过 equal() 方法比较返回 false，但两者的 hashCode() 返回相等，则将其存储在相同位置，在这个位置以链表式结构来保存多个对象。因为向 HashSet 集合中存入一个元素时，HashSet 将调用对象的 hashCode() 获取其 hash 值，然后根据 hash 值来决定对象在 HashSet 中的存储位置；
• 若两元素通过 equal() 方法比较返回 true，且两者的 hashCode() 返回相等，则不添加到 HashSet；

4.2 TreeSet 类

一组有序的集合，若未指定排序规则 Comparator，则按照自然排序。

注意：TreeSet 中的元素都必须实现 Comparable 接口；

4.3 HashSet vs LinkedHashSet vs TreeSet

5. Collection 之 List

5.1 List 常用方法

List 是一个元素有序、可重复的集合，其中的每个元素均有对应的顺序索引，允许使用重复元素，通过索引来访问指定位置的集合元素，继承自 Collection，拥有其所有方法，此外还有其他一些根据索引来操作元素的方法，如下：

5.2 ArrayList

1. ArrayList 特点
   • 实现了 List 接口的可变数组；
   • 可以插入 null；
   • 非 synchronized；
   • 其 size(),isEmpty(),get(),set(),iterator(),add() 等方法的时间复杂度均为

   O(1)

   ；

5.3 LinkedList

LinkedList 是一个链表维护的序列容器，和 ArrayList 最大的区别在于其底层实现，前者使用链表，后者使用数组，所以选用时可以根据数组和链表的特性来进行选择，主要不同有如下几点：

• 数组查找效率高，能够通过索引直接查找出对应元素，但链表却需要每次都从头开始；
• 链表插入和删除元素比较高效，只需要在插入或删除位置断链后重组链即可，但数组需要重新复制一份将所有数据后移或前移；
• 动态申请内存时，链表只需要动态创建，但数组达到初始申请长度后，需要重新申请一个更大的数组，并将原来数组的数据迁移过去；

5.4 ArrayList vs LinkedList

6. Collection 之 Queue

6.1 Queue 常用方法

Queue 用于模拟队列这种数据结构，是一种 先进先出（FIFO，first-in-first-out） 的容器。队列头部是队列中存放时间最长的元素，尾部元素是队列中存放时间最短的元素。新的元素插入（offer()）到队列尾部，访问元素（poll）操作将返回队列头部元素，通常接口中提供了如下方法 ：

7. Map

7.1 Map 常用方法

Map 用于保存具有映射关系的数据，所以通常保存着两组数，一组保存 key，一组保存 value 。两者都可以是任意引用类型的数据，但是 key 不允许重复。接口中通常提供了如下方法：

7.2 HashMap

最基础常用的一种 Map，无序且以散列表的方式进行存储。HashSet 其实就是基于 HashMap，将其 key 作为单个元素进行存储。关于 HashMap 的更多知识，可以参看 HashMap 知多少[1]。

7.3 LinkedHashMap

和 HashMap 最大的区别在于 LinkedHashMap 遍历时是有序的，可以保存插入时的顺序，同时还可以设置根据最近访问的元素放在最前面（即 LRU）；

7.4 TreeMap

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator进行排序，具体取决于使用的构造方法。TreeMap 的基本操作 containsKey、get、put和 remove 的时间复杂度是

log(n)

。另外，TreeMap是非同步的。它的 iterator方法返回的迭代器是 fail-fastl 的。

7.5 WeakHashMap

除了自身有对 key 的引用之外，若 key 没有其他引用指向它，此时就会自动丢弃该值。

7.6 各 Map 类型对比

参考资料

[1]

HashMap 知多少: 3.HashMap.md

更多教程请访问码农之家

点击查看往期精彩内容

二叉树的 4 种遍历方式，你会多少？

面试中最长常问到的 HashMap，你都知道多少？