集合

​ Java是一门面向对象的语言,自然少不了要处理对象,如果需要处理多个对象不可避免的需要使用一个容器(集合)来装载(其实对象的本质也是装在数据的容器)。

​ 之前学过一种可以存储基本数据类型和对象的容器为数组,但是数组有个缺点是,一旦创建必须指定长度或者指定数组存储的内容其长度是不可变的,所以变衍生出另一种可以存储对象的容器便是集合,其长度可变,集合也提供了丰富的API方便我们操作数据,但集合也有个缺点,集合只能存储引用数据类型,但是每个基本数据类型都有其对应包装类,并且有自动拆装箱机制后影响不大。

​ 同时由于我们对数据存储的方式或元素有要求,又分为多种不同数据结构的集合,单其本质还是存储数据,Java中将集合的共性抽取出来提供了一个接口Collection,其中常用的实现类

​ RandomAccess接口 代表可以随机访问:通过索引顺序访问

image-20200627161804909

image-20200627163709985

接口中定义了一些基础的方法

image-20200627180024559

image-20200627180201410

迭代器

​ Collection接口的父接口是Iterable,其中的iterator()方法会返回一个迭代器Iterator,迭代器中有三个常用的方法

image-20200627180809007

// Iterator也是一个接口,不同的集合都有不同的实现
public interface Iterator<E> {}

其中forEachRemaining()方法是java8新增,可以使用lambda表达式的方式调用方法,其内部实现还是依靠另外两个方法

hasNext():是否有下一个元素,如果有返回true否则false

next():获取下一个元素并向后移动一个位置(如果没有元素会抛出NoSuchElementException异常)

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

使用迭代器时需要注意的是不可以在迭代期间对集合做改变,以ArrayList内部实现的迭代器为例

ArrayList<Integer> integers = new ArrayList<>();
//        HashSet<Integer> integers = new HashSet<>();
integers.add(1);
integers.add(2);
integers.add(3);
Iterator<Integer> iterator = integers.iterator();
// 使用foreach方式同样会出现以下错误,因为foreach本质上也是迭代器
while (iterator.hasNext()){
    System.out.println(iterator.next());
    if (iterator.next() == 2){
        integers.add(4);
    }
}

// 会报并发修改异常
1
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
    at xyz.taoqz.chapter6.demo.MyTest.main(MyTest.java:19)

Java中认为集合在迭代时不应该对其做修改,可以看看ArrayList内部的迭代器的实现

private class Itr implements Iterator<E> {
    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 != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    ....
}

其中modCount是集合内部维护的一个变量,用来记录集合发生变化的次数

protected transient int modCount = 0;

​ 在迭代器中将其赋值给了迭代器中的expectedModCount,在每一次调用next()时都会检查该变量是否和集合内部的变量一致,如果不一致抛出ConcurrentModificationException()异常,但其内部又实现了remove方法,可以使用迭代器的方法对集合进行删除操作,其中调用了集合内部的remove()

ArrayList.this.remove(lastRet);

并且对维护的变量进行了重新赋值,所以并不会抛出并发修改异常

expectedModCount = modCount;

如果想添加元素可以使用普通for循环,或者在使用迭代器时添加后即刻停止迭代

ArrayList<Integer> integers = new ArrayList<>();
integers.add(1);
integers.add(1);
integers.add(3);

// 需要注意的是,每次修改集合中的元素,在for循环中integers.size()便会重新获取
// 而变量i则会根据规则走,所以需要注意在修改或添加时避免漏掉数据
for (int i = 0; i < integers.size(); i++) {
    if (integers.get(i).equals(1)){
        // 会添加到尾部
        integers.add(4);
        //                integers.remove(i);
        // 由于删除时元素会往前移动,所以需要将i变量 -1避免漏掉数据(也可以选择倒叙遍历进行删除)
        //                i--;
    }
}

Iterator<Integer> iterator = integers.iterator();
while (iterator.hasNext()){
    if (iterator.next().equals(2)){
        integers.add(4);
        break;
    }
}

​ 在ArrayList内部有一个实现了Iterator接口的内部类,除了以上一种还有一个就是ListIterator接口的实现类,同时又继承了Iterator接口的实现类,有更加丰富的功能(LinkedList和Vector也有)

ArrayList<Integer> integers = new ArrayList<>();
integers.add(1);
integers.add(2);
integers.add(3);

