总览

先放一张Java集合类的关系图（非原创）

Java集合框架图

类有点多，看的眼晕？我们来慢慢从头梳理一下。

图中四边为点细点的是接口，虚线的是抽象类。

Iterator

迭代器。从源码看Collection接口继承了Iterator接口，所以我们平时用到的ArrayList、LinkedList等都是实现了Iterator接口的。迭代器是用来遍历选择序列中的对象的，但是它只能单向移动。

1）使用方法iterator()要求容器返回一个Iterator。
2）使用hasNext()检查序列中时候还有元素。
3）使用next()获取序列中的下一个元素。
4）使用remove()将迭代器最新返回的元素删除。

重点在使用迭代器的时候如果遇到需要将当前获取到的元素从序列中移除，比如遍历一个List，不能使用List.remove()，而要使用迭代器的Iterator.remove()。

ListIterator

这是一个更加强大的Iterator的子类型，只能用于各种List类的访问。ListIterator可以双向移动

看一看源码中定义的方法就明白了：

boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove();
void set(E e);//将最近返回的元素替换
void add(E e);//向下一个将要返回的元素前面插入新元素

Collection

Collection接口概括了序列的概念——一种存放一组对象的方式。一个独立元素的序列，这些元素都服从一条或多条规则。List必须按照插入的顺序保存元素，Set不能有重复的元素（这里先这样记着，这确实是Set的特点，其他后面再详细说）。Queue按照排队规则来确定对象产生的顺序（很简洁的用几个方法实现了队列的功能）。

在添加一组元素的时候建议使用Collections.addAll(..)。

public static <T> boolean addAll(Collection<? super T> c, T... elements)

Map

可能是图上有误，从源码看其实它和Collection接口并没有关系，两者互相独立。Map使用一组“键值对”（key-value）来储存元素，允许使用键来查找值。Map不能包含重复的key，但是可以包含相同的value。

List

这里只提ArrayList和LinkedList。

ArrayList & LinkedList

ArrayList的实现是基于动态对象数组，源码：

transient Object[] elementData;

LinkedList的实现是基于双向链表，适合用于实现Stack和Queue，链表节点的源码：

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

在随机访问的时候，ArrayList的性能要优于LinkedList，因为ArrayList只需要提取下标对应的元素，而LinkedList需要通过链表一个个的往后查找。

在执行插入和移除操作的时候，特别是频繁插入，量大的时候，LinkedList的性能要远优于ArrayList。对LinkedList来说，插入元素只需要调整前后元素的指针（上面的next和prev）；而对ArrayList来说，插入移除操作不仅需要将后面的元素全部进行移动，还要在空间不足的时候进行动态扩展（新建一个更大的数组并把原来的数组copy过去）。

最佳的做法可能是将ArrayList作为默认首选，只有你需要使用额外的功能，或者当程序性能因为经常从表中间进行插入和删除而变差的时候，才去选择LinkedList。

Map

HashMap & HashTable

两者都是存储“键值对”（key-value）的散列表，都是采用拉链法实现的。
即使用Entry<K,V>数组来存放键值对（各自有静态内部类Entry，继承自Map.Entry），数组中每个槽位又是一个链表的头节点。笔者描述的不太清楚，看图就明了了。

来自HashMap的百度百科

添加和删除操作的实现：用key计算出hash值，以hash值为数组下标检查对应槽位是否存在Entry，若有，沿着链表对比key和Entry的key。若匹配到了，添加操作就变成覆盖原来的value值，删除操作就删除该节点。若匹配不到，添加操作就把该键值对插入到该链表表头，删除操作返回null。
这里有个区别，HashTable是直接使用key.hashCode()方法返回值作为hash值，而HashMap则要在HashMap.hash(Object key)方法中使用key.hashCode()返回值重新计算产生hash值：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

在线程安全方面，HashTable几乎所有方法都加上了synchronized关键字实现线程安全，而HashMap没有，需要HashMap实现线程安全的话可以使用

Map Collections.synchronizedMap(Map m)

不过这两种都是锁住整个Map，而ConcurrentHashMap则使用分段加锁实现线程安全，在多线程时性能更好。

LinkedHashMap

LinkedHashMap继承自HashMap，增加了一个Entry链表来储存键值对的添加顺序，以便在遍历时按添加顺序遍历。应该只在程序功能有这方面要求时使用，不然额外维护一个链表需要耗费额外的资源。

TreeMap

TreeMap使用红黑树来实现的，按照键来进行排序。

Map的遍历

1、使用keySet()，在遍历返回的key获取对应的value。
2、使用entrySet()，直接或许每一组键值对，推荐。

第一选择还是HashMap吧，除非有额外的功能需求。

Set

HashSet & TreeSet

HashSet内部用一个HashMap来实现功能，TreeSet则是封装了一个TreeMap。
怎么实现不重复元素，看下面几行源码就明白了：

private static final Object PRESENT = new Object();
······
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

参考：
jdk1.8.0中的源码
《Java编程思想》
JAVA集合类汇总
Java 集合系列14之 Map总结