List, Set,Queue,Map

List、Set、Queue接口分别继承了Collection接口，Map本身是一个接口。
像ArrayList、LinkedList都是实现了List接口，HashSet实现了Set接口，而Deque（双向队列，允许在队首、队尾进行入队和出队操作）继承了Queue接口，PriorityQueue实现了Queue接口。另外LinkedList（实际上是双向链表）实现了了Deque接口。
像ArrayList、LinkedList、HashMap这些容器都是非线程安全的。

Vector、Stack、HashTable

public interface Iterable<T> {

    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

各种关系

public interface Collection<E> extends Iterable<E> 

public interface Queue<E> extends Collection<E>

Queue的子类
AbstractQueue<E>,ArrayBlockingQueue<E>,ArrayDeque<E>,BlockingDeque<E>,BlockingQueue<E>,ConcurrentLinkedDeque<E>,ConcurrentLinkedQueue<E>,DelayQueue<E extends Delayed>,Deque<E>,LinkedBlockingDeque<E>,LinkedBlockingQueue<E>,LinkedList<E>,LinkedTransferQueue<E>,PriorityBlockingQueue<E>,PriorityQueue<E>,SynchronousQueue<E>,TransferQueue<E>

Vector,Stack相关

public abstract class AbstractCollection<E> implements Collection<E>
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> 

public class Vector<E> extends AbstractList<E>  implements List<E>, RandomAccess, Cloneable, java.io.Serializable

class Stack<E> extends Vector<E>

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public interface List<E> extends Collection<E>

public interface Set<E> extends Collection<E> 

Hashtable关系

public abstract class Dictionary<K,V>

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable

Collection相关
AbstractCollection<E>,AbstractList<E>,AbstractQueue<E>,AbstractSequentialList<E>,AbstractSet<E>,ArrayBlockingQueue<E>,ArrayDeque<E>,ArrayList<E>,ArraySet<E>,BlockingDeque<E>,BlockingQueue<E>,ConcurrentHashMap.KeySetView<K, V>,ConcurrentLinkedDeque<E>,ConcurrentLinkedQueue<E>,ConcurrentSkipListSet<E>,and23 others.

ArrayList简单查看，可以看到它把数据存在一个数组里的。就是操作数组的

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
E elementData(int index) {
        return (E) elementData[index];
    }

LinkedList相关

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
  //可以看到对我们的元素E进行了封装，多保留了prev和next也就是前后两个数据
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);//添加到最后的，上一条就是l也就是last，最后一条没有就是null
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;//l就是插入这条数据之前的最后一条数据。它的next就是当前这条数据拉
        size++;
        modCount++;
    }

    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);//添加到第一条的话，那么上一条就是空，下一条就是以前的第一条，也就是first
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);
  //  取数据，一分为二，看在哪部分，可以提高效率，只循环最近的一部分。
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

LinkedBlockingQueue,LinkedBlockingDeque

public class LinkedBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable
public class LinkedBlockingDeque<E>
    extends AbstractQueue<E>
    implements BlockingDeque<E>, java.io.Serializable

看下父类Queue,看源码说明，这个里边不能存空数据的。
add,offer基本一样都是插入数据的，唯一区别就是容量限制的区别了。
remove和poll一样都是把数据取出来，并从集合里删除掉。区别在于，后者在这个Queue为空的时候可以返回null，前者就挂了。
element和peek，也是把数据取出来，不过不删除。peek可以返回null，element和remove一样，没有数据就挂了

public interface Queue<E> extends Collection<E> {
    /**
     * Inserts the specified element into this queue if it is possible to do so
     * immediately without violating capacity restrictions, returning
     * {@code true} upon success and throwing an {@code IllegalStateException}
     * if no space is currently available.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean add(E e);

    /**
     * Inserts the specified element into this queue if it is possible to do
     * so immediately without violating capacity restrictions.
     * When using a capacity-restricted queue, this method is generally
     * preferable to {@link #add}, which can fail to insert an element only
     * by throwing an exception.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean offer(E e);

    /**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll poll} only in that it throws an exception if this
     * queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E remove();

    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E poll();

    /**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E element();

    /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();
}

完事分析下他们的实现接口的区别，还有这两个都带了Block，就是里边的操作带了lock锁的

public interface BlockingQueue<E> extends Queue<E>

public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E>

看下图的方法比较明白了，Deque和queue的区别就是前者可以两头取数据，而后者只能从头开始一条一条取数据

image.png

另外看下他们存储的数据就能知道了为啥一个可以两头取，一个只能按顺序取了

//Deque的存储数据如下，包括前一条，后一条数据
    static final class Node<E> {
        /**
         * The item, or null if this node has been removed.
         */
        E item;

