Java常用数据结构分析

总结一下常用的数据结，以上是它们大概的继承关系。
- List：列表
- Map：key-value映射关系
- Set：集合中元素唯一

Collection 
├─List
│  ├─ArrayList
│  ├─LinkedList
│  ├─Vector
│ 
├─Set
│  ├─HashSet
│  ├─TreeSet

Map
├─HashMap
├─TreeMap
├─LinkedHashMap

List

ArrayList
使用数组进行缓存，好处的遍历快，缺点的插入/删除中间元素比较慢

//数据集合
private transient Object[] elementData;

中间插入分析

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //需要copy（size-n）个单位，时间消耗比较长
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

当数组空间不足时，会调用Arrays.copyOf进行扩展

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

LinkedList使用双链表的结构

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个方法，中间插入因为不需要coye数组，所以比较快

 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比较经过上面的分析，中间插入元素LinkedList较好，因为 ArrayList 使用数组，是连续的内存，所以遍历会比较快。

Vector的数据结果和实现跟ArrayList差不多，主要的区别是操作数据的方法都加了synchronized关键字修饰，它是线程安全的，也牺牲了些性能，慎用。

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使用数组和单链表的形式保存数据

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

接下来看一下具体的保存实现

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        //先计算获取hash
        int hash = hash(key);
        //通过hash计算数组的索引，(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相等时，不插入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的扩展规则的是：当前元素size大于threshold时，将2倍扩展，所有元素将重新计算索引值在插入到新的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的值的当前table数组长度*loadFactor，loadFactor可以设置，默认0.75
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

LinkedHashMap继承了HashMap，数据结果和HashMap一样，但增加了双向列表的结果，用来记录插入的顺序，结果如下

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

双向链表的结果为：E0-E1-E2-…-header

TreeMap使用红-黑树结果，具有元素排序功能

 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默认使用TreeMap的key来保存元素，具有排序功能

 public TreeSet() {
        this(new TreeMap<E,Object>());
    }

小提示

在大多数据结果使用modCount来记录操作数，目的是为了检验数据安全，比如在多线程中使用不当就会抛出异常ConcurrentModificationException，比如遍历或者序列化的时候

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{

        //保存当前操作数
        int expectedModCount = modCount;
        s.defaultWriteObject();

        clone()
        s.writeInt(size);

        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        //对比操作数，不同就抛出异常，
        //在进入其他线程前做好能copy一份数据，使用副本数据比较安全
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }