先盗一张总图

Java集合类(结合源码小结)

Java里的集合分别出自两个接口，Collection 和 Map。

其中Collection 集成了Iterator，因此只有Collection的实现类才能用Iterator进行遍历。

public interface Collection<E> extends Iterable<E>

1.Collection接口

Collection接口下面有三个接口，分别是List、Set、Queue (Deque extends Queue)

1.1List

其实现类有LinkedList 、 ArrayList、Vector(已经不推荐用)。

LinkedList和ArrayList的差别：

LinkedList 还实现了 Deque 接口和Queue接口。

因此LinkedList还可以作为队列、双向队列、栈(只从一头进出)来用。

class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Queue<E>

1.2Set

Set不允许重复元素，其原因可从add()方法中找到：

  public boolean add(E object) {
        return backingMap.put(object, this) == null;
    }

Map中的Key是不能重复的，因此Set的内容不能重复。

Set的主要实现类有HashSet、TreeSet。

HashSet<E> extends AbstractSet<E> implements Set<E>
class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>
interface NavigableMap<K,V> extends SortedMap<K,V>

其中TreeSet是有序的，因为他实现了SortedMap接口，具体逻辑也可以从add()方法中找到：

 public boolean add(E object) {
        return backingMap.put(object, Boolean.TRUE) == null;
    }

backingMap是TreeMap的实例，put方法如下：

V putInternal(K key, V value) {
        Node<K, V> created = find(key, Relation.CREATE);
        V result = created.value;
        created.value = value;
        return result;
    }

    /**
     * Returns the node at or adjacent to the given key, creating it if requested.
     *
     * @throws ClassCastException if {@code key} and the tree's keys aren't mutually comparable.
     */
    Node<K, V> find(K key, Relation relation)

它会创建一个Node，将插入值放到指定的位置。

2.Map

Map的实现类主要有4个， TreeMap、HashMap、WeakHashMap、Hashtable。其中，前3者都是AbstractMap的实现类， AbstractMap 实现了Map接口；而Hashtable则是直接实现map接口。

2.1TreeMap

如之前所说，TreeMap的put方法证明TreeMap是有序的。

2.2HashMap和Hashtable

HashMap extends AbstractMap（AbstractMap implements Map）, 是非线程安全的， value可以为null

Hashtable implements Map，是线程安全的， value不能为null

Hashtable的Value不能为null的原因，其内部类HashtableEntry的setValue()方法中，value为null时抛出了空指针异常。

public final V setValue(V value) {
            if (value == null) {
                throw new NullPointerException("value == null");
            }
            V oldValue = this.value;
            this.value = value;
            return oldValue;
}

而HashMap的父类AbstarctMap中，内部类SimpleEntry的setValue()方法如下：

  public V setValue(V object) {
            V result = value;
            value = object;
            return result;
 }

从中也可以发现，显然AbstractMap的各个实现类的VALUE也可以为null。

Hashtable是线程安全的，原因只是其各个实现方法加上了synchronized而HashMap没加。

    public synchronized int size() {
        return size;
    }

通过Collections.synchronizedMap()可以将HashMap转化为线程安全的Map，其余的集合类同理，都是加了个互斥锁。

public static <K, V> Map<K, V> synchronizedMap(Map<K, V> map) {
        if (map == null) {
            throw new NullPointerException("map == null");
        }
        return new SynchronizedMap<K, V>(map);
    }

 static class SynchronizedMap<K, V> implements Map<K, V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K, V> m;

        final Object mutex;

        SynchronizedMap(Map<K, V> map) {
            m = map;
            mutex = this;
        }

        @Override
        public void clear() {
            synchronized (mutex) {
                m.clear();
            }
        }
        ……
    }

2.3HashMap 和 WeakHashMap

HashMap中，值是存放在HashMapEntry中的

class HashMapEntry<K, V> implements Entry<K, V>

而WeakHashMap中，存放值的Entry是个弱引用的

 private static final class Entry<K, V> extends WeakReference<K> implements
            Map.Entry<K, V> {
        ……
        Entry(K key, V object, ReferenceQueue<K> queue) {
            super(key, queue);
            isNull = key == null;
            hash = isNull ? 0 : Collections.secondaryHash(key);
            value = object;
        }
        ……
    }

秒客网