總結(jié)一下常用的數(shù)據(jù)結(jié)，以上是它們大概的繼承關(guān)系。
- List：列表
- Map：key-value映射關(guān)系
- Set：集合中元素唯一
Collection
├─List
│ ├─ArrayList
│ ├─LinkedList
│ ├─Vector
│
├─Set
│ ├─HashSet
│ ├─TreeSet
Map
├─HashMap
├─TreeMap
├─LinkedHashMap
List
ArrayList
使用數(shù)組進(jìn)行緩存，好處的遍歷快，缺點(diǎn)的插入/刪除中間元素比較慢
//數(shù)據(jù)集合
private transient Object[] elementData;
中間插入分析
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//需要copy（size-n）個(gè)單位，時(shí)間消耗比較長
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
當(dāng)數(shù)組空間不足時(shí)，會(huì)調(diào)用Arrays.copyOf進(jìn)行擴(kuò)展
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//一般擴(kuò)展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);
}
LinkedList使用雙鏈表的結(jié)構(gòu)
transient Node<E> first;
transient Node<E> last;
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;
}
}
插入主要有3個(gè)方法，中間插入因?yàn)椴恍枰猚oye數(shù)組，所以比較快
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element.
*/
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++;
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
ArrayList和LinkedList比較經(jīng)過上面的分析，中間插入元素LinkedList較好，因?yàn)?ArrayList 使用數(shù)組，是連續(xù)的內(nèi)存，所以遍歷會(huì)比較快。
Vector的數(shù)據(jù)結(jié)果和實(shí)現(xiàn)跟ArrayList差不多，主要的區(qū)別是操作數(shù)據(jù)的方法都加了synchronized關(guān)鍵字修飾，它是線程安全的，也犧牲了些性能，慎用。
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}
Map
HashMap使用數(shù)組和單鏈表的形式保存數(shù)據(jù)
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
接下來看一下具體的保存實(shí)現(xiàn)
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//先計(jì)算獲取hash
int hash = hash(key);
//通過hash計(jì)算數(shù)組的索引，(hash & (length-1))
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//hash相同或key相等時(shí)，不插入table，替換value，并且返回舊值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//插入
addEntry(hash, key, value, i);
return null;
}
HashMap的擴(kuò)展規(guī)則的是：當(dāng)前元素size大于threshold時(shí)，將2倍擴(kuò)展，所有元素將重新計(jì)算索引值在插入到新的table。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//threshol的值的當(dāng)前table數(shù)組長度*loadFactor，loadFactor可以設(shè)置，默認(rèn)0.75
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
LinkedHashMap繼承了HashMap，數(shù)據(jù)結(jié)果和HashMap一樣，但增加了雙向列表的結(jié)果，用來記錄插入的順序，結(jié)果如下
private transient Entry<K,V> header;
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
}
只要重寫createEntry的
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
//插入到header前面
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
雙向鏈表的結(jié)果為：E0-E1-E2-...-header
TreeMap使用紅-黑樹結(jié)果，具有元素排序功能
private transient Entry<K,V> root = null;
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
}
HashSet使用HashMap來保存對象
private transient HashMap<E,Object> map;
//使用key來保持元素唯一
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
TreeSet默認(rèn)使用TreeMap的key來保存元素，具有排序功能
public TreeSet() {
this(new TreeMap<E,Object>());
}
小提示
在大多數(shù)據(jù)結(jié)果使用modCount來記錄操作數(shù)，目的是為了檢驗(yàn)數(shù)據(jù)安全，比如在多線程中使用不當(dāng)就會(huì)拋出異常ConcurrentModificationException，比如遍歷或者序列化的時(shí)候
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
//保存當(dāng)前操作數(shù)
int expectedModCount = modCount;
s.defaultWriteObject();
clone()
s.writeInt(size);
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
//對比操作數(shù)，不同就拋出異常，
//在進(jìn)入其他線程前做好能copy一份數(shù)據(jù)，使用副本數(shù)據(jù)比較安全
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
