Java集合框架吐血总结

Java中的集合框架，大致分为四个接口：Set List Queue 以及Map,Map这个接口，并不属于Collection总接口下，但是它用到了Collection下的接口。

Java的集合类主要由两个接口派生而出：Collection和Map,Collection和Map是Java集合框架的根接口。

Java集合和数组的区别：

1：数组长度在初始化时指定，意味着只能保存定长的数据。而集合可以保存数量不确定的数据。同时可以保存具有映射关系的数据（即关联数组，键值对 key-value）。

2：数组元素即可以是基本类型的值，也可以是对象。集合里只能保存对象。

集合中接口关系图：

图片来源于图片上的地址，在此感谢，个人觉得比别人的图更清晰.

Collection这个接口的父类接口就是*的接口类interface，所以它的子接口都可以使用迭代器来操作，进行遍历。在Collection接口中也有一些通用的方法，比如添加元素，删除元素，返回Collection集合的个数以及清空集合等。

接下来，就该一个一个梳理这些Collection子接口的特性，以及它们的利弊啦！~

NO.1                                  集合Set

Set集合中包含了三个比较重要的实现类:HashSet、TreeSet和EnumSet。

什么是HashSet?

HashSet是Set接口的典型实现，实现了Set接口中的所有方法，并没有添加额外的方法，大多数时候使用Set集合时就是使用这个实现类。HashSet按Hash算法来存储集合中的元素。因此具有很好的存取和查找性能.

HashSet的特性：

 

1.不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化。
2.HashSet不是同步的，如果多个线程同时访问一个HashSet，则必须通过代码来保证其同步。（即线程不安全的）
3.集合元素值可以是null。
4.HashSet判断两个元素是否相等的标准也是其一大特点。HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也相等。

需要特别介绍的地方：

HashSet特性中的第四点：HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也相等。

在这一特性中，两个对象比较 具体分为如下四个情况：

1.如果有两个元素通过equal()方法比较返回false，但它们的hashCode()方法返回不相等，HashSet将会把它们存储在不同的位置。

2.如果有两个元素通过equal()方法比较返回true，但它们的hashCode()方法返回不相等，HashSet将会把它们存储在不同的位置。

3.如果两个对象通过equals()方法比较不相等，hashCode()方法比较相等，HashSet将会把它们存储在相同的位置，在这个位置以链表式结构来保存多个对象。这是因为当向HashSet集合中存入一个元素时，HashSet会调用对象的hashCode()方法来得到对象的hashCode值，然后根据该hashCode值来决定该对象存储在HashSet中存储位置。

4.如果有两个元素通过equal()方法比较返回true，但它们的hashCode()方法返回true，HashSet将不予添加。

HashSet判断两个元素相等的标准：两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也相等。

注意：HashSet是根据元素的hashCode值来快速定位的，如果HashSet中两个以上的元素具有相同的hashCode值，将会导致性能下降。所以如果重写类的equals()方法和hashCode()方法时，应尽量保证两个对象通过hashCode()方法返回值相等时，通过equals()方法比较返回true。

笔者自己遇到过的问题：有一次，我在HashSet中放入对象后，通过迭代器遍历，并修改其中一个对象的某个属性，导致在HashSet中，修改后的对象的属性，也就是hashCode，都与另一个对象相同，并使用equals方法为true，这就导致HashSet中存在了相同的对象，当修改后再次遍历后，就只能在这两个相同对象中取到其中的一个，也就是hashSet可能有N个对象,但只遍历了N-1次，即取出N-1个对象，针对这种情况，我使用的解决方法是：当修改后的元素可能属性与HashSet中其他对象的属性完全相同时，我们先在HashSet的遍历中，remove掉这个对象，并复制一份，然后修改复制的对象，再把复制的对象加入HashSet，如果修改后的属性与HashSet中某个对象相同了，就加不进去了，这样保证了HashSet中的对象个数，和遍历它的次数是一样的，我们在遍历的时候，不会丢掉其中的某个。 

 

