Java集合容器梳理

在 Java 中，集合可以笼统的分为两类：数组与列表，二者各有各有的优缺点。

数组为顺序存储，在随机读取即通过下标方式访问上速度优于列表，但在增删改需要从目标位置移动大量数据，因此效率相对更低。

列表底层实现逻辑为链表，在插入删除时只需更新指针指向，显然效果高于数组，但在随机读取时因为链表特性需要从头逐一遍历因此效率低于数组。

因此二者并没有孰优孰略，应根据不同的业务场景选择合适的实现方式。

下面分别盘点 Java 中常用的集合容器。

一、数组容器

1. Array

数组作为基本的数据结构之一其底层逻辑为一片连续的物理存储空间，在随机访问时拥有不俗的性能，常见的声明方式共有两种：一种为在创建时仅声明大小不定义内容，另一种为同时声明大小和内容。

需要注意的是无论哪种方式都必须在创建时定义长度，后续只允许修改数组内容，并不允许修改数组长度。

简而言之，即数组为定长集合且大小在初始化时确定。

/**
 * 声明容量后再赋值
 */
public void demo1() {
    String[] strArr = new String[2];
    strArr[0] = "Hello";
    strArr[1] = "World";
}

/**
 * 同时定义大小和内容，以下两种定义方式等价
 */
public void demo2() {
    String[] arr1 = {"Hello", "World"};
    String[] arr2 = new String[]{"Hello", "World"};
}

(1) 类型转化

通过 Arrays.asList() 可以将数组与列表之间进行转化。

需注意转化后对于底层而言仍为数组，无法使用 add() 等操作，须通过 stream 流的方式转化才允许。

public void arrayToList() {
    String[] str = {"path1", "path2", "path3"};
    
    // add() 非法
    List<String> list1 = Arrays.asList(str);
    list.add("path4");
    System.out.println(list1);

    // add() 合法
    List<String> list2 = Arrays.stream(str).collect(Collectors.toList());
    list2.add("path4");
    System.out.println(list2);
}

2. Vector

Vector 底层封装了数组，在此基础上新增了扩容操作，弥补了普通数据必须在定义时固定长度的缺点，且元素操作封装了 synchronized 因此为线程安全容器，在多线程并发情况下可替代 ArrayList 容器。

但由于 Vector 的锁是通过 synchronized 并基于类层级的，虽实现了线程安全当频繁操作时性能相对较低，在现行的编程中用到的较少。

// Vector addElement 源码实现，通过 synchronized 保证原子性
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

通过 new Vector<>() 创建的容器默认大小为 10，也可通过 new Vector<>(init, increase) 指定初始容量与递增量，当数组长度达到 init 大小后，将会根据自动扩容 increase 个空间，若未指定默认的初始容量为 10，增长量为当前容量的一倍。

public void vectorDemo() {
    // 初始化长度 4, 超过则再扩容 5 个单位
    Vector<Integer> vector = new Vector<>(4, 5);
    for (int i = 1; i < 6; i += 2) {
        vector.addElement(new Integer(i));
    }
    System.out.println(vector);
    // 总容量大小
    System.out.println(vector.capacity());

    // 在下标 2 处插入元素
    vector.insertElementAt(new Integer(2), 2);
    // 移除在下标 2 的元素
    vector.removeElementAt(2);
    // 移除值为 4 的元素
    vector.removeElement(new Integer(4));
    System.out.println(vector);
}

二、List容器

1. ArrayList

ArrayList 是 List 的接口实现类，按照存入的顺序存放元素，是有序集合且允许重复元素。

ArrayList 是非线程安全容器，在多线程并发下将会抛出异常，并发场景下可考虑选用 Vector 或 CopyOnWriteArrayList 容器进行替代。

常见方法接口参考下表内容。

方法	作用
add()	添加单个元素至容器内。
addAll()	向容器内添加集合。
get()	根据下标获取元素，从 0 开始
set(i, v)	将元素 v 插入至下标为 i 位置， i 不能大于集合 size。
remove()	移除容器单个元素。
removeAll()	批量移除容器中的元素。
clear()	清空整个容器内容。
size()	获取当前容器中的元素个数。
isEmpty()	判断当前容器是否为空，返回 boolean 值。

public void listDemo() {
    List<String> list = new ArrayList<>();
    list.add("Jack");
    list.add("Beth");
    list.add("Mark");
    System.out.println(list);
}

2. LinkedList

LinkedList 同样是 List 的接口实现类，底层实现为 链表，可以在任意位置进行高效插入删除操作。

LinkedList 常见操作方法参考下表：

方法	作用
addFirst()	在链头插入元素。
getFirst()	获取链头元素。
removeFirst()	移除链头元素。
addLast()	在链尾插入元素。
getLast()	获取链尾元素。
removeLast()	移除链尾元素。

由于链表的自身特性，其相邻元素间通过指针连接，故不支持下标随机访问，即获取元素时只能通过首节点依次遍历指针往后读取，但对于插入与新增则通过变化指针指向即可。

