List

Vector

采纳Object数组存储元素

protected Object[] elementData;

Stack

Stack继承了Vector，采纳Object数组存储元素

ArrayList

顾名思义，ArrayList底层采纳数组存储元素

Object[] elementData;

LinkedList

顾名思义，LinkedList底层采纳链表存储元素。通过first和last指针别离指向头元素和尾元素。

/** * Pointer to first node. * Invariant: (first == null && last == null) || *            (first.prev == null && first.item != null) */transient Node<E> first;/** * Pointer to last node. * Invariant: (first == null && last == null) || *            (last.next == null && last.item != null) */transient Node<E> last;

其中Node是LinkedList自定义的动态类，通过next和prev指针别离指向后驱节点和前驱节点。因而LinkedList底层是通过first和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;    }}

CopyOnWriteArrayList

顾名思义，CopyOnWriteArrayList底层是通过Object[] 数组存储数据，提供的构造方法在初始化时主动创立了长度为0的数组。

/** The array, accessed only via getArray/setArray. */private transient volatile Object[] array;/** * Creates an empty list. */public CopyOnWriteArrayList() {    setArray(new Object[0]);}

CopyOnWrite的逻辑大体上都是在插入数据的时候，从新复制一份数组，在新数组中插入新数据，之后将指针指向新的数组。这种模式次要是为了针对“改变操作很少，次要是读操作”的业务。CopyOnWriteArrayList一样，在操作数据时通过ReentrantLock锁住避免并发之后，复制原数组再在新数组中操作数据，最初将指针指向新数组。

  • 相干代码