此外HashSet还有一个子接口，是LinkHashSet:

LinkedHashSet是HashSet对的子类，也是根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，使得元素是以插入的顺序来保存的。当遍历LinkedHashSet集合里的元素时，LinkedHashSet将会按元素的添加顺序来访问集合里的元素。但是由于要维护元素的插入顺序，在性能上略低与HashSet，但在迭代访问Set里的全部元素时有很好的性能。
注意：LinkedHashSet依然不允许元素重复，判断重复标准与HashSet一致。

实质：HashSet的实质是一个HashMap。HashSet的所有集合元素，构成了HashMap的key，其value为一个静态Object对象。因此HashSet的所有性质，HashMap的key所构成的集合都具备。可以参考后续文章中HashMap的相关内容进行比对。

接下来，介绍TreeSet

什么是TreeSet?

TreeSet是一个有序的Set,TreeSet中所谓的有序，不同于之前所讲的插入顺序，而是通过集合中元素属性进行排序方式来实现的。
TreeSet支持两种排序方法：自然排序和定制排序。在默认情况下，TreeSet采用自然排序。

当我们把对象放入TreeSet时，要给对象的类实现Comparable接口，这样就有了比较的功能。否则就会出现异常。TreeSet中只能添加同一种类型的对象，否则无法比较，会出现异常。

TreeSet会调用集合中元素所属类的compareTo(Object obj)方法来比较元素之间的大小关系，然后将集合元素按升序排列，即把通过compareTo(Object obj)方法比较后比较大的的往后排。这种方式就是自然排序。

 

TreeSet中判断集合元素相等

对于TreeSet集合而言，判断两个对象是否相等的唯一标准是：两个对象通过compareTo(Object obj)方法比较是否返回0——如果通过compareTo(Object obj)方法比较返回0，TreeSet则会认为它们相等，不予添加入集合内；否则就认为它们不相等，添加到集合内。
TreeSet是根据红黑树结构找到集合元素的存储位置。

定制排序

如果要实现定制排序，则需要在创建TreeSet时，调用一个带参构造器，传入Comparator对象。并有该Comparator对象负责集合元素的排序逻辑，集合元素可以不必实现Comparable接口。

注意:如果向TreeSet中添加了一个可变对象后，并且后面程序修改了该可变对象的实例变量，这将导致它与其他对象的大小顺序发生了改变，但TreeSet不会再次调整它们

最后，是我们的EnumSet

EnumSet是一个专为枚举类设计的集合类，EnumSet中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显示或隐式地指定。EnumSet的集合元素也是有序的，EnumSet以枚举值在EnumSet类内的定义顺序来决定集合元素的顺序。

特点：

 

1.EnumSet集合不允许加入null元素。EnumSet中的所有元素都必须是指定枚举类型的枚举值。
2.EnumSet类没有暴露任何构造器来创建该类的实例，程序应该通过它提供的类方法来创建EnumSet对象。

EnumSet没有其他额外增加的方法，只是增加了一些创建EnumSet对象的方法。

Set接口中各个set的性能对比：

EnumSet性能>HashSet性能>LinkedHashSet>TreeSet性能

但是具体使用要考虑具体的使用场景。
当需要一个特定排序的集合时，使用TreeSet集合。
当需要保存枚举类的枚举值时，使用EnumSet集合。
当经常使用添加、查询操作时，使用HashSet。
当需要用到元素加入Set的顺序时使用LinkedHashSet。

 

NO.2                                 集合LIST

在List这个集合接口中，主要就是我们常用的ArrayList和LinkList啦！~

不急，我们先了解一下

List集合判断元素相等的标准 ：

List判断两个对象相等只要通过equals()方法比较返回true即可。

 

与Set不同，List还额外提供了一个ListIterator()方法（并不是集合共有的那个iterator接口），ListIterator增加了前向迭代的功能，还可以通过add()方法向List集合中添加元素。

 

ArrayList:

ArrayList和Vector作为List类的两个典型实现，完全支持之前介绍的List接口的全部功能。

 

ArrayList和Vector类都是基于数组实现的List类，所以ArrayList和Vector类封装了一个动态的、允许再分配的Object[]数组。ArrayList或Vector对象使用initalCapacity参数来设置该数组的长度，当向ArrayList或Vector中添加元素超过了该数组的长度时，它们的initalCapacity会自动增加。即ArrayList和Vector一样，是动态的拓展的数组。如果开始就知道ArrayList或Vector集合需要保存多少个元素，则可以在创建它们时就指定initalCapacity的大小，这样可以提高性能。

 

ArrayList和Vector的区别

1.ArrayList是线程不安全的，Vector是线程安全的。
2.Vector的性能比ArrayList差。

ArrayList的遍历方式

1：通过迭代器遍历

2：随机访问，通过索引值来遍历

3：增强for循环遍历

遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低。

 

LinkedList:

LinkedList类是List接口的实现类——这意味着它是一个List集合，可以根据索引来随机访问集合中的元素。除此之外，LinkedList还实现了Deque接口，可以被当作成双端队列来使用，因此既可以被当成“栈"来使用，也可以当成队列来使用。
LinkedList的实现机制与ArrayList完全不同。ArrayList内部是以数组的形式来保存集合中的元素的，因此随机访问集合元素时有较好的性能；而LinkedList内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能比较出色。
由于LinkedList双端队列的特性，所以新增了一些方法:

 

void addFirst(E e):  将指定元素插入此列表的开头。
void addLast(E e):   将指定元素添加到此列表的结尾。
E getFirst(E e):         返回此列表的第一个元素。
E getLast(E e):          返回此列表的最后一个元素。
boolean offerFirst(E e):          在此列表的开头插入指定的元素。
boolean offerLast(E e):           在此列表末尾插入指定的元素。
E peekFirst(E e):                      获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。
E peekLast(E e):                       获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。
E pollFirst(E e):                        获取并移除此列表的第一个元素；如果此列表为空，则返回 null。
E pollLast(E e):                         获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。
E removeFirst(E e):                  移除并返回此列表的第一个元素。
boolean removeFirstOccurrence(Objcet o): 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
E removeLast(E e):                                         移除并返回此列表的最后一个元素。
boolean removeLastOccurrence(Objcet o): 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。

LinkedList遍历方式

LinkedList支持多种遍历方式。
1.通过迭代器遍历LinkedList
2通过快速随机访问遍历LinkedList
3.通过for循环遍历LinkedList
4.通过pollFirst()遍历LinkedList
5.通过pollLast()遍历LinkedList
6通过removeFirst()遍历LinkedList
7.通过removeLast()遍历LinkedList

其中采用逐个遍历的方式，效率比较高。采用随机访问的方式去遍历LinkedList的方式效率最低。

LinkedList也是非线程安全的。

性能对比：

ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。ArrayList应使用随机访问(即，通过索引序号访问)遍历集合元素。
LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。LinkedList应使用采用逐个遍历的方式遍历集合元素。
如果涉及到“动态数组”、“栈”、“队列”、“链表”等结构，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍。
(01) 对于需要快速插入，删除元素，应该使用LinkedList。
(02) 对于需要快速随机访问元素，应该使用ArrayList。
(03) 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。

 

NO.3                                 集合 Queue

今天我们来介绍下集合Queue中的几个重要的实现类。关于集合Queue中的内容就比较少了。主要是针对队列这种数据结构的使用来介绍Queue中的实现类。

 

What's the Queue?

Queue用于模拟队列这种数据结构，队列通常是指“先进先出”（FIFO）的容器。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。这种结构就如同我们生活中的排队一样。

 

 

PriorityQueue（优先队列）

PriorityQueue保存队列元素的顺序不是按加入队列的顺序，而是按队列元素的大小进行重新排序。因此当调用peek()或pool()方法取出队列中头部的元素时，并不是取出最先进入队列的元素，而是取出队列中的最小的元素。