因此，LinkedList 在读取频繁的场景下性能低于 ArrayList，但在写入或修改的情景下拥有不错的性能。

3. CopyOnWriteArrayList

CopyOnWriteArrayList 进一步扩展了 ArrayList 操作接口，在操作元素时会先复制一份原集合，将待执行操作在复制的容器中执行，最后再将旧容器的引用指向新容器。

通过复制可以解决多线程并发 读取 ，但同时复制会导致内存资源占用，且只能保证数据最终一致性，无法保证实时一致性。

观察其添加方法 add() 可以看出在添加元素时通过 synchronized 实现加锁，保证同一时刻只有单个线程在操作，然后将原容器通过 Arrays.copyOf() 实现复制并将新元素添加至复制的容器中，最后将旧容器的引用指向复制添加后的新容器。

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true;
    }
}

final void setArray(Object[] a) {
    array = a;
}

CopyOnWriteArrayList 容器的 set() 与 remove() 等常用列表方法采取的实现方式类似，都是通过 synchronized 配合复制操作实现，这里不重复介绍。需要注意其 get() 方法没有实现加锁，因此在增改容器时若执行查询读取的数据仍可能是旧制，因为操作时发生在复制的容器中（未完成前引用指向的仍是旧容器），但其保证了最终的数据一致性。

4. SynchronizedList

在 JDK 中的 Collections 集合工具类中提供了 synchronizedList() 方法可将 ArrayList 转为线程安全容器。

其是基于对象的 synchronized 锁，相对 Vector 更为轻量，同时与 CopyOnWriteArrayList 相比也更为节省内存。

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    // 转为线程安全容器
    List<String> synList = Collections.synchronizedList(list);
}


// SynchronizedList 部分源码
public class Collections {
    public static <T> List<T> synchronizedList(List<T> list) {
        // ArrayList 实现了 RandomAccess
        return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<>(list) :
                new SynchronizedList<>(list));
    }

    // SynchronizedRandomAccessList 继承于 SynchronizedList
    static class SynchronizedRandomAccessList<E>
            extends SynchronizedList<E>
            implements RandomAccess { }

    // SynchronizedList 继承于 SynchronizedCollection
    static class SynchronizedList<E>
            extends SynchronizedCollection<E>
            implements List<E> {
                
        public void add(int index, E element) {
            // mutex 为继承父类中的对象用于加锁
            synchronized (mutex) {list.add(index, element);}
        }
    } 

    static class SynchronizedCollection<E> implements Collection<E>, Serializable { 
        final Object mutex;     // Object on which to synchronize

        // 重写了一系列方法加锁以实现线程安全，此处不一一列举
        public boolean addAll(Collection<? extends E> coll) {
            synchronized (mutex) {return c.addAll(coll);}
        }
        public boolean removeAll(Collection<?> coll) {
            synchronized (mutex) {return c.removeAll(coll);}
        }
    }
}

三、Set容器

1. HashSet

HashSet 是无序集合，根据数据的哈希值进行排序存储，不允许存入重复元素，非线程安全。

如果你查看 HashSet 的源码即可发现其是基于 HashMap 结构进行存储，其中对应的 Key 即为存入的数据，而 value 则填充了一个空对象，而 HashMap 是基于哈希值进行存储的，因此在去重或判断值等操作上 HashSet 往往相较于 ArrayList 拥有更好的性能。

// ============ HashSet 源码片段截取 ============
private transient HashMap<E,Object> map;

public HashSet() {
    map = new HashMap<>();
}

private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

// ============ HashMap 源码片段截取 ============
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

2. LinkedHashSet

LinkedHashSet 在基于链表扩展实现，因此其为有序集合，按照存入的顺序存放元素，与 HashSet 类似其不允许重复元素，性能方面略低于 HashSet。

如存入按照 A, B, C 顺序存入三个对象至 LinkedHashSet 集合，则最后输出的结果一定是 [A, B, C]，倘若换为 HashSet，则输出的结果顺序为 A, B, C 的排列组合，每一次输出的结果都将不一致。

3. TreeSet

TreeSet 是 SortedSet 接口的唯一实现类，对存入的元素基于红黑树排序存储。

4. CopyOnWriteArraySet

CopyOnWriteArraySet 作用效果与 CopyOnWriteArrayList 效果类似，这里不再详细介绍。

四、Map对象

1. 数据结构

HashMap 底层实现主要分为部分：数组和链表/红黑树。数组是 HashMap 的主体，链表和红黑树是为了解决哈希冲突而存在的辅助结构。

当我们向 HashMap 中 put 键值对时， HashMap 会根据键的哈希值算出其在数组中的位置，然后将键值对存储在数组的对应位置上。如果发生哈希冲突 HashMap 会将发生冲突的键值对以链表的形式存储在对应位置上。但是，如果链表中的元素超过了一定的数量，为了提高查询效率， HashMap 会将链表转换为红黑树。

2. HashMap

