Amarone's Blog

java 集合容器

collection

Collection 是最基本的集合接口，一个 Collection 代表一组 Object，即 Collection 的元素, Java不提供直接继承自Collection的类，只提供继承于的子接口(如List和set)。

Collection 接口存储一组不唯一，无序的对象。

list

List接口是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(元素在List中位置，类似于数组的下标)来访问List中的元素，第一个元素的索引为 0，而且允许有相同的元素。

List 接口存储一组不唯一，有序（插入顺序）的对象。

线性列表存储方式，长度动态可变

ArrayList

可以仔细观察一下ArrayList的构造方法

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);
        }
    }

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

其底层就是一个new Object[initialCapacity]，object类型的数组

数组与其他容器区别有三方面：效率、类型和保存基本数据的能力。数组是一种效率最高的存储和随机访问对象引用序列的方式，就是一个简单地线性程序，这使得元素访问非常快速，但是他的大小是固定的并且的生命周期不可变。

ArrayList通过创建一个新的实例，然后将就得实例中所有的引用迁到新的实例中，从而实现空间的自动分配，这种弹性需要开销，所以他的效率比数组低很多。可以看看ArrayList的新增方法

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
 }

// 确保内部的容纳能力
private void ensureCapacityInternal(int minCapacity) {
// elementData 为数组中的元素
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算容积
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果所有元素 为 一个空的数组    
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 返回 DEFAULT_CAPACITY 默认为10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return 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;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

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

LinkedList

LinkedList在执行插入和移除比ArrayList更高效，但是在随机访问方面要逊色一些

泛型

set

Set 具有与 Collection 完全一样的接口，只是行为上不同，Set 不保存重复的元素。

Set 接口存储一组唯一，无序的对象。

map

key->Map 存储方式，长度可变