        /**
         * One of:
         * - the real predecessor Node
         * - this Node, meaning the predecessor is tail
         * - null, meaning there is no predecessor
         */
        Node<E> prev;

        /**
         * One of:
         * - the real successor Node
         * - this Node, meaning the successor is head
         * - null, meaning there is no successor
         */
        Node<E> next;

        Node(E x) {
            item = x;
        }
    }
//Queue存储的数据，只有一个next
    static class Node<E> {
        E item;

        /**
         * One of:
         * - the real successor Node
         * - this Node, meaning the successor is head.next
         * - null, meaning there is no successor (this is the last node)
         */
        Node<E> next;

        Node(E x) { item = x; }
    }

PriorityBlockingQueue

看queue的时候看到这个类就顺道简单看下，这个类 是有排序的，自己可以在构造方法里传一个Comparator，如果不传的话，那么数据就必须实现Comparable接口，否则就挂了。

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        int n, cap;
        Object[] array;
        while ((n = size) >= (cap = (array = queue).length))
            tryGrow(array, cap);
        try {
            Comparator<? super E> cmp = comparator;
            if (cmp == null)//如果构造方法里没有传compartor的话
                siftUpComparable(n, e, array);
            else
                siftUpUsingComparator(n, e, array, cmp);
            size = n + 1;
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
        return true;
    }

    private static <T> void siftUpComparable(int k, T x, Object[] array) {
        Comparable<? super T> key = (Comparable<? super T>) x;//这里把数据强转了。可能发生ClassCastException
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = array[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            array[k] = e;
            k = parent;
        }
        array[k] = key;
    }

vector这个东西和数组差不多，就是它的长度可以根据需要改变而已。

 * The {@code Vector} class implements a growable array of
 * objects. Like an array, it contains components that can be
 * accessed using an integer index. However, the size of a
 * {@code Vector} can grow or shrink as needed to accommodate
 * adding and removing items after the {@code Vector} has been created.
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    //就是放到一个数组里了
    public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

stack

看介绍，就是一个后进先出的原则，就是我们常说的那种堆栈push,pop方法

 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.
 * <p>
 * When a stack is first created, it contains no items.

public
class Stack<E> extends Vector<E>

Hashtable

看介绍，它的key，value不能为空，另外key还要实现hashCode和equals方法，还有这东西是线程安全的，随处可见synchronized方法

 * This class implements a hash table, which maps keys to values. Any
 * non-<code>null</code> object can be used as a key or as a value. <p>
 *
 * To successfully store and retrieve objects from a hashtable, the
 * objects used as keys must implement the <code>hashCode</code>
 * method and the <code>equals</code> method. <p>
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable 

稍作测试,

Stack<String> stack=new Stack<>();
        stack.add("fragment1");
        stack.add("fragment2");
        
        System.err.println("pop====="+stack.pop()+" ="+stack.pop()+" =="+stack.isEmpty());
        
        Hashtable<String, String> hashtable=new Hashtable<>();
    hashtable.put("key1", "value1");
        hashtable.put("key5", "value2");
        hashtable.put("key4", "value4");
        hashtable.put("key3", "value3");
        Enumeration<String> keys=hashtable.keys();
        while(keys.hasMoreElements()) {
            System.err.println("==="+keys.nextElement());
        }
//result
pop=====fragment2 =fragment1 ==true
===key5
===key4
===key3
===key1

为啥Hashtable是有序的，而且是倒叙的，它按照key自动排序了【这是错误的结论】

我刚好写的key它就按照倒叙排了，还以为这玩意能自动排序了，源码看了几遍，楞是没看出来，百度搜也没找出来啊，看到有人说是无序的，我去，不对啊。我又赶紧改了下key，改成111，222之类的数字，终于发现它是无序的了。
弄完了顺道看下别人对hashtable的介绍，就随便百度下：嗯，我是觉得图画的不错，
http://blog.csdn.net/fujiakai/article/details/51585767
http://wiki.jikexueyuan.com/project/java-collection/hashtable.html
话说集合也太多了，还有一堆concurrent开头的hashmap。list，set等，看名字应该是为了处理并发的吧。有空再看。