集合

Collection

List

ArrayList

使用数组存储，当数组长度不够时，会构造一个新数组，长度为原数组的2倍，然后将原数组内容copy到新数组。

• 数组存储关键代码

  /**
  * Shared empty array instance used for empty instances.
  */
  private static final Object[] EMPTY_ELEMENTDATA = {};

• 扩容关键代码

  /**
   * Increases the capacity to ensure that it can hold at least the
   * number of elements specified by the minimum capacity argument.
   *
   * @param minCapacity the desired minimum capacity
   */
  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);
  }

Vector

vector与ArrayList方法一致，只是在对数组操作的方法上加入了synchronized 从而保证线程安全。

• 线程安全关键代码

/**
     * Appends the specified element to the end of this Vector.
     *
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     */
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

LinkedList

使用链表存储，默认add方法在最后端存储。

• LinkedList 数据结构

private static class Node<E> {
    E item;
    Node&lt;E&gt; next;
    Node&lt;E&gt; prev;

    Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Set

HashSet

Hash的数据存储在HashMap中的key中，值都是Object对象，从而保证了数据不可重复。

• HashSet数据结构

    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

LinkedHashSet

Map

HashMap

采用“数组+链表”形式存储，下标使用了key的hashcode，当hashcide发生碰撞时则在数组后面形成链表，在链表过长时，使用红黑树优化索引

LinkedHashMap

存储原理与HashMap基本一致，LinkedHashMap的Entry加入了next，从而保证了LinkedHashMap 的有序结构

• next 关键代码

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        ......
    }

Hashtable

Hashtable 在操作的方法上添加了synchronized 保证线程安全，并且校验了value为空的情况。

关键代码

    /**
     * Maps the specified <code>key</code> to the specified
     * <code>value</code> in this hashtable. Neither the key nor the
     * value can be <code>null</code>. <p>
     *
     * The value can be retrieved by calling the <code>get</code> method
     * with a key that is equal to the original key.
     *
     * @param      key     the hashtable key
     * @param      value   the value
     * @return     the previous value of the specified key in this hashtable,
     *             or <code>null</code> if it did not have one
     * @exception  NullPointerException  if the key or value is
     *               <code>null</code>
     * @see     Object#equals(Object)
     * @see     #get(Object)
     */
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        ......
    }

TreeMap

TreeMap的key使用红黑树的存储结构，有序结构，当key为引用对象类型时，可以指定排序属性。

Properties

工具类

Arrays

Collections

我们能否让HashMap同步？ HashMap可以通过下面的语句进行同步：

Map m = Collections.synchronizeMap(hashMap);