乐趣区

关于java:Java-List集合解析

jiezi

List 概述

List 汇合的元素以线性形式存储
1. 能够容许反复的对象。
2. 能够插入多个 null 元素。
3. 是一个有序汇合，放弃了每个元素的插入程序，输入的程序就是插入的程序。

List 实现类

ArrayList

ArrayList 底层是用数组实现的存储，Object[] elementData
查问效率高，增删效率低，线程不平安
ArrayList() 提供了三种构造方法。
  ArrayList()：结构一个初始容量为 10 的空列表。

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

  ArrayList(int initialCapacity)：结构具备指定初始容量的空列表。

    public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {
            throw new IllegalArgumentException("Illegal Capacity:"+
                                               initialCapacity);
        }
    }

  ArrayList(Collection c)：结构一个蕴含指定汇合的元素的列表，依照它们由汇合的迭代器返回的程序。

    public ArrayList(Collection<? extends E> c) {elementData = c.toArray();
        if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList 要害源码解析

add()办法
    public boolean add(E e) {ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 如果 minCapacity 大于 elementData 的长度，则进行扩容解决
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 容量默认扩充 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 数组容量存在最大值
            newCapacity = hugeCapacity(minCapacity);
        
        // 数组复制
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
  1. int newCapacity = oldCapacity + (oldCapacity >> 1);每次扩容是原数组的 1.5 倍
  2. elementData = Arrays.copyOf(elementData, newCapacity);创立一个长度是原数组容量 1.5 倍的新的数组，将原数组的数据复制到新数组中，elementData 指向新的数组地址
  3. 扩容也是无限的，存在最大值 Integer.MAX_VALUE，然而在某些虚拟机上数组容量达到 MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8 时会内存溢出

4. 最重要的一个点：如果咱们能够当时预计出数据量，那么最好给 ArrayList 一个初始值，这样能够缩小其扩容次数，从而省掉很屡次内存申请和数据搬移操作。（不指定初始值，至多会执行一次 grow 办法，用于初始化外部数组）。

remove()办法
    public E remove(int index) {rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

System.arraycopy(elementData, index+1, elementData, index,numMoved); 复制一个 index+ 1 开始到最初的数组，而后把它放到 index 开始的地位

ArrayList 为什么是线程不平安的

add()办法是非原子操作
1. 多个线程进行 add 操作时可能会导致 elementData 数组越界
2. 多线程环境下执行时，可能就会产生一个线程的值笼罩另一个线程增加的值

Vector

在 ArrayList 的所有办法加了 synchronized 关键字，线程平安。

LinkedList

ArrayList 底层是用双向链表实现的存储，
查问效率低，增删效率高，线程不平安

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 有一个空参构造函数和一个汇合参数构造函数：


    public LinkedList() {}

    public LinkedList(Collection<? extends E> c) {this();
        addAll(c);
    }

LinkedList 要害源码解析

get()办法：

    public E get(int index) {checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {// assert isElementIndex(index);

        // 查找地位 index 如果小于节点数量的一半 (size>>1 示意把 size 右移 1 位，相当于 size/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;
        }
    }

LinkedList 为什么是线程不平安的

add()办法是非原子操作
多个线程进行 add 操作时可能会节点笼罩

Stack

Stack 继承自 Vector，底层也是用数组实现的存储，线程平安，恪守 LIFO（后进先出）的操作程序

Stack 要害源码解析

    // 入栈，增加一个元素到数组开端
    public E push(E item) {addElement(item);

        return item;
    }
    
    // 出栈，删除数组最初一个元素并返回
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    // 获取最初一个元素，不删除
    public synchronized E peek() {int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

参考：
一篇文章带您读懂 List 汇合（源码剖析）

退出移动版