集合大家族概述

1、集合分类

Java集合类主要由两个根接口Collection和Map派生出来的。

Collection派生出了三个子接口：List、Set、Queue，因此Java集合大致也可分成List、Set、Queue、Map四种接口体系。

图中，List代表了有序可重复集合，可直接根据元素的索引来访问；

Set代表无序不可重复集合，只能根据元素本身来访问；

Queue是队列集合；

Map代表的是存储key-value对的集合，可根据元素的key来访问value。

2、 List、Set、Queue、Map 的区别

• List：存储的元素是有序的、可重复的

• Set：存储的元素是无序的、不可重复的

• Queue：按特定的排队规则来确定先后顺序（默认先进先出），存储的元素是有序的、可重复的

• Map：存储键值对（key-value）类型的数据，key 是无序的、不可重复的，value 是无序的、可重复的，每个键只能映射到一个值

3、集合框架的底层数据结构

List

• Arraylist： Object[] 数组
• Vector：Object[] 数组
• LinkedList： 双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）

Set

• HashSet：基于 HashMap 实现的，底层采用 HashMap 来保存元素
• LinkedHashSet：LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的
• TreeSet: 红黑树（自平衡的排序二叉树）

Queue

• PriorityQueue：Object[] 数组实现的二叉堆
• ArrayQueue：Object[] 数组 + 双指针

Map

• HashMap： JDK1.8 之前 HashMap 由数组+链表组成，数组是 HashMap 的主体，链表则是为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间 （注意：将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）
• Hashtable： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap： 红黑树（自平衡的排序二叉树）
• LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是由数组和链表组成。另外，LinkedHashMap 在上述结构的基础上，还增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序（指在插入数据时，数据在集合中的存储顺序与插入顺序一致），同时通过对链表进行相应的操作，实现了访问顺序相关逻辑（指在插入后你随机访问了某个元素，那么这个元素则会排列到集合的最后一位）

关于LinkedHashMap的访问顺序测试代码：

public class MapTest {
    public static Map<String,String> orderMap(){
         Map<String,String> linkedHashMap = new LinkedHashMap<String,String>(0,1.6f,true);

        // 数据插入
        linkedHashMap.put("key_1", "value_11111");
        linkedHashMap.put("key_2", "value_22222");
        linkedHashMap.put("key_3", "value_33333");
        linkedHashMap.put("key_4", "value_44444");
        linkedHashMap.put("key_5", "value_55555");

        /**
         * 遍历打印Entry对象
         * 注意：此时是程序开始的第1次数据打印
         */
        Set<Entry<String,String>> entrySet = linkedHashMap.entrySet();
        for(Entry<String,String> entry : entrySet){
            System.out.println("key:"+entry.getKey()+";  Value: "+entry.getValue());
        }

        System.out.println("--------------------------------------------");
        return linkedHashMap;
    }

    public static void main(String[] args) {
        Map<String, String> orderMap = orderMap();

        // 随机调用数据中的一个元素
        orderMap.get("key_3");

        /**
         * 遍历打印Entry对象
         * 注意：此时是程序开始的第2次数据打印
         */
        Set<Entry<String,String>> entrySet = orderMap.entrySet();
        for(Entry<String,String> entry : entrySet){
            System.out.println("key:"+entry.getKey()+";  Value: "+entry.getValue());
        }
    }
}

输出结果：

key:key_1;  Value: value_11111
key:key_2;  Value: value_22222
key:key_3;  Value: value_33333
key:key_4;  Value: value_44444
key:key_5;  Value: value_55555
------------------------------
key:key_1;  Value: value_11111
key:key_2;  Value: value_22222
key:key_4;  Value: value_44444
key:key_5;  Value: value_55555
key:key_3;  Value: value_33333

4、线程安全的集合有哪些？线程不安全的呢？

线程安全的：

• Vector：比Arraylist多了个同步化机制
• Stack：栈，也是线程安全的，继承于Vector
• Hashtable：比HashMap多了个线程安全
• ConcurrentHashMap:是一种高效但是线程安全的集合

线性不安全的：

• Arraylist

• LinkedList

• HashSet

• TreeSet

• HashMap

• TreeMap

5、总结

本节主要对集合做了一个全面又简单的概述：

• 首先介绍了集合主要分为4类：List、Set、Queue、Map （重点，必须掌握）

• 然后介绍了4中集合之间的区别 （重点，必须掌握）

• 接着又简单介绍了常用集合的底层数据结构

• 最后介绍了哪些集合是线程安全的，哪些是非线程安全的 （重点，必须掌握）

本节只是预热，后面将会介绍每种集合的底层原理与常见面试题！