PriorityQueue的排序方式

PriorityQueue中的元素可以默认自然排序（也就是数字默认是小的在队列头，字符串则按字典序排列）或者通过提供的Comparator（比较器）在队列实例化时指定的排序方式。

注意：队列的头是按指定排序方式的最小元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。当PriorityQueue中没有指定Comparator时，加入PriorityQueue的元素必须实现了Comparable接口（即元素是可比较的），否则会导致 ClassCastException。

 

下面具体写个例子来展示PriorityQueue中的排序方式：

PriorityQueue<Integer> qi = new PriorityQueue<Integer>();
        qi.add(5);
        qi.add(2);
        qi.add(1);
        qi.add(10);
        qi.add(3);
        while (!qi.isEmpty()){
          System.out.print(qi.poll() + ",");
        }
        System.out.println();
        //采用降序排列的方式，越小的越排在队尾
        Comparator<Integer> cmp = new Comparator<Integer>() {
          public int compare(Integer e1, Integer e2) {
            return e2 - e1;
          }
        };
        PriorityQueue<Integer> q2 = new PriorityQueue<Integer>(5,cmp);
        q2.add(2);
        q2.add(8);
        q2.add(9);
        q2.add(1);
        while (!q2.isEmpty()){
              System.out.print(q2.poll() + ",");

结果：

1,2,3,5,10,
9,8,2,1,

由此可以看出，默认情况下PriorityQueue采用自然排序。指定Comparator的情况下，PriorityQueue采用指定的排序方式。

PriorityQueue的本质：

 

PriorityQueue 本质也是一个动态数组，在这一方面与ArrayList是一致的。
PriorityQueue调用默认的构造方法时，使用默认的初始容量（DEFAULT_INITIAL_CAPACITY=11）创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用加入其中的集合元素实现的Comparable）。

当使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。

public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

从构造方法可以看出，内部维护了一个动态数组。当添加元素到集合时，会先检查数组是否还有余量，有余量则把新元素加入集合，没余量则调用 grow()方法增加容量，然后调用siftUp将新加入的元素排序插入对应位置，如下：

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

除此之外，还要注意：
①PriorityQueue不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue 实例，这时请使用线程安全的PriorityBlockingQueue 类。

②不允许插入 null 元素。

③PriorityQueue实现插入方法（offer、poll、remove() 和 add 方法） 的时间复杂度是O(log(n)) ；实现 remove(Object) 和 contains(Object) 方法的时间复杂度是O(n) ；实现检索方法（peek、element 和 size）的时间复杂度是O(1)。所以在遍历时，若不需要删除元素，则以peek的方式遍历每个元素。

④方法iterator()中提供的迭代器并不保证以有序的方式遍历优PriorityQueue中的元素。

Dueue接口(双端队列)与ArrayDeque实现类

Deque接口增加了一些关于双端队列操作的方法。

void addFirst(E e):将指定元素插入此列表的开头。
void addLast(E e): 将指定元素添加到此列表的结尾。
E getFirst(E e): 返回此列表的第一个元素。
E getLast(E e): 返回此列表的最后一个元素。
boolean offerFirst(E e): 在此列表的开头插入指定的元素。
boolean offerLast(E e): 在此列表末尾插入指定的元素。
E peekFirst(E e): 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。
E peekLast(E e): 获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。
E pollFirst(E e): 获取并移除此列表的第一个元素；如果此列表为空，则返回 null。
E pollLast(E e): 获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。
E removeFirst(E e): 移除并返回此列表的第一个元素。
boolean removeFirstOccurrence(Objcet o): 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
E removeLast(E e): 移除并返回此列表的最后一个元素。
boolean removeLastOccurrence(Objcet o): 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。

从上面方法中可以看出，Deque不仅可以当成双端队列使用，而且可以被当成栈来使用，因为该类里还包含了pop(出栈)、push(入栈)两个方法。

 

 

Deque与Queue、Stack的关系

当 Deque 当做 Queue队列使用时（FIFO），添加元素是添加到队尾，删除时删除的是头部元素。

Deque 也能当Stack栈用（LIFO）。这时入栈、出栈元素都是在 双端队列的头部 进行。

注意：Stack过于古老，并且实现地非常不好，因此现在基本已经不用了，可以直接用Deque来代替Stack进行栈操作。

 

ArrayDeque

顾名思义，就是用数组实现的Deque；既然是底层是数组那肯定也可以指定其capacity，也可以不指定，默认长度是16，然后根据添加的元素的个数，动态扩展。ArrayDeque由于是两端队列，所以其顺序是按照元素插入数组中对应位置产生的。
由于本身数据结构的限制，ArrayDeque没有像ArrayList中的trimToSize方法可以为自己瘦身。ArrayDeque的使用方法就是上面的Deque的使用方法，基本没有对Deque拓展什么方法。

 

注意：ArrayDeque不是线程安全的。ArrayDeque的本质是循环数组（可以看我的循环队列那篇博客） 当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。

NO.4                                 集合 Map

HashMap

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
既然要介绍HashMap，那么就顺带介绍HashTable,两者进行比对。HashMap和Hashtable都是Map接口的经典实现类，它们之间的关系完全类似于之前介绍的ArrayList和Vector的关系。由于Hashtable是个古老的Map实现类（从Hashtable的命名规范就可以看出，t没有大写，并不是我写错了），需要方法比较繁琐，不符合Map接口的规范。但是Hashtable也具有HashMap不具有的优点。下面我们进行两者之间的比对。

HashMap与Hashtable的区别

1.Hashtable是一个线程安全的Map实现，但HashMap是线程不安全的实现，所以HashMap比Hashtable的性能好一些；但如果有多个线程访问同一个Map对象时，是盗用Hashtable实现类会更好。

2.Hashtable不允许使用null作为key和value，如果试图把null值放进Hashtable中，将会引发NullPointerException异常；但是HashMap可以使用null作为key或value。

HashMap判断key与value相等的标准

前面文章中，我们针对其他集合都分析了判断集合元素相等的标准。针对HashMap也不例外，不同的是有两个元素：key与value需要分别介绍判断相等的标准。

key判断相等的标准

类似于HashSet，HashMap与Hashtable判断两个key相等的标准是：两个key通过equals()方法比较返回true,两个key的hashCode值也相等，则认为两个key是相等的。

注意：用作key的对象必须实现了hashCode()方法和equals()方法。并且最好两者返回的结果一致，即如果equals()返回true，hashCode()值相等。

value判断相等的标准

HashMap与Hashtable判断两个value相等的标准是：只要两个对象通过equals()方法比较返回true即可。

注意：HashMap中key所组成的集合元素不能重复，value所组成的集合元素可以重复。

存储查找原理：

• 存储：首先获取key的hashcode，然后取模数组的长度，这样可以快速定位到要存储到数组中的坐标，然后判断数组中是否存储元素，如果没有存储则，新构建Node节点，把Node节点存储到数组中，如果有元素，则迭代链表(红黑二叉树)，如果存在此key,默认更新value,不存在则把新构建的Node存储到链表的尾部。
• 查找：同上，获取key的hashcode，通过hashcode取模数组的长度，获取要定位元素的坐标，然后迭代链表，进行每一个元素的key的equals对比，如果相同则返回该元素。

HashMap在相同元素个数时，数组的长度越大，则Hash的碰撞率越低，则读取的效率就越高，数组长度越小，则碰撞率高，读取速度就越慢。典型的空间换时间的例子。

Node类型：
HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, size, threshold, loadFactor。

table是一个Node[]数组类型，而Node实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Node数组中的。

size是HashMap的大小，它是HashMap保存的键值对的数量。

threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。

loadFactor就是加载因子。

要想理解HashMap，首先就要理解基于Node实现的“拉链法”。

Java中数据存储方式最底层的两种结构，一种是数组，另一种就是链表，数组的特点：连续空间，寻址迅速，但是在刪除或者添加元素的时候需要有较大幅度的移动，所以查询速度快，增刪较慢。而链表正好相反，由于空间不连续，寻址困难，增刪元素只需修改指針，所以查询速度慢、增刪快。有沒有一种数组结构來综合一下数组和链表，以便发挥它们各自的优势？答案是肯定的！就是：哈希表。哈希表具有较快（常量级）的查询速度，及相对较快的增刪速度，所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”，我們可以理解为“链表的数组”，如下图：

图中，我们可以发现哈希表是由数组+链表組成的，一个长度为16的数组中，每個元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢？
一般情況是通过hash(key)获得，也就是元素的key的哈希值。如果hash(key)值相等，则都存入该hash值所对应的链表中。它的內部其实是用一個Node数组來实现。

所以每个数组元素代表一个链表，其中的共同点就是hash(key)相等。

HashMap遍历方式：

1.遍历HashMap的键值对

第一步：根据entrySet()获取HashMap的“键值对”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。

2.遍历HashMap的键

第一步：根据keySet()获取HashMap的“键”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。

3.遍历HashMap的值

第一步：根据value()获取HashMap的“值”的集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。

另外，推荐大家看一篇https://www.jianshu.com/p/b2d611c01bf3 HASHMAP源码分析更深入理解。

LinkedHashMap实现类：

HashSet有一个LinkedHashSet子类，HashMap也有一个LinkedHashMap子类；LinkedHashMap使用双向链表来维护key-value对的次序。
LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能；但是因为它以链表来维护内部顺序，所以在迭代访问Map里的全部元素时有较好的性能。迭代输出LinkedHashMap的元素时，将会按照添加key-value对的顺序输出。
本质上来讲，LinkedHashMap=散列表+循环双向链表

TreeMap：

TreeMap排序方式

TreeMap有两种排序方式，和TreeSet一样。

自然排序：TreeMap的所有key必须实现Comparable接口，而且所有的key应该是同一个类的对象，否则会抛出ClassCastException异常。

定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序。

TreeMap中判断两个元素key、value相等的标准

类似于TreeSet中判断两个元素相等的标准，TreeMap中判断两个key相等的标准是：两个key通过compareTo()方法返回0，TreeMap即认为这两个key是相等的。

TreeMap中判断两个value相等的标准是：两个value通过equals()方法比较返回true。

注意：如果使用自定义类作为TreeMap的key，且想让TreeMap良好地工作，则重写该类的equals()方法和compareTo()方法时应保持一致的返回结果：两个key通过equals()方法比较返回true时，它们通过compareTo()方法比较应该返回0。如果两个方法的返回结果不一致，TreeMap与Map接口的规则就会冲突。

除此之外，与TreeSet类似，TreeMap根据排序特性，也添加了一部分新的方法，与TreeSet中的一致。可以参考前面的文章。

TreeMap的本质：

红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接*衡的二叉树。

由于红黑树这种结构太复杂，不是三言两句就能介绍的，所以推荐一个文章：http://www.cnblogs.com/skywang12345/p/3245399.html

Map实现类的性能分析及适用场景

HashMap与Hashtable实现机制几乎一样，但是HashMap比Hashtable性能更好些。
LinkedHashMap比HashMap慢一点，因为它需要维护一个双向链表。
TreeMap比HashMap与Hashtable慢（尤其在插入、删除key-value时更慢），因为TreeMap底层采用红黑树来管理键值对。
适用场景：
一般的应用场景，尽可能多考虑使用HashMap，因为其为快速查询设计的。
如果需要特定的排序时，考虑使用TreeMap。
如果仅仅需要插入的顺序时，考虑使用LinkedHashMap。

以上就是集合Map的内容，介绍地比较粗糙，感兴趣的话可以自己看源码深入了解其内部的结构。

参考自：https://www.jianshu.com/p/0580eb808eea