java中Map、Collection接口常用实现类源码浅析

在Java中集合是常用的数据结构，而Map与Collection的实现类有很多，我们常见的有HashMap、HashTable、TreeMap、LinkedHashMap、ArrayList、Linkedlist、Vector、HashSet、TreeSet、LinkedHashSet；

下面从源码的层面简析这些实现类的特性；

Map

先看看Map接口的继承关系图

Map是顶级接口，声明了通用的抽象方法，如获取所有键值对的方法——entrySet；以及还有静态的内部接口Entry；使用entrySet遍历Map集合的方式效率高于使用keySet遍历方式；keySet会遍历两次集合，第一次将集合转为Iterator对象，第二次重hashMap中取出key所对应的entrySet；而entrySet只是遍历一次就把key和value放入了entry中。如果是在JDK8，使用Map.forEach方法更好。

values()返回的是 V 值集合，是一个 list 集合对象；keySet()返回的是 K 值集合，是一个 Set 集合对象；entrySet()返回的是 K-V 值组合集合。

AbstractMap

抽象类AbstractMap实现了Map接口的”骨干”方法，目的是减少实现Map接口的时需要重写的方法。

如其中实现的keySet方法用于获得Map中的所有Key值Set集合，内部创建AbstractSet的匿名子类实例存放key值；实现的values方法中，创建了AbstractCollection匿名子类实例，用于存放map中value值；

HashMap

HashMap继承自AbstractMap并实现了Map等接口，HashMap中定义了名为Node的静态内部类，Node实现了Map.Entry接口，是一个单向链表，然后使用Node[]数组，完成了HashMap的存储结构（数组+链表/红黑树）。

HashMap中还定义了一个静态内部类，TreeNode，TreeNode继承自LinkedHashMap.Entry，TreeNode实现了红黑树数据结构。

在计算Key的Hash值时，如果Key为空，则Hash值为0

put()