//        ListIterator<Integer> iterator = integers.listIterator();
// 可以指定索引 正向:从哪个索引开始迭代 反向: 从倒数第几个开始遍历
// 他们会共用同一份cursor变量
ListIterator<Integer> iterator = integers.listIterator(1);
while (iterator.hasNext()){
    // 还可以获取每次的索引
    //            System.out.println(iterator.next()+"   "+iterator.nextIndex());
    if (iterator.next().equals(2)){
        // 修改指定索引的值
        //                iterator.set(4);
        // 添加到指定索引后
        iterator.add(5);
    }
}
System.out.println(integers);

System.out.println("=============");

while (iterator.hasPrevious()){
    System.out.println(iterator.previous()+"  "+iterator.previousIndex());
}

功能类似的Enumeration接口

Vector是在Java早期的集合和ArrayList作用基本一致,但是Vector的方法都是线程同步的,而ArrayList不是

Vector<Integer> vector = new Vector<>();
vector.add(3);
vector.add(1);
vector.add(2);

Enumeration<Integer> elements = vector.elements();
while (elements.hasMoreElements()){
    System.out.println(elements.nextElement());
}

// 源码
public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;

        public boolean hasMoreElements() {
            return count < elementCount;
        }

        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}

List集合

​ Collection中主要的集合有两种List和Set,List集合的特点是有序(存储和去除的顺序一致)可重复

​ 前面做例子主用的都是ArrayList,底层是数组结构,线程不安全

​ LinkedList : 底层是链表结构,线程不安全

​ Vector : 底层是数组结构,线程安全

ArrayList

源码分析

// 默认的初始容量 (再扩容时才会使用到)
private static final int DEFAULT_CAPACITY = 10;
// 当集合的长度被指定为0时返回的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认空参构造时返回的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 实际存储元素的数组,ArrayList的底层就是数组
transient Object[] elementData; 
// 实际储存元素的个数
private int size;

