Java 集合框架（上）

友情提示：文章可能有点长，各种集合的实现原理我用自己的理解去解释了，配合源码食用更佳。

一、Java集合框架简述

简介：上古时期（Java 2之前） Java 就提供的数据操作类：Dictionary、Vector、Stack 等，但是它们存在着效率较低、缺少统一的主题的问题。为了解决这些问题，Java 重新进行了设计，就是现在的 Java集合框架。

java 集合框架（图片来自网络）

从上图可以看出，Java 集合框架主要包含三个方面：

• 迭代器（Iterator）：提供一种方法访问一个容器（container）对象中各个元素，而又不需暴露该对象的内部细节。
• 集合（Collection）：用来储存元素集合，列表等。
  Collection 包括 List、Set 和 Queue。这些抽象是为了定义通用方法和变量，统一管理抽象和实现类等。常用实现类有 HashSet、LinkedHashSet、ArrayList 等。
• 图（Map）：用于储存键值对。
  Map 包括 AbstractMap 和 SortedMap 等抽象，原理与上面相同。再往下是 HashMap、LinkedHashMap 等具体实现。

二、集合框架的构成

2.1 接口 Iterable

说明：

• 是 Java 集合框架的顶级接口。
• 实现此接口，定义自己的迭代器实现对数据容器的遍历。

Iterable 三个成员方法：

Iterator<T> iterator(); 返回一个迭代器。

void forEach(Consumer<? super T> action)：对内部元素进行遍历，并对元素进行指定的操作

default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

pliterator<T> spliterator() ：创建并返回一个可分割迭代器

default Spliterator<T> spliterator() {
    return Spliterators.spliteratorUnknownSize(iterator(), 0);
}

那么回头看第一个成员方法，返回的是一个迭代器，这个迭代器也是一个接口，里面定义了常用的一些方法：

接口 Iterator ：迭代器

public interface Iterator<E> {
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

• hasNext()：是否存在下一个元素。
• next()：返回下一个元素。
• remove()：移除一个元素（迭代器实现，与 List 的 remove() 不同）。

也就是说，集合框架中几乎所有容器都实现了 Iterable，通过它们的 iterator() 方法获取自己定义的实现了 Iterator 的迭代器。

举个栗子：

public class IterableTest {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next());
        }
    }
    
}

比较简单，首先调用 list.iterator() 获取 Iterator 实例，这里的 list 是一个 ArrayList，所以获取的就是 ArrayList 的迭代器实现。
那么看一下 ArrayList 的迭代器是怎样的：

ArrayList # iterator()方法 和 内部迭代器 Itr

public Iterator<E> iterator() {
        return new Itr();
    }

private class Itr implements Iterator<E> {
    protected int limit = ArrayList.this.size;

    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor < limit;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        ...
        return (E) elementData[lastRet = i];
    }

    public void remove() {
            ...
        try {
            ArrayList.this.remove(lastRet);
            ...
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        ...
    }
}

可以看到 ArrayList 的 iterator() 创建自定义迭代器 Itr，Itr 是一个 Iterator 实现，实现了 hasNext()、next() 等主要方法。

上面遍历 ArrayList 的小栗子就是通过调用它的迭代器相关方法来实现的。

特别注意：

你可能注意到了，在描述 Iterator 的 remove() 方法时特意加了括号表面与 List 的 remove() 方法的不同。

那么在使用迭代器进行遍历需要删除元素时需要调用迭代器的 remove() 方法，调用 list 的 remove() 会造成并行修改异常(ConcurrentModificationException)。

错误示范：

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
    String s = iterator.next();
    if(s.equals("b")){
        list.remove(s);
    }
}

正确写法应为：

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
    String s = iterator.next();
    if(s.equals("b")){
        iterator.remove();
    }
}

自己实现迭代器：

如果我们想自己写一个集合并使用迭代器来遍历的话，可以这样写：

public class MyList<E> implements Iterable<E> {

    @Override
    public Iterator<E> iterator() {
        return new MyIterator();
    }

    private class MyIterator implements Iterator<E>{

        @Override
        public boolean hasNext() {
            return false;
        }

        @Override
        public E next() {
            return null;
        }

        @Override
        public void remove() {
        }
    }
}

2.2 接口 Collection

Collection 接口包含的方法，AS 找到这个类，快捷键 Ctrl + O：

Collection 接口方法.png