HashMap 是一种无序序列（根据哈希值进行排序存储）的数据结构，数据以键值对形式存储，非线程安全。其中 key 值不允许重复，对于存入 key 重复的元素进行覆盖，并有且仅有一个元素的的 key 值可为 null 。

HashMap 容器的存储效率由 capacity 与 loadFactor 变量控制，前者为容器的大小，默认为 16，后者为容器的扩容策略，取值范围为 0~1，默认值为 0.75，当容器的内的元素数量达到 capacity*loadFactor 时将自动扩容为 2*capacity。

即默认初始化容器大小为 16，当存入的个数超过 12(16*0.75) 时，容器大小将扩容至 32(16*2)，以此类推。

3. LinkedHashMap

LinkedHashMap 与之前提到的 LinkedHashSet 类似，其底层基于链表实现，因此其容器内存储的数据并非和 HashMap 一样无序，而是根据存入的先后顺序而定。

4. TreeMap

TreeMap 基于红黑树实现，与 TreeSet 容器类似其对于存入的元素根据元素的 Key 进行排序，正因有序的特性，故其性能自然也低于 HashMap。

5. HashTable

HashTable 与 HashMap 类似，但其操作使用 synchronized 关键字保证多线程的数据原子性。

具象的使用示例不再重复介绍，这里分析一下其对应的源码实现。打开 HashTable 的源码，可以看见几乎所有操作方法都被 synchronized 关键字修饰，因此在并发的情景下仅有一个线程能取得锁实现对应操作，从而达到线程安全的效果。

public synchronized V get(Object key) {
    // Omit code

}

public synchronized V put(K key, V value) {
    // Omit code

}

public synchronized V remove(Object key) {
    // Omit code

}

6. ConcurrentHashMap

ConcurrentHashMap 与 HashTable 都是线程安全，但前者针对后者实现进一步的优化，从而实现更高的性能。

在上述 HashTable 的示例中介绍了其通过方法加 synchronized 关键字实现线程安全，但该方法将锁住整个数据结构相对过于笨重，而 ConcurrentHashMap 正是在此基础上实现更细粒度上的操控达到线程安全的同时拥有更好性能。

下面以 ConcurrentHashMap 的 put() 方式为例，通过源码可以看到在添加元素时当容器为空或被添加的元素不存在于容器中(Key 值不重复)时并没有选择加锁，只有当数据出现重复时通过 synchronized 关键字锁住需添加的对象。而 HashTable 锁住的是整个容器结构， ConcurrentHashMap 通过更细粒的操作保证相同的元素在同一刻只有一个线程能获取其锁对象，但是不影响其它元素的操作。

概括而言，ConcurrentHashMap 只对影响一致性的容器元素加锁控制，并且锁的作用对象是单个目标元素而非整个容器结构，因此其在实现线程安全的情况下仍能达到相对较好的性能。

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            // 容器不存在则初始化
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 容器为空直接添加（未加锁）
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;                   
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else if (onlyIfAbsent // check first node without acquiring lock
                && fh == hash
                && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                && (fv = f.val) != null)
            // 元素首次添加不加锁
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                // 加锁并发控制，略去具体实现
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

7. Properties

Properties 类继承于 Hashtable，因此使用起来二者其实差别并不大，但 Properties 为我们额外封装的一些方法可应用于部分业务场景。

通过 Properties 类的 load() 方法可以便捷的将 .conf、.properties 等配置文件以键值对的形式加载。

如下示例中则读取 boostrap.conf 文件的内容并赋值 Properties 对象。

public void propertiesDemo() throws IOException {
    String location = "/data/bootstrap.conf";
    try (
            InputStream in = Files.newInputStream(Paths.get(location));
            InputStreamReader reader = new InputStreamReader(in);
    ) {
        Properties props = new Properties();
        props.load(reader);
        System.out.println(props);
    } catch (IOException e) {
        throw new RuntimeException(e);
    }
}

与之相似，除了从配置文件中读取信息， Properties 支持将信息持久化保存至本地空间。

如下示例中将 Properties 对象内容以文件访问保存至 src\\main\\resources 目录下。

public void propertiesDemo() {
    Properties prop = new Properties();
    prop.setProperty("key3", "value3");
    prop.setProperty("key4", "value4");
    prop.setProperty("key5", "value5");

    // 导出文件
    String location = "/data/bootstrap.conf";
    try (OutputStream out = new FileOutputStream("src\\main\\resources\\test.xml")) {
        prop.store(out, " Configuration file",);
    } catch (IOException e) {
        throw new RuntimeException(e);
    }
}

五、栈结构

1. 基本结构

栈 (Stack) 是一种单向通道 先进后出 的线性结构，先入栈的元素在栈底。

如存在一组数据 [1, 2, 3, ..., n] 并按照顺序压入栈内，则读取的顺序则正好相反为 [n, ..., 3, 2, 1]。

2. 操作方式

Stack 容器常见操作参考下表：

方法	作用
peek()	访问栈顶元素。
pop()	弹出栈顶元素并返回值。
push()	添加元素。
search()	返回对应元素的位置。