// 指定容量大小的构造
public ArrayList(int initialCapacity) {
    // 构建指定大小的数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
        // 如果指定为0 使用EMPTY_ELEMENTDATA空数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 空参构造使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA作为存储元素的数组使用
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 在尾部添加元素
public boolean add(E e) {
    // 扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // size自增同时为数组赋值
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 如果使用的空参构造,比较默认的容量和参数作比较取较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
// modCount自增,修改次数++
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    // 如果比原来的数组长度大
    if (minCapacity - elementData.length > 0)
        // 调用实际的扩容方法
        grow(minCapacity);
}

// 设置数组最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    // 获取数组现在的长度
    int oldCapacity = elementData.length;
    // 扩大到其自身的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩容后小于参数值,使用参数值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果参数比内部设置的数组最大长度还大,将其设置为Integer的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// System类方法,发方法为本地方法,有c/c++编写,ArrayList的底层全靠其来做动态增长
// src: 原数组 srcPos: 原数组开始索引 dest: 复制至新的数组 destPos: 新数组的索引起始 length: 复制元素个数
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

// 在指定索引位置添加元素
public void add(int index, E element) {
    rangeCheckForAdd(index);
    // 扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 复制数组,并且将指定index位置空出来
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 为空出来的指定索引赋值
    elementData[index] = element;
    // 集合长度加一
    size++;
}
// 检查是否索引越界
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 获取元素的方法
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
// 检查元素是否越界,索引大于等于集合长度抛出异常
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 返回实际元素,如果get参数为负数,由此处抛出索引越界异常
E elementData(int index) {
    return (E) elementData[index];
}

// 修改指定索引上的值,并返回旧值,该方法不会对modCount变量操作
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

// 删除指定索引上的值
public E remove(int index) {
    rangeCheck(index);
    // 删除会修改modCount的值
    modCount++;
    E oldValue = elementData(index);
    // 拷贝数组
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将--size位置上的元素赋值为null同时将size-1 让GC进行垃圾回收
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

//  elementData[--size] = null; 操作是因为System.arraycopy()方法的特性
LinkedList<Integer> integers = new LinkedList<>();
int[]arr = {1,2,3};
System.arraycopy(arr,1,arr,0,2);
System.out.println(Arrays.toString(arr));
// console
[2, 3, 3]

总结

​ ArrayList基于在底层复制数组实现动态扩容,add和remove方法都会对modCount变量做修改所以在使用迭代器时避免使用这两个方法,add的时候会自动扩容但是在remove时不会自动减少容量,如果需要减少容量可以手动调用trimToSize()方法

// 如果实际存储元素数量小于数组长度
// 将数组容量缩小至数组实际存储元素的个数
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

Vector

Vector是jdk1.2的类,其结构和后来的ArrayList一样,但Vector是线程安全的

// 底层也是数组
protected Object[] elementData;
// 扩容追加的个数
protected int capacityIncrement;
// 带有扩容指数的构造
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}
// 添加方法,举例 代表该类是线程安全的
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
// 扩容方法
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 如果不指定capacityIncrement那么默认在原来的基础上扩容1倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList

上面说的ArrayList和Vector底层都是数组结构,而LinkedList底层是链表结构,双向链表,内部类实现为Node

private static class Node<E> {
    // 本节点存储的数据
    E item;
    // 分别记录下一个和上一个节点的位置
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList集合继承图

LinkedList还实现了Queue接口,也提供了很多队列的操作方式

image-20200704162057269

源码解析

transient int size = 0;
// 记录链表的头节点和尾节点,通过这两个节点可以任意操作链表(只有头节点便可满足大部分需求(单向链表))
transient Node<E> first;
transient Node<E> last;

// 分别提供了空参构造和有一个实现了Collection接口的实现类参数的构造
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

public boolean add(E e) {
    linkLast(e);
    return true;
}
// 具体的添加方法,会默认添加到尾部,如果添加时尾部是空的说明是空链表
// 将头和尾指向同一个节点
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++;
}

// 检查添加的索引是否超出链表长度,或者是否是负数
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

// 根据索引查找元素
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果索引小与长度的1/2,从头开始遍历查找,相反从尾部开始遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

// addAll(c),最终会调用
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查索引
    checkPositionIndex(index);
    // 转为数组,拿到数组长度,可以循环添加到链表中
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    // 临时变量
    // pred:上一个节点 succ:下一个节点
    Node<E> pred, succ;
    // 如果添加的位置在尾部,将上一个节点指向last
    if (index == size) {
        succ = null;
        pred = last;
        // 如果指定了索引,通过索引位置查找链表中的元素
        // 找到后确定添加元素所需的前后(上下)节点
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    // 迭代数组,赋值
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果上一个元素等于null,说明last为null,也就是此时的链表是空的,因为add()方法默认添加到尾部,将头部指向用循环创建的第一个节点,否则向后添加
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    // 如果succ为null,说明没有下一个节点,将尾部节点指向循环后的最后一个节点
    // 否则将添加完成后的一段链表中的最后一个节点的下一个节点指向通过node(index)找到的元素节点,将找到的元素节点的上一个节点指向添加后的最后一个节点
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

// get最终调用的node(index),方法,方法返回指定位置的节点匀元素
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 本质个get相同只是切换了指定位置节点保存的元素
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

// 删除指定元素,还有一个删除指定索引位置的元素的方法,本质一样都会调用unlink方法
// 元素为null和元素不为null时分别进行遍历删除,不为null时使用equals判断
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
// 删除节点
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;
    // 如果前一个节点为null,说明此节点为头节点,将头节点更改为该节点的下一个节点
    if (prev == null) {
        first = next;
    } else {
        // 将前一个节点的下一个节点指向本节点的下一个节点
        prev.next = next;
        // 将本节点的上一个节点的引用消除
        x.prev = null;
    }

    // 如果next为null说明此节点为尾节点
    if (next == null) {
        // 将链表的尾节点更换为该节点的上一个节点
        last = prev;
    } else {
        // 将此节点的下一个节点的上一个节点引用指向本节点的上一个节点
        next.prev = prev;
        // 将本节点的下一个节点引用消除
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

ArrayList和LinkedList的使用场景

ArrayList由于采用数组作为数据结构,在进行增删时通过使用数组复制来完成动态的添加与删除,在大量的数据下处理较慢,在增删较多时推荐使用LinkedList

image-20200621203817016

image-20200621203834282

Set集合

Set集合的特点的是元素不可重复

常用子类

HashSet:底层是哈希表结构(是一个元素为链表的数组)

TreeSet:底层是红黑树(是一个自平衡的二叉树),保证元素的排序方式

LinkedHashSet:底层由哈希表和链表组成

Java集合继承图

引自Java核心技术卷I

image-20200621193316284

image-20200621195204437

image-20200621195103536

Copyright © TaoQZ 2019 all right reserved，powered by Gitbook作者联系方式：taoqingzhou@gmail.com 修订时间： 2024-11-19 17:25:43

results matching ""

    No results matching ""

    results matching ""

      No results matching ""