public E set(int index, E element) {    final ReentrantLock lock = this.lock;    lock.lock();    try {        Object[] elements = getArray();        E oldValue = get(elements, index);        if (oldValue != element) {            int len = elements.length;            Object[] newElements = Arrays.copyOf(elements, len);            newElements[index] = element;            setArray(newElements);        } else {            // Not quite a no-op; ensures volatile write semantics            setArray(elements);        }        return oldValue;    } finally {        lock.unlock();    }}public boolean add(E e) {    final ReentrantLock lock = this.lock;    lock.lock();    try {        Object[] elements = getArray();        int len = elements.length;        Object[] newElements = Arrays.copyOf(elements, len + 1);        newElements[len] = e;        setArray(newElements);        return true;    } finally {        lock.unlock();    }}public E remove(int index) {    final ReentrantLock lock = this.lock;    lock.lock();    try {        Object[] elements = getArray();        int len = elements.length;        E oldValue = get(elements, index);        int numMoved = len - index - 1;        if (numMoved == 0)            setArray(Arrays.copyOf(elements, len - 1));        else {            Object[] newElements = new Object[len - 1];            System.arraycopy(elements, 0, newElements, 0, index);            System.arraycopy(elements, index + 1, newElements, index,                             numMoved);            setArray(newElements);        }        return oldValue;    } finally {        lock.unlock();    }}

Map

HashTable

HashTable底层通过Entry数组存储元素，

private transient Entry<?,?>[] table;
  • 其中Entry类型为HashTable自定义的数据结构，外部记录了元素的hash值，key，value，以及下一节点的指针next。
private static class Entry<K,V> implements Map.Entry<K,V> {    final int hash;    final K key;    V value;    Entry<K,V> next;    protected Entry(int hash, K key, V value, Entry<K,V> next) {        this.hash = hash;        this.key =  key;        this.value = value;        this.next = next;    }    @SuppressWarnings("unchecked")    protected Object clone() {        return new Entry<>(hash, key, value,                              (next==null ? null : (Entry<K,V>) next.clone()));    }    // Map.Entry Ops    public K getKey() {        return key;    }    public V getValue() {        return value;    }    public V setValue(V value) {        if (value == null)            throw new NullPointerException();        V oldValue = this.value;        this.value = value;        return oldValue;    }    public boolean equals(Object o) {        if (!(o instanceof Map.Entry))            return false;        Map.Entry<?,?> e = (Map.Entry<?,?>)o;        return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&           (value==null ? e.getValue()==null : value.equals(e.getValue()));    }    public int hashCode() {        return hash ^ Objects.hashCode(value);    }    public String toString() {        return key.toString()+"="+value.toString();    }}

HashMap

HashMap底层通过 Node数组存储元素

transient Node<K,V>[] table;
  • 其中Node是HashMap自定义的数据结构，外部记录了元素的hash值，key，value，以及下一节点的指针next。
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;    }    public final K getKey()        { return key; }    public final V getValue()      { return value; }    public final String toString() { return key + "=" + value; }    public final int hashCode() {        return Objects.hashCode(key) ^ Objects.hashCode(value);    }    public final V setValue(V newValue) {        V oldValue = value;        value = newValue;        return oldValue;    }    public final boolean equals(Object o) {        if (o == this)            return true;        if (o instanceof Map.Entry) {            Map.Entry<?,?> e = (Map.Entry<?,?>)o;            if (Objects.equals(key, e.getKey()) &&                Objects.equals(value, e.getValue()))                return true;        }        return false;    }}

当元素hash雷同时，元素会通过链表的模式通过next指针相连。在JDK1.8之后，当满足肯定条件后，链表会转化为红黑树，此时，元素会从Node类型转化为TreeNode类型。

  • TreeNode为HashMap自定义的数据结构，外部记录父节点parent，左右孩子left，right，色彩标记red曾经同级前驱节点prev
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {    TreeNode<K,V> parent;  // red-black tree links    TreeNode<K,V> left;    TreeNode<K,V> right;    TreeNode<K,V> prev;    // needed to unlink next upon deletion    boolean red;    TreeNode(int hash, K key, V val, Node<K,V> next) {        super(hash, key, val, next);    }    ...... }

具体的操作逻辑能够参考：[[HashMap]]

LinkedHashMap

LinkedHashMap继承了HashMap的逻辑，只不过增加了Entry构造。以及head，tail首尾指针。

static class Entry<K,V> extends HashMap.Node<K,V> {    Entry<K,V> before, after;    Entry(int hash, K key, V value, Node<K,V> next) {        super(hash, key, value, next);    }}private static final long serialVersionUID = 3801124242820219131L;/** * The head (eldest) of the doubly linked list. */transient LinkedHashMap.Entry<K,V> head;/** * The tail (youngest) of the doubly linked list. */transient LinkedHashMap.Entry<K,V> tail;

Entry中保留了before和after指针，指向上一个插入元素Entry以及后一个插入元素Entry。以数组+红黑树+元素链表+插入程序链表的模式存储数据。

ConcurrentHashMap

ConcurrentHashMap底层通过Node数组存储数据

transient volatile Node<K,V>[] table;
  • 其中Node是ConcurrentHashMap自定义的数据结构，外部记录了元素的hash值，key，value，以及下一节点的指针next。
static class Node<K,V> implements Map.Entry<K,V> {      final int hash;      final K key;      volatile V val;      volatile Node<K,V> next;      Node(int hash, K key, V val, Node<K,V> next) {          this.hash = hash;          this.key = key;          this.val = val;          this.next = next;      }      public final K getKey()       { return key; }      public final V getValue()     { return val; }      public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }      public final String toString(){ return key + "=" + val; }      public final V setValue(V value) {          throw new UnsupportedOperationException();      }      public final boolean equals(Object o) {          Object k, v, u; Map.Entry<?,?> e;          return ((o instanceof Map.Entry) &&                  (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&                  (v = e.getValue()) != null &&                  (k == key || k.equals(key)) &&                  (v == (u = val) || v.equals(u)));      }      /**       * Virtualized support for map.get(); overridden in subclasses.       */      Node<K,V> find(int h, Object k) {          Node<K,V> e = this;          if (k != null) {              do {                  K ek;                  if (e.hash == h &&                      ((ek = e.key) == k || (ek != null && k.equals(ek))))                      return e;              } while ((e = e.next) != null);          }          return null;      }  }

当元素hash雷同时，元素会通过链表的模式通过next指针相连。在JDK1.8之后，当满足肯定条件后，链表会转化为红黑树，此时，table数组中的Node 元素会转化为TreeBin类型，TreeBin类型记录了由TreeNode形成红黑树的根节点root。

  • TreeBin有ConcurrentHashMap自定义，继承了Node类型。寄存了下辖红黑树的根节点root。
static final class TreeBin<K,V> extends Node<K,V> {    TreeNode<K,V> root;    volatile TreeNode<K,V> first;    volatile Thread waiter;    volatile int lockState;    // values for lockState    static final int WRITER = 1; // set while holding write lock    static final int WAITER = 2; // set when waiting for write lock    static final int READER = 4; // increment value for setting read lock    ......}
  • TreeNode由ConcurrentHashMap自定义，跟HashMap的TreeNode相似，然而ConcurrentHashMap的TreeNode继承自Node类型。
static final class TreeNode<K,V> extends Node<K,V> {    TreeNode<K,V> parent;  // red-black tree links    TreeNode<K,V> left;    TreeNode<K,V> right;    TreeNode<K,V> prev;    // needed to unlink next upon deletion    boolean red;    TreeNode(int hash, K key, V val, Node<K,V> next,             TreeNode<K,V> parent) {        super(hash, key, val, next);        this.parent = parent;    }    ......}

具体的操作逻辑能够参考：[[ConcurrentHashMap]]

TreeMap

TreeMap 通过Entry存储数据，底层是以红黑树的逻辑构造存储。

private transient Entry<K,V> root;
  • Entry是TreeMap自定义的数据结构，其中蕴含key，value，左右子树left，right，以及父节点parent，和标记色彩的color；
static final class Entry<K,V> implements Map.Entry<K,V> {      K key;      V value;      Entry<K,V> left;      Entry<K,V> right;      Entry<K,V> parent;      boolean color = BLACK;      /**       * Make a new cell with given key, value, and parent, and with       * {@code null} child links, and BLACK color.       */      Entry(K key, V value, Entry<K,V> parent) {          this.key = key;          this.value = value;          this.parent = parent;      }      ......}

WeakHashMap

WeakHashMap底层通过Entry[] 数组存储数据，采纳链表法解决hash抵触，跟HashMap 不同没有进行长链表的红黑树转化。

Entry<K,V>[] table;
  • Entry为WeakHashMap自定义的数据结构继承了WeakReference，其中蕴含value，hash值，以及next指针。key为弱援用reference的值。
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {    V value;    final int hash;    Entry<K,V> next;    /**     * Creates new entry.     */    Entry(Object key, V value,          ReferenceQueue<Object> queue,          int hash, Entry<K,V> next) {        super(key, queue);        this.value = value;        this.hash  = hash;        this.next  = next;    }    ......}

具体的操作逻辑能够参考：[[WeakHashMap]]

ConcurrentSkipListMap

ConcurrentSkipListMap底层通过跳表的数据结构进步查找效率。ConcurrentSkipListMap通过Node存储根本的key,value数据，Index存储跳表索引，HeadIndex为层级头索引。

// Node存储根本的key,value数据，是一个简略的链表static final class Node<K,V> {    final K key;    volatile Object value;    volatile Node<K,V> next;    ...}// Index 内蕴含Node元素，以及向下和向右的Index指针static class Index<K,V> {    final Node<K,V> node;    final Index<K,V> down;    volatile Index<K,V> right;    ...} // HeadIndex继承了Index,增加了level索引层级属性static final class HeadIndex<K,V> extends Index<K,V> {    final int level;    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {        super(node, down, right);        this.level = level;    }}

同时，ConcurrentSkipListMap通过对大部分操作增加CAS锁避免并发。

Set

HashSet

HashSet底层默认通过HashMap存储元素，数据贮存在HashMap的key中，value设置为默认值Object。

private transient HashMap<E,Object> map;private static final Object PRESENT = new Object(); // default valuepublic boolean add(E e) {  return map.put(e, PRESENT)==null;}

HashSet 底层还能够通过 LinkedHashMap 存储元素。依据结构函数参数不同抉择是 HashMap还是LinkedHashMap实现。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {    map = new LinkedHashMap<>(initialCapacity, loadFactor);}

LinkedHashSet

LinkedhashSet继承了HashSet，采纳LinkedHashMap存储元素。

ConcurrentSkipListSet

底层通过ConcurrentSkipListMap实现，寄存的值作为key存入ConcurrentSkipListMap中，应用Boolean.TRUE对象最为默认的value。

private final ConcurrentNavigableMap<E,Object> m;/** * Constructs a new, empty set that orders its elements according to * their {@linkplain Comparable natural ordering}. */public ConcurrentSkipListSet() {    m = new ConcurrentSkipListMap<E,Object>();}public boolean add(E e) {    return m.putIfAbsent(e, Boolean.TRUE) == null;}

TreeSet

TreeSet底层通过TreeMap存储元素，和HashSet相似，数据存储在TreeMap 的Key中，value设置为默认值Object。

private transient NavigableMap<E,Object> m;  // Dummy value to associate with an Object in the backing Map  private static final Object PRESENT = new Object();    public TreeSet(Comparator<? super E> comparator) {      this(new TreeMap<>(comparator));  }

CopyOnWriteArraySet

底层通过CopyOnWriteArrayList实现，通过List.addIfAbsent()办法实现同一个元素只存在一个，保障了元素的唯一性。

private final CopyOnWriteArrayList<E> al;/** * Creates an empty set. */public CopyOnWriteArraySet() {    al = new CopyOnWriteArrayList<E>();}public boolean add(E e) {    return al.addIfAbsent(e);}

Queue

PriorityQueue

PriorityQueue优先队列，底层通过Object数组存储元素，Object[]以档次遍历的模式存储优先队列（齐全二叉树）的元素值。索引n的左右孩子索引别离为$2n+1,2*(n+1)$;

transient Object[] queue;

BlockingQueue

A Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element.

阻塞队列接口，提供了额定的一些操作，当这些操作无奈立刻执行时（插入时容量满了、删除/获取元素时队列为空），不会像失常的queue一些立刻返回而是阻塞一段时间直到满足条件（设置了等待时间、条件满足了）

阻塞队列的阻塞操作个别是通过创立多个条件锁ReentrantLock.Condition实现的，通过调用Condition.await()以及Condition.signal()进行线程的阻塞和唤醒。

private final Condition notEmpty;/** Condition for waiting puts */private final Condition notFull;

  • 增加元素

    • add(E e)/offer(E e)办法，当数组满了之后，间接返回false

      public boolean offer(E e) {    checkNotNull(e);    final ReentrantLock lock = this.lock;    lock.lock();    try {        if (count == items.length)            return false;        else {            enqueue(e);            return true;        }    } finally {        lock.unlock();    }}

    • put(E e)/offer(E e, long timeout, TimeUnit unit)办法，当数组满了之后，阻塞直到唤醒或者阻塞指定工夫

      public void put(E e) throws InterruptedException {    checkNotNull(e);    final ReentrantLock lock = this.lock;    lock.lockInterruptibly();    try {        while (count == items.length)            notFull.await();        enqueue(e);    } finally {        lock.unlock();    }}public boolean offer(E e, long timeout, TimeUnit unit)    throws InterruptedException {    checkNotNull(e);    long nanos = unit.toNanos(timeout);    final ReentrantLock lock = this.lock;    lock.lockInterruptibly();    try {        while (count == items.length) {            if (nanos <= 0)                return false;            nanos = notFull.awaitNanos(nanos);        }        enqueue(e);        return true;    } finally {        lock.unlock();    }}

  • 获取元素

    • poll()，弹出队首元素，队列为空时间接return null;
    • take() ，弹出队首元素，队列为空时阻塞至队列不为空。
    • poll(long timeout, TimeUnit unit)，弹出队首元素，队列为空时阻塞指定工夫后重试一次。
    • peek()，获取队首元素，队列为空时间接return null;

ArrayBlockingQueue

A bounded BlockingQueue backed by an array. This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.

顾名思义，ArrayBlockingQueue底层是通过Object[]数组实现元素的存储的。ArrayBlockingQueue是有界队列，存储元素的数量通过初始化办法指定。当数组满了的时候，就无奈间接往数组中增加元素了。ArrayBlockingQueue FIFO，增加元素到队尾，删除队首元素。

  • 初始化办法

    public ArrayBlockingQueue(int capacity, boolean fair) {    if (capacity <= 0)        throw new IllegalArgumentException();    this.items = new Object[capacity];    lock = new ReentrantLock(fair);    notEmpty = lock.newCondition();    notFull =  lock.newCondition();}

LinkedBlockingQueue

依据初始化参数动静结构是否有界的阻塞队列。底层通过Node构造实现的链表进行存储。

  • Node构造

    static class Node<E> {    E item;    Node<E> next;    Node(E x) { item = x; }}

  • 初始化办法

    public LinkedBlockingQueue() {    // 不指定队列容量，默认为Integer的最大值    this(Integer.MAX_VALUE);}public LinkedBlockingQueue(int capacity) {    if (capacity <= 0) throw new IllegalArgumentException();    this.capacity = capacity;    last = head = new Node<E>(null);}

ArrayBlockingQueue 和LinkedBlockingQueue除了底层实现形式不同之外，ArrayBlockingQueue在进行数据操作时用的都是同一把锁final ReentrantLock lock;，而LinkedBlockingQueue初始化了二把锁插入和弹出操作应用不同的锁。final ReentrantLock putLock； final ReentrantLock takeLock；