Java集合是面试中经常被问到的一块内容，很多人在这个地方被面试官吊打。Java集合类被定义在java.util包中，主要有四种集合，分别是List、Queue、Set和Map，每种集合分类如下图所示

List集合

List是一种在开发中比较常用的集合类，作为有序的Collection的典范，分别有如下的三个实现类

ArrayList

Vector

LinkedList

从名字可以看出三个实现类分别都代表什么。

ArrayList

ArrayList底层是通过数组实现的，既然是数组那么它就有数组带给它的属性，增加和删除速度慢，但是查询速度快，是线程不安全的。

ArrayList的缺点是元素必须是连续的存储，当需要在ArrayList中间插入一个或者删除一个元素的时候，需要将待插入或者删除节点之后的所有的元素进行移动。所以ArrayList不适合随机插入和删除操作。适合的操作是遍历和随机查找。可以通过下标直接找到对应的元素。

ArrayList 不需要在定义的时候指定数组的长度，而是在数据存储长度不足的时候，ArrayList会创建一个新的更大的数组并且将数组中已经有的数据复制到新的数组中。

Vector

Vector基于数组实现，增加和删除速度慢，查询速度快，是线程安全的。

Vector的数据结构与ArrayList的结构是一样的，都是基于数组的方式进行实现的。与ArrayList不同的是Vector支持线程同步操作，也就是说同一时刻只允许一个线程对Vector进行写操作，这样保证了在多线程的环境下的数据一致性问题，但是需要对Vector进行反复的加锁释放锁的操作，所以Vector在读写操作上的速度的要比ArrayList低。

LinkedList

LinkedList是基于双向链表，增加和删除的速度快，查询的速度慢，是线程不安全的。

LinkedList采用的双向链表的数据结构进行存储元素，在对LinkedList进行插入和删除操作的时候，只需要在对应的节点上插入或者删除对应的元素即可，并且将节点的指针进行修改就可以了，数据变动是最小的，这样做的话插入和删除的效率很高。由于是链表数据结构，在随机访问的时候，需要从链表的头部一直遍历到对应的节点才能找到对应的元素，所以随机访问的速度较慢。除此之外，LinkedList 还提供了在List接口中未定义的方法，用来操作链表头部和尾部的元素，所以有的时候也可以当做堆栈、队列或者双向队列来使用。

Queue

队列也是一种特殊的线性表，它只允许在两端进行操作，插入或者取出，不允许操作中间的数据。比如只允许在对头出队，队尾入队。这样就具有先进先出的特性(first in first out-FIFO)。就像排队买东西一样，不允许插队，先排先买。

队列分为单向队列(有序队列)，就是上面所说的排队模型，先进先出的操作，只允许一边进，另一边出，比如Java中的Queue。另外一种就是双端队列，两端都可以进行进出操作。比如java中的Deque。

Queue是队列结构，在Java中常见的几种队列结构如下

• ArrayBlockingQueue：基于数组数据结构实现的有界阻塞队列形式
• LinkedBlockingQueue：基于链表数据结构实现的有界阻塞队列。
• PriorityBlockingQueue：支持优先级排序的无界阻塞式队列形式。
• DelayQueue：支持延迟操作的无界阻塞队列
• SynchronousQueue：用于线程同步的阻塞队列
• LinkedTransferQueue：基于链表实现的无界阻塞队列
• LinkedBlockingDeque：基于链表实现的双向阻塞队列

import java.util.LinkedList;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 有界队列的基本实现
 */
public class MyQueue {

    private LinkedList<Object> list = new LinkedList<>();

    private AtomicInteger count = new AtomicInteger(0);

    private final int minSize = 0;

    private int maxSize;

    private final Object lock = new Object();

    public MyQueue(int size) {
        this.maxSize = size;
    }

    public void put(Object obj) {
        synchronized (lock) {
            while (count.get() == this.maxSize) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            list.add(obj);
            count.incrementAndGet();
            System.out.println("元素加入：" + obj);

            lock.notify();
        }
    }

    public Object take() {
        Object obj = null;
        synchronized (lock) {
            while (count.get() == this.minSize) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            obj = list.removeFirst();
            count.decrementAndGet();
            System.out.println("元素拿出：" + obj);

            lock.notify();
        }
        return obj;
    }

    public static void main(String[] args) {
        final MyQueue mq = new MyQueue(4);
        System.out.println("初始化四个元素");
        mq.put("aa");
        mq.put("bb");
        mq.put("cc");
        mq.put("dd");
        System.out.println();

        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("小明开始放元素了");
                mq.put("ee");
                mq.put("ff");
            }
        });
        t1.start();

        System.out.println();
        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("小王开始拿元素了");
                Object o1 = mq.take();
                Object o2 = mq.take();
            }
        });


        try {
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        t2.start();

        try {
            TimeUnit.SECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println();
        System.out.println("队列中的元素：");
        for (Object obj : mq.list) {
            System.out.println(obj);
        }
    }

}

Set

Set核心是适用于存储无序且值不相等的元素的存储，对象的相等性质是通过比较对象上的HashCode是否相同。Java中依据对象内存地址计算出对象的HashCode值。如果比较两个对象是否相等，就必须同时覆盖对象的hashCode()方法和equals方法，并且hashCode方法和equals方法的返回值必须是相同的，才能保证对象相等。

HashSet

HashSet 存放的是散列值，是按照元素的散列值来存取元素，元素的散列值是通过元素的hashCode方法计算得到的，HashSet首先判断两个元素的散列值是否相等。如果相等，则通过equals来比较，如果相等，则HashSet就将其视为同一个对象元素；如果equals返回的方法结果为false，HashSet就不认为是同一个对象。

TreeSet

TreeSet基于二叉树的原理实现，对象按照一定的顺序排列，每次添加一个对象都会进行排序，并且将对应的值插入到二叉树的指定位置。

Integer和String等基础对象类型可以直接根据TreeSet的默认排序方式进行存储。自定义的数据类型也是必须实现Comparable接口，并且覆盖其中的compareTo()方法才可以按照自定义的规则进行排序。

LinkHashSet

底层数据结构是使用双向链表来记录，使用LinkedHashMap存储元素，它继承了HashSet，所有的方法在操作上都与HashSet相同。所以LinkedHashSet的实现比较简单，只是简单的提供了四个构造方法，并通过传递一个标识参数调用父类构造器，在底层构造一个LinkedHashMap来记录数据访问，其他相关的操作则与其父类HashSet相同。直接调用父类的对应方法即可。

Map

Map是一组键值对的集合

HashMap

基于键的HashCode值唯一标识一条数据，同时基于键的HashCode值进行数据的存取，因此可以快速的更新和查询数据，但不能保证每次遍历的数据是相同的，HasMap的key和value允许为null。

HashMap是线程不安全的，也就是说在多线程同时写入HashMap的时候可能导致数据不一致，如果需要满足线程安全的条件，则可以使用Collection的synchronizedMap方法使得HashMap具有线程安全的能力。或者可以使用ConcurrentHashMap。

为了减少链表遍历的时候产生的开销，Java8中对于HashMap的存储结构进行了优化，将数据结构由数组+链表的形式修改为数组+链表+红黑树的结构，来提高查询的效率。如图所示。

ConcurrentHashMap

基于分段锁实现，保证线程安全操作。与HashMap不同，ConcurrentHashMap采用分段锁的思想实现并发操作，所以是线程安全的。ConcurrentHashMap由多个Segment组成，Segment的数量是所的并发度，每个Segment都继承自ReentrantLock并单独加锁，所以每次进行加锁操作时锁住的那个Segment，这样就可以保证每个Segment都是线程安全的，也就实现了全局的线程安全，如图所示。

在ConcurrentHash中有个concurrencyLevel参数表示并行级别，默认是16，也就是说ConcurrentHashMap默认由16个Segment组成，在这种情况下最多同时支持16个并发线程的读写操作。只要将它们分配到不同的Segment上就可以了。这个并行级别是在初始化的时候进行设置的，一旦初始化了就不能被修改，ConcurrentHashMap的每个Segment内部的数据结构都和HashMap是相同的。

Java8中的数据结构如下图所示。

HashTable

HashTable是遗留下来的操作，很多的功能与HashMap是一样的，不同的是它是继承自Dictionary类，并且是线程安全的，同一时刻只有一个线程能对HashTable进行操作，并发性能不如ConcurrentHashMap.

TreeMap

TreeMap基于二叉树数据结构进行存储，同时实现了SortedMap接口用来保证顺序存取，默认按照键值的升序排序，也可以使用自定义的比较器。

TreeMap常用与实现排序的映射列表，在使用TreeMap时其key必须实现Compareable接口或采用自定义的额比较器，会抛出java.lang.ClassCastException异常。

LinkedHashMap

基于HashTable的数据结构，使用链表保存插入顺序。LinkedHashMap是HashMap的子类，其内部使用链表的方式保存元素的插入操作，在通过Iterator遍历LinkedHashMap的时候，会按照元素的插入顺序进行元素访问。