可见 Collection 定义的这些方法有一些是我们经常用到的，比如 add() 添加元素，clear() 删除所有元素。

正是因为 Collection 定义了这些接口，所有的实现类都受到该接口的管理。这里是接口的一个功能的体现： 定义一个规范（协议），这样做的好处是 Collection 无需知道子类是如何实现的，而且扩展性高、解耦。

接口的三大作用：实现多继承、定义一个规范（协议），用于回调。

先看图片的左边部分：

AbstractCollection：实现了大部分的集合接口。

2.2.1 接口 List extends Collection

List

特点：

• List 继承了 Collection，它定义一个 允许重复的有序集合。
• 因为是有序集合，所以查找元素效率高。
• 同时因为删除和插入数据会引起其它元素位置改变，所以删除和插入数据效率低。

从实现方法来看，List 增加了允许在指定位置，也就是下标操作元素的功能。同时增加了 ListIterator 迭代器，它是迭代器接口 Iterator 的子类，主要用于定义双向遍历的功能，具体由子类实现。

AbstractList extends AbstractCollection implements List：继承于AbstractCollection 并且实现了大部分List接口，抽象类。

AbstractSequentialList<E> extends AbstractList<E>：AbstractSequentialList 继承 AbstractList，也是一个抽象类，用于提供了对元素链式访问而不是随机访问。

ArrayList

ArrayList

特点：

• 数组实现，大小可变。
• 根据下标获取元素，随机访问和遍历元素时提供更好的性能。新增和移除元素时效率较低。
• 非同步。

ArrayList 继承了 AbstractList 且实现 List，此外还实现了 Serializable，说明它支持序列化，可用于传输和储存相关。下面记录 ArrayList 常用方法的实现：

ArrayList # add()：添加元素

//1.定义 Object 数组
transient Object[] elementData;