public V put(K key, V value) {
    //1.对Key计算Hash值
        return putVal(hash(key), key, value, false, true);
    }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
    //2.检查Hash表是否为空，如果是空则调用resize扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
    //3.计算下标，并检查是否存在，不存在则在数组中直接添加一个节点，并放入key，value
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //4.Hash值、key相同时，替换旧值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //4.Hash值相同，Key不同时，则以链表的的方式连接到后面
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //5.如果链表长度超过阀值（TREEIFY_THRESHOLD=8），则把链表转换成红黑树
                        if (binCount >= TREEIFY_THRESHOLD= - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //链表中包含要插入的键值对时，终止插入
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //判断要插入的值是否存在HashMap中
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
    //键值对数量超过阀值时扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

方法的入口是put(K,V)，但核心逻辑是在putVal(int, K k, V , boolean ,boolean)；核心做了以下工作：

1. 计算下标
2. 判断Hash表状态，表容量不够则扩容
3. 查找要插入的键值对是否存在，不存在则直接放入，键相同时，用链表的方式连接到相应的Hash值后面
4. 如果链表长度超过阈值，将链表转换成红黑树
5. 如果键存在，则更新旧值

get()

public V get(Object key) {
        Node<K,V> e;
    //1.根据Key计算Hash值，再调用getNode方法
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //2.节点数组判空，并根据Hash值找到头结点
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //3.检查头节点是否为要找的节点
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //4.遍历链表，找到节点并返回
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
    //5.找不到返回空
        return null;
}

get()方法相比put()更简单，先计算Hash值，再根据Hash值遍历后面的链表，调用Key.equals()方法进行匹配。

小结

HashMap使用Hash表作为数据结构，线程不安全，键值可以为空，自定义对象作为键时，需要重写equals()和HashCode()方法;如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使
HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。

LinkedHashMap

LinkedHashMap继承自HashMap，并实现了Map接口，其中定义的静态内部类Entry继承自HashMap.Node类，在Entry中定义了前后节点，实现了Hash表和双向链表数据结构。通过双向链表，保证了数据存取顺序一致。

TreeMap

TreeMap继承自AbstractMap，直接实现了NavigableMap接口，NavigableMap是Map的间接子接口；TreeMap中定义的静态内部类Entry实现了Map.Entry接口，并添加了父、左右还有节点属性，实现了红黑树结构；TreeMap内部自动自然排序，如果要存储自定义对象需要创建比较器（实现Comparator接口）或自定义类实现Comparable接口，重写compareTo方法；

Hashtable

Hashtable继承自Dictionary，实现了Map接口。其中的私有静态内部类Entry实现了Map.Entry接口，并增加了增加了hash、key、value、next成员属性，实现了单向链表结构，再结合数组，实现了Hash表存储结构。

其中的public成员方法都使用了synchronized修饰，所以线程安全但效率相对较低。

键值都不可以为null。

Collection

Collection 层次结构中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接实现：它提供更具体的子接口（如 Set 和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。

AbstractCollection

AbstractCollection抽象类提供了Collection接口的骨干实现，减少子类需要实现的方法，如contains()；

List

List接口继承自Collection接口，该接口下的实现类为有序列表，可以根据索引访问其中的元素，可以有多个null元素。

LinkedList

LinkedList继承自AbstractCollection的子类AbstractSequentialList；LinkedList中定义了静态内部类Node，Node中定义了前驱与后继节点（Node），这实现了单向链表数据结构，单向链表的特性就是增删快。

get()

先检查索引（下标）是否存在，不存在则抛出索引（下标）越界异常，

下标存在则调用node(inde)方法，这个方法会先判断下标是在前半还在是后半，在前半就从前往后遍历，在后半就从后往前遍历，这说明如果要找的索引在两头时，效率是很高的。

set()

set()方法很简单，先根据索引遍历列表，获得Node后替换成新值。

add()

add()方法被重载过，当只有一个参数时，直调用linkLast()将元素链接到链表最后面；

两个参数时，先判断是不是尾节点，是位节点直接调用linkLast()方法；不是尾节点则调用linkBefore()方法；

查找到索引值处的节点(node)，判断是不是头结点，最后就是链表的插入操作。

LinkedList线程不安全，查询慢。由于定义了表头与表尾元素，所以也可以当做堆栈、队列和双向队列使用。

ArrayList

ArrayList继承自AbstractList并实现了List等接口。通过ArrayList提供的构造方法可已看出来，ArrayList是通过数组实现的；

get()

get()方法直接是通过数组索引(下标)取值

set()

set()方法也是通过通过数组索引(下标)直接赋值

add()

两个add()方法在插入元素前都会对数组容量进行检查，容量不够时进行扩容；扩容完成后对数组进行复制；

扩容后的长度是之前长度的1.5倍+1。

ArrayList数据查询快，增删慢，线程不安全。

Vector

Vector继承自AbstractList并实现了List等接口；Vector与ArrayList基本一致，也是使用数组实现的；但是Vector的构造方法可以指定扩容参数

在扩容方法grow()中，默认扩展一倍大小，也可增加指定大小

Vector与ArrayList最大的区别是，Vector的public方法都使用了synchronized来实现线程安全，这就降低了Vector的速度。

Set

Set接口也继承自Collection接口，Set的实现类是不包含重复元素的集合，最多只能包含一个null元素;

TreeSet

TreeSet继承自AbstractSet实现了Set的子孙接口(NavigableSet)，通过TreeSet的构造方法，可以发现，TreeSet内部是用TreeMap实现的，那么底层也是使用了二叉树做数据结构；自动内排序；

add()

add()方法其实调用的是Map的put()方法，map的key是需要存放的元素，而value是一个Object对象。这也是为什么TreeSet不能存放重复值得原因。

TreeSet中的其他方法内也是对Map方法的调用。TreeMap的key不可以为空，value可以为空；

HashSet

HashSet继承自AbstractSet并实现了Set等接口；通过构造方法，可以看出来，HashSet内部是使用HashMap实现的，底层也是使用了Hash表作为数据结构；

add()

HashSet的add()方法使用的是HashMap的put()方法；

HashSet的其他方法也使用的是HashMap的响应方法进行封装。

小结

HashSet不保证存取顺序一致，允许一个null，值唯一。

LinkedHashSet

LinkedHashSet继承自HashSet，并实现了Set等接口；其构造方法直接调用了父类的3个参数的构造方法，在父类的构造方法中创建LinkedHashMap对象；可以看出来LinkedHashSet底层使用了链表加Hash表作为数据结构。既保证数据的存取顺序，也保证了值得唯一性；