Java常用容器类盘点

Posted on | Edited on | In | Views: | Views:

ArrayList

底层实现

ArrayList的底层实现为Object[]数组。Add和Remove操作多使用System.arrayCopy()方法。随机访问效率高，插入和删除效率差。

线程安全性

非线程安全

扩容机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * The minimum amount by which the capacity of an ArrayList will increase.
 * This tuning parameter controls a time-space tradeoff. This value (12)
 * gives empirically good results and is arguably consistent with the
 * RI's specified default initial capacity of 10: instead of 10, we start
 * with 0 (sans allocation) and jump to 12.
 */
private static final int MIN_CAPACITY_INCREMENT = 12;

/**
 * This method controls the growth of ArrayList capacities.  It represents
 * a time-space tradeoff: we don't want to grow lists too frequently
 * (which wastes time and fragments storage), but we don't want to waste
 * too much space in unused excess capacity.
 *
 * NOTE: This method is inlined into {@link #add(Object)} for performance.
 * If you change the method, change it there too!
 */
private static int newCapacity(int currentCapacity) {
    int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
            MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
    return currentCapacity + increment;
}

LinkedList

底层实现

LinkedList的底层实现为双向链表。存在一个voidLink节点来连接表头和表尾。在访问某一节点的过程中，如果location小于size / 2，则从表头开始遍历，否则从表尾开始遍历。插入和删除效率高，随机访问效率差。

线程安全性

非线程安全

扩容机制

直接增加元素

CopyOnWriteArrayList

底层实现

CopyOnWriteArrayList的底层实现为Object[]数组。Add和Remove操作多使用System.arrayCopy()方法

线程安全性

线程安全，通过写时拷贝实现，保证最终一致性。在进行写操作时通过synchronized加锁，先拷贝一个副本在副本中执行操作，最后获取副本的引用。以add方法为例

1
2
3
4
5
6
7
public synchronized boolean add(E e) {
    Object[] newElements = new Object[elements.length + 1];
    System.arraycopy(elements, 0, newElements, 0, elements.length);
    newElements[elements.length] = e;
    elements = newElements;
    return true;
}

写操作不保证立刻生效，有可能在执行写操作时读到之前的值。

扩容机制

直接增加元素

Vector

底层实现

Vector的底层实现为Object[]数组。Add和Remove操作多使用System.arrayCopy()方法

线程安全性

线程安全，通过synchronized代码块实现。由于大量操作使用synchronized，性能受到影响。

扩容机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * JIT optimization
 */
private void growByOne() {
    int adding = 0;
    if (capacityIncrement <= 0) {
        if ((adding = elementData.length) == 0) {
            adding = 1;
        }
    } else {
        adding = capacityIncrement;
    }

    E[] newData = newElementArray(elementData.length + adding);
    System.arraycopy(elementData, 0, newData, 0, elementCount);
    elementData = newData;
}

ArrayMap

底层实现

ArrayMap底层实现为两个数组，int[] mHashes和Object[] mArray。其中mHashes存储key.hashCode()，mArray存储key和value。当插入一个键值对时，会分配一个index。

1
2
3
4
mHashes[index] = key.hashCode();
index <<= 1;
mArray[index] = key;
mArray[index+1] = value;

查找元素时，得到key的hashCode，使用二分法从mHashes中找到对应的index。然后再到mArray中获取相应的key和value。

删除操作有多个数组的copy操作，性能差。

线程安全性

非线程安全

扩容机制

通过allocArrays和freeArrays动态分配空间

HashMap

底层实现

HashMap的底层实现为HashEntry[]数组，每个HashEntry是一个单链表。是哈希表的拉链法实现。通过hashCode和equal方法共同找到一个元素。

线程安全性

非线程安全

扩容机制

首先HashMap存在容量限制

1
2
3
4
5
6
7
8
9
10
/**
 * Min capacity (other than zero) for a HashMap. Must be a power of two
 * greater than 1 (and less than 1 << 30).
 */
private static final int MINIMUM_CAPACITY = 4;

/**
 * Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY.
 */
private static final int MAXIMUM_CAPACITY = 1 << 30;

其次存在一个load factor

1
2
3
4
5
6
7
8
9
10
11
/**
 * The default load factor. Note that this implementation ignores the
 * load factor, but cannot do away with it entirely because it's
 * mentioned in the API.
 *
 * <p>Note that this constant has no impact on the behavior of the program,
 * but it is emitted as part of the serialized form. The load factor of
 * .75 is hardwired into the program, which uses cheap shifts in place of
 * expensive division.
 */
static final float DEFAULT_LOAD_FACTOR = .75F;

以及threshold

1
2
3
4
5
6
7
/**
 * The table is rehashed when its size exceeds this threshold.
 * The value of this field is generally .75 * capacity, except when
 * the capacity is zero, as described in the EMPTY_TABLE declaration
 * above.
 */
private transient int threshold;

这些成员都可以从构造函数中传入。从注释中可以看出，threshold = loadFactor * capacity，当HashMap容量超过threshold时，会进行doubleCapacity的扩容操作。由于哈希表在容量改变时需要进行Rehash操作，会耗费大量的时间。所以应该尽量避免频繁的扩容操作。

LinkedHashMap

底层实现

与HashMap类似，不过HashEntry[]数组改为用LinkedEntry为节点的双向链表实现，保存了插入的顺序。性能表现可以参考LinkedList和ArrayList。与HashMap是继承关系。

线程安全性

非线程安全

扩容机制

直接增加元素

TreeMap

底层实现

TreeMap底层实现为红黑树。元素是有序的，不支持空元素。

线程安全性

非线程安全

扩容机制

直接增加元素

HashTable

底层实现

HashTable底层实现为HashTableEntry[]数组。不支持空元素。HashTable是遗留类，已经不推荐使用，在不需要线程安全的场景可以使用HashMap，在线程安全的场景可以使用ConcurrentHashMap。

线程安全性

线程安全，通过synchronized代码块实现。由于大量操作使用synchronized，性能受到影响。

扩容机制

扩容机制同HashMap

ArraySet

底层实现

同ArrayMap，在插入操作时不允许重复元素。

线程安全性

非线程安全

扩容机制

同ArrayMap

HashSet

底层实现

HashSet底层实现为HashMap<E, HashSet<E>>，十分巧妙，增删改查等基础操作只需要调用HashMap中的相应方法即可。

线程安全性

非线程安全

扩容机制

同HashMap

TreeSet

底层实现

TreeSet底层实现为NavigableMap<E, Object>。思想与HashSet类似。

线程安全性

非线程安全

扩容机制

直接增加元素

CopyOnWriteArraySet

底层实现

CopyOnWriteArraySet的底层实现为CopyOnWriteArrayList。增删改查等基础操作只需要调用CopyOnWriteArrayList中的相应方法即可。注意add操作调用的是addAllAbsent防止元素重复。

线程安全性

线程安全，原理同CopyOnWriteArrayList

扩容机制

同CopyOnWriteArrayList