public boolean add(E e) {
    //2.确定和记录数组容量
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //5.将新元素添加到新数组
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 3.确定容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //4.复制原有数据到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

看注释序号：

1. 定义 Object 数组：定义这个数组用于储存 ArrayList 中的数据，transient 修饰的变量不参与序列化，但是 ArrayList 实际使用时数据是可以进行序列化的。原因可以参考下面：

用transient修饰的成员变量不能序列化，为什么ArrayList集合可以实现序列化

也就是说 ArrayList 提供了自己的 writeObject() 方法所以可以进行序列化，但是为什么不直接使用 Object[] elementData呢？原因是 ArrayList 是动态数组可以自增长容量，但是如果设定了数组容量是 100，而实际只放了一个元素，那么默认序列化后就会生成 99 个 null 元素，这明显是没必要的。所以 ArrayList 就提供了自己的序列化方法 writeObject() 在序列化时只遍历实际元素，这样就避免了指定长度生成无用元素的弊端。

以上答案参考：

ArrayList如何实现序列化？

2. 确定和记录数组容量：ensureCapacityInternal()和ensureCapacityInternal() 经过计算得出要创建的数组大小，这个容量用于创建新数组。
3. 新的容量为旧的容量加上它的一半，也就是说每次扩容会增加原来的 50%。
   *这里的 ">>" 是移位预算符，表示二进制的向右移动一位，获得的结果是原来的一半，反之则是原来的一倍。比如：4>>1 = 2。那么 4<<1 = 8。
4. 复制原有数据到新数组：利用 copyOf() 方法创建一个新数组，且容量已确定，同时将原有数据复制给新的数组。
5. 将新元素添加到新数组：elementData[size++] = e; 实现了将新元素的添加并且下标加一。

除了上面添加元素的方法，其它常用的比如 indexOf() 其实是遍历数组 elementData 中的所有元素并进行对比，如果存在相同元素则返回，反之返回 -1.

ArrayList # 其他主要方法

LinkedList

LinkedList

特点：

• 底层是链表实现。
• 允许有 null（空）元素，主要用于创建链表数据结构。
• LinkedList 是一个双链表，所以在添加和删除数据时比 ArrayList 有更好的性能，但查找效率低。
• 非同步。可使用下列方法实现同步：

Listlist=Collections.synchronizedList(newLinkedList(...));

了解关于链表可参考我另一篇笔记：

Java 数据结构了解一下

属性：LinkedList 有三个成员变量：

int size = 0; // LinkedList 长度
Node<E> first; // 首节点
Node<E> last; // 尾结点

方法：挑几个重要的方法记录

LinkedList # add(E e)：添加元素

public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

直接将新增的元素放到链表的最后面，并将 LinkedList 长度加 1，修改的次数（modCount）加1。

LinkedList # add(int index, E element)：添加元素到指定位置

public void add(int index, E element) {
    // 1. 检测 index 是否合法
    checkPositionIndex(index);

    // 2. 判断元素插入位置
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    // 3. 插入到当前元素之前
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

1. 首先进行检测，查看 index 是否大于等于 0 和 小于等于数组长度，如果不合法则抛出（这里代码比较简单，省略掉了）。
2. 进行判断，如果插入到末尾，直接调用刚才也用到的 linkLast() 方法就好。反之调用 linkBefore() 把要插入的元素放到下标元素之前。
3. 如果下标元素的前一个元素为空，则说明下标元素已经在队首了，因为之前已经把下标元素的前元素指向新元素，所以直接把新元素放到队首即可。最后进行 LinkedList 的长度（size）和修改次数（modCount）的增长。

LinkedList # get(int index)：根据下标获取元素，该方法是通过遍历来获取的

public E get(int index) {
    // 1.判断
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // 2. index 和链表长度的一半进行对比
    if (index < (size >> 1)) { //2.1 小于一半
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {//2.2 大于一半
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

1. 依旧是判断下标合法性。
2. 下标和数组长度一半进行判断。因为双链表的特性，所以不需要进行全部元素的遍历。
   2.1 如果 index 小于链表长度的一半，只需遍历链表的前半部分，遍历到第 index-1 个元素的下一个元素就是需要的元素。
   2.2 如果 index 大于链表的一半，遍历后半部分，拿前一个结点即可。

LinkedList # remove(int index)：根据下标移除元素，移除的过程就是重新指向和值置空的过程：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    // 1. 判断是否是首元素
    if (prev == null) {
        first = next;
    } else {// 1.1 不是首元素
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    // 2.当前元素的值置空
    x.item = null;
    size--;
    modCount++;
    return element;
}

首先依旧判断要移除的元素 item 是否合法。

1. 如果当前元素的前一个元素为 null，说明它是首元素。直接将首元素由下一个元素覆盖，就完成了移除过程。
   1.1 不是首元素则由下一个元素覆盖当前元素，并把 x 的一个元素置空。因为 x 已经被替换了，新来的有自己的 prev，所以也无需保存 x 的 prev 了。
2. 把要移除的元素的值置空，然后长度减 1，修改次数加 1。

LinkedList # 其他主要方法

Vector

Vector

特点：

• 同步：基本所有 public 方法或者其具体操作都添加同步关键字 synchronized。
• 效率较低：因为基本所有方法都是同步的，所以会造成性能损失。但其效率问题不止是因为这一个原因。
• 不推荐使用（...）：可使用 Collections 的 synchronizedList 方法同步 ArrayList 来替代。

Stack extends Vector

继承 Vector 实现的栈。

主要方法有三：

• push(E item)：添加元素。
• peek()：返回栈顶元素，不移除。
• pop()：返回栈顶元素并移除。

栈的实现方式也有很多，参考笔记里面有关栈的记录：

Java 数据结构了解一下

2.2.2 接口 Set extends Collection

Set

Set 集合三大特征：确定性、互斥性、无序性。大部分实现此接口的集合都具有此特性。

特点：

• 强调元素无序性，但是不可重复，重复的元素会被覆盖掉。
• 检索元素效率较低，插入和删除效率高且不会引起元素位置改变。

抽象类 AbstractSet

继承了 AbstractCollection，实现了 Set 的大部分接口。这个抽象类就是为了方便扩展而存在的。

HashSet

HashSet

特点：

• 底层实现是 HashMap。
• 不允许出现重复元素，且不保证顺序。因为它的数据存储是用 HashMap 实现的。
• 允许包含值为 null 的元素，但最多只能一个。

HashSet # add(E e)

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

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

这里涉及到 HashMap 的特性：map 储存时如果当前 map 没有相同的 key，则返回 null。
也就是说只有当新添加的值 e 为新的 key 时，才会返回 null，从而判定成功使 Set 加入这个值。
所以，当 e 为 null 时也可以存进 map（HashMap key、value 均可以为 null），但是只能存一个 null，多了添加时会返回 false 存不进去。

HashSet # remove(Object o)

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

remove 的实现也比较简单，调用内部 map 的 remove() 方法。返回的是被移除的 map 的值（猜的），如果该值与储存的 PRESENT 相同则表明从 Set 移除成功。

HashSet 遍历

public static void main(String[] args) {
    Set<String> set = new HashSet<String>();

    set.add("aaa");
    set.add("bbb");
    set.add("ccc");
    set.add("ccc"); //故意加一个相同元素，遍历出来确实没它。

    //遍历
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    //或者这样
    for (String s:set) {
        System.out.println(s);
    }
}

LinkedHashSet

LinkedHashSet

• 底层是 LinkedHashMap 实现。
• 继承 HashSet，但是是链表实现，所以可以保证元素顺序。
• 有序，允许为 null。
• 非线程安全，底层操作通过 LinkedHashMap 实现。

HashSet 构造函数

public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

HashSet 调用了父类 HashSet 的构造函数：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

1. 第一个参数 initialCapacity 表示初始容量，可以看到默认的 LinkedHashSet 初始容易为 16。
2. 第二个参数 loadFactor 表示装载因子。比如这个值为 0.5，则每次容量达到一半时进行扩容（默认 16 达到 8 扩容为 32）。那么当这个值为 0.75，当容量达到当前最大容量的 75% 时进行扩容。
   为啥是 0.75 呢？哈哈，想笑。

HashMap的loadFactor为什么是0.75？

3. 第三个参数作为标记与 HashSet 构造方法区分。

TreeSet

TreeSet

特点：

• 基于 TreeMap 实现的有序集合。
• 最开始的图上有写 TreeMap 是继承 SortedSet 的，但是我在 JDK1.8 的源码中看到并没有。

TreeSet 无参构造函数

public TreeSet() {
    this(new TreeMap<E,Object>());
}

TreeSet 主要方法

2.3 接口 Queue extends Collection

Queue

Queue 主要方法：

2.3.1 接口 Deque extends Queue

Deque

特点：

• 双端队列，支持从两个端点检索和插入元素。

可以看出，Deque 在 Queue 的基础上添加了针对队首和队尾的一些操作。

Deque 的具体实现

Deque 的直接实现有 ArrayDeque和LinkedList，它们共同特点是非阻塞，非线程安全。

ArrayDeque

特点：

• 由 Object[] 来维护数据，也就是数组实现。
• 在两端增删元素较为高效。
• 总体比 LinkedList 要更优越。

LinkedList

上面有聊到过 LinkedList 的特点，所以这里注重和 ArrayDeque 对比。

特点：

• 链表实现，实现了 Deque 需要有获取头和尾的功能，所以是一个双端链表。
• 在两端增删元素效率较低，因为需要创建和删除相关结点。
• 实现了 List 接口的所有操作，较为灵活。

Deque 的阻塞实现有 BlockingQueue 接口和五个阻塞队列类，阻塞队列的特点是不是立即从队列添加或删除元素，线程执行操作阻塞直到有空间或元素可用。

阻塞队列的五个实现类：

• ArrayBlockingQueue：一个由数组支持的有界队列。
• LinkedBlockingQueue：一个由链接节点支持的可选有界队列。
• PriorityBlockingQueue：一个由优先级堆支持的无界优先级队列。
• DelayQueue：一个由优先级堆支持的、基于时间的调度队列。
• SynchronousQueue：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

那么它们是怎么实现阻塞的呢，就选第一个实现类 ArrayBlockingQueue 的添加元素方法来看一下：

ArrayBlockingQueue # offer(E e)

public boolean offer(E e) {
    Objects.requireNonNull(e);
    // 1.获取 ReentrantLock 
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        if (count == items.length)
            return false;
        else {
            // 2.进行插入数据的操作
            enqueue(e);
            return true;
        }
    } finally {
        // 3.释放锁
        lock.unlock();
    }
}

根据注释 1 2 3 来看，ArrayBlockingQueue 的添加元素的方法使用了 ReentrantLock 重入锁，满足一定条件后执行数据插入操作，最后再释放锁。其它主要方法也都有用到重入锁，所以说它是一个阻塞队列。

其它实现了 BlockingQueue 几个阻塞队列基本都是通过加锁的方式来实现阻塞的，但其中的具体实现和锁的功能和方式可能不同，暂不深究吧。

java并发编程 之 Queue的一些总结

那么有关 List、Set 和 Queue 的内容先到这里，下篇记录 Map 相关和总结。

Java - 集合框架完全解析
Java 集合框架