Java常用容器类盘点

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[] mHashesObject[] 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操作,性能差。

线程安全性

非线程安全

扩容机制

通过allocArraysfreeArrays动态分配空间

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