书成

再这样堕落下去就给我去死啊你这混蛋！！！

0%

Java集合

发表于 分类于

Java集合

集合表示一组对象，称为它的元素。一些集合允许重复元素，而另一些则不允许。有些是有序的，有些是无序的。

Collection 与 Iterator

Java 集合的顶层接口是 java.util.Collection<E>,它作为集合层次结构中的根接口，定义了集合应有的一些基础方法，例如 add, clear, contains 等方法。

Collection 接口继承了 Iterable 接口，该接口的 iterator() 方法会返回一个迭代器,可以遍历集合中的元素。

Iterator 接口是集合上的迭代器。迭代器在Java集合框架中代替枚举。迭代器与枚举有两个不同之处:

  • 迭代器允许调用者在迭代期间使用定义良好的语义从基础集合中删除元素。
  • 方法名得到了改进。

Iterator 接口主要包含以下三个方法：

方法 作用
hasNext() 判断迭代器是否还有元素
next() 获得迭代器的下一个元素
remove() 删除迭代器返回的最后一个元素

List

List 是有序的集合，用户可以精确地控制每个元素在列表中的位置。用户可以通过元素的整数索引(在列表中的位置)访问元素，并搜索列表中的元素。列表中的元素是可以重复的。

ArrayList

ArrayList 是基于数组实现的 List 类，封装了一个动态增长的 Object 数组，支持元素的随机访问，适合查找和遍历，不适合插入和删除。ArrayList 默认大小为 10， 扩容为 1.5 倍扩容。

ArrayList 虽然线程不安全，但是它的父类 AbstractList 定义了一个 modCount 的变量，记录了这个列表在结构上被修改的次数。如果该字段的值意外更改，迭代器(或列表迭代器)将抛出一个 ConcurrentModificationException 。

例如在 ArrayList 的 writeObject 方法中，通过这个变量确保在多线程情况下列表序列化时结构更改时会抛出异常让调用者得知：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioral compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        // 如果结构发生改变，抛出异常让调用者得知
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

LinkedList

LinkedList 是双链表实现的list和Deque接口。实现所有可选的列表操作，并允许所有元素(包括null)。

Deque 接口是双端队列接口，可以在队列两端操作元素。

Vector

Vector 是线程安全版本的 ArrayList，但是性能低下，不常用。

CopyOnWriteArrayList

一个线程安全的ArrayList变体，其中所有可变操作(添加、设置等)都是通过生成底层数组的新副本来实现的，即写时复制策略。

例如它的 add 函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}

但是 CopyOnWriteArrayList 会产生数据弱一致性问题，即读的线程可能不会立即感知到写线程对数据的修改。

Map

Map 接口不是 Collction 接口的子接口，它以 key-value 的形式保存数据。

HashMap

HashMap 是基于哈希表实现的映射接口，它不能保证内部元素的顺序。

HashMap 的默认容量大小是16，负载因子是0.75，且 HashMap 的大小一定为2的幂次方。因为容量为2的幂次方时，当需要扩容时，很容易计算出元素再哈希的值。

在 jdk1.8 之后，HashMap 的哈希扰动函数如下：

1
2
3
4
5
static final int hash(Object key) {
    int h;
    // 高16位与低16位异或，加大低位随机性！！！
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap 处理哈希冲突的方式是链表法，在1.8之后，当链表长度大于8时，会转为红黑树，当红黑树节点个数小于6时，会转为链表。因为红黑树相比较链表更加占用空间，所以当链表到达一定长度时才转换。

HashMap 在 jdk1.8 之前采用头插法，多线程下可能会造成环，jdk1.8 之后采用尾插法，不会造成环，但是多线程下依旧不安全。

LinkedHashMap

LinkedHashMap 继承 HashMap，它维护了一个双向链表。

当它的属性 accessOrder 为 true 时，表示访问顺序，某一个节点被访问时将它移动到链表尾部，这样链表头就是最久未使用节点。当它的属性 accessOrder 为 false 时，表示插入顺序，某一个节点插入时将它移动到链表尾部，这样链表头就是最早插入的节点。

可以通过继承它实现最简单的缓存：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;
 
    private int maxCacheSize;
 
    public LruCache(int maxCacheSize) {
        // 第三个参数为 accessOrder，传入 true 表示按照按照访问顺序排列元素，最近访问的元素会排在队末尾
        super(maxCacheSize, 0.75f, true);
        this.maxCacheSize = maxCacheSize;
    }
 
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        // 这个函数返回 true 时会删除链表头的元素
        // 当达到预设缓存上限时删除最老元素
        return this.size() >= maxCacheSize + 1;
    }
 
}

Set

Set 接口表示不包含重复元素的集合。

HashSet

HashSet 实现了Set接口，它由一个哈希表(实际上是一个HashMap实例)支持。它不能保证集合的迭代顺序;特别是，它不能保证顺序随时间保持不变。这个类允许空元素。

LinkedHashSet

LinkedHashSet 继承自 HashSet，它实际上由一个 LinkedHashMap 实例支持。能维护元素的插入次序。

TreeSet

TreeSet 通过红黑树维护元素的插入次序。