高频面试题-Java集合体系

Java中的集合体系

Java中的集合分为两大体系，一是继承于Collection接口的List和Set体系，List体系如：ArrayList,LinkedList，Set体系如：TreeSet,HashSet，二是继承于Map接口集合体系如：HashMap,TreeMap等。其中使用到多种数据结构：数组，链表，队列，Hash表等等。

1.Map继承体系

Map是一种key-value的存储结构，最大的有点在于查询效率高，继承体系如下： Map比较常用的有HashMap和LinkedHashMap,TreeMap。

1.1.LinkedHashMap

LinkedHashMap是在HashMap的基础上保证了元素的插入顺序，它是基于双向链表来实现的。见《HashMap底层原理》，LinkedHashMap 是继承于 HashMap 实现的一种集合，具有 HashMap 的特点外，它还是有序的。

LinkedHashMap源码如下：

public class LinkedHashMap extends HashMap implements Map
{
	//一个 LinkedHashMap.Entry 就是HashMap.Node
   static class Entry extends HashMap.Node {
        Entry before, after;
        Entry(int hash, K key, V value, Node next) {
            super(hash, key, value, next);
        }
    }

	/**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry tail;
	//true 表示按照访问顺序，会把访问过的元素放在链表后面，放置顺序是访问的顺序
	//false 表示按照插入顺序遍历
	final boolean accessOrder;
	//构造方法
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

LinkedHashMap中的一个 .Entry 就是HashMap的Node ，只不过LinkedHashMap的Entry中多出来了一个 before, after ，这个是用来保证Entry的插入顺序的。

对于 LinkedHashMap.Entry head 和 LinkedHashMap.Entry tail 则是用来表示链表的头节点和尾节点的。

具有默认初始容量（16）和加载因子（0.75）。并且设定了 accessOrder = false，表示默认按照插入顺序进行遍历。 LinkedHashMap中没有add方法以及remove方法等，直接调用的是HashMap中的方法，具体见HashMap。

1.2.TreeMap

TreeMap是基于红黑树实现，它默认情况下按照key的compareTo进行自然顺序升续排序，所以put的key需要实现Comparable接口，当然也可以在new TreeMap(Comparator)的时候指定Comparator进行排序。

public class TreeMap
    extends AbstractMap
    implements NavigableMap, Cloneable, java.io.Serializable
{
    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     * 比较器
     */
    private final Comparator comparator;

	//红黑树根节点
    private transient Entry root;

    /**
    节点数
     * The number of entries in the tree
     */
    private transient int size = 0;

    /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;
	//通过构造器指定比较器
    public TreeMap(Comparator comparator) {
        this.comparator = comparator;
    }
	//红黑树种的每个节点类型
	static final class Entry implements Map.Entry {
        K key;				//键
        V value;			//值
        Entry left;	//左子树
        Entry right;	//有子树
        Entry parent;	//父节点
        boolean color = BLACK;	//颜色
        ...省略...
   }

这里可以看到，TreeMap通过 Comparator 进行排序，当然可以通过构造器传入Comparator。添加元素方法如下：

 public V put(K key, V value) {
        Entry t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
			//根节点为空，设置新添加的元素为根节点
            root = new Entry(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry parent;
        // split comparator and comparable paths
        //比较器
        Comparator cpr = comparator;
        if (cpr != null) {
        	//比较器不为空，插入新的元素时，按照comparator实现的类进行排序
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp  0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            //如果比较器为空，按照key的自然顺序
                Comparable k = (Comparable) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp  0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry e = new Entry(key, value, parent);
        if (cmp