# 前言   Java集合框架 (Java Collections Framework, JCF) 也称容器,这里可以类比 C++ 中的 STL,在市面上似乎还没能找到一本详细介绍的书籍。在这里主要对如下部分进行源码分析,及在面试中常见的问题。   例如,在阿里面试常问到的 HashMap 和 ConcurrentHashMap 原理等等。深入源码分析是面试中必备的技能,通过本文的阅读会对集合框架有更深一步的了解。 本文参考: * [CarpenterLee/JCFInternals: 深入理解Java集合框架](https://github.com/CarpenterLee/JCFInternals) * [crossoverJie/Java-Interview:👨‍🎓Java related : basic, concurrent, algorithm](https://github.com/crossoverJie/Java-Interview) * [Interview-Notebook/Java 容器.md at master · CyC2018/Interview-Notebook](https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Java%20%E5%AE%B9%E5%99%A8.md) # [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#一概述)一、概述   Java集合框架提供了数据持有对象的方式,提供了对数据集合的操作。Java 集合框架位于`java.util`包下,主要有三个大类:**Collection(接口)**、**Map(接口)**、**集合工具类**。 ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#集合框架图)集合框架图 [![](https://github.com/frank-lam/fullstack-tutorial/raw/master/notes/JavaArchitecture/assets/1535785576589.png)](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/1535785576589.png) ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#collection)Collection * `ArrayList`:**线程不同步**。默认初始容量为 10,当数组大小不足时容量扩大为 1.5 倍。为追求效率,ArrayList 没有实现同步(synchronized),如果需要多个线程并发访问,用户可以手动同步,也可使用 Vector 替代。 * `LinkedList`:**线程不同步**。**双向链接实现**。LinkedList 同时实现了 List 接口和 Deque 接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList 简直就是个全能冠军。当你需要使用栈或者队列时,可以考虑使用 LinkedList,一方面是因为 Java 官方已经声明不建议使用 Stack 类,更遗憾的是,Java 里根本没有一个叫做 Queue 的类(它是个接口名字)。关于栈或队列,现在的首选是 ArrayDeque,它有着比 LinkedList(当作栈或队列使用时)有着更好的性能。 * `Stack and Queue`:Java 里有一个叫做 Stack 的类,却没有叫做 Queue 的类(它是个接口名字)。当需要使用栈时,Java 已不推荐使用 Stack,而是推荐使用更高效的 ArrayDeque;既然 Queue 只是一个接口,当需要使用队列时也就首选 ArrayDeque 了(次选是 LinkedList )。 * `Vector`:**线程同步**。默认初始容量为 10,当数组大小不足时容量扩大为 2 倍。它的同步是通过`Iterator`方法加`synchronized`实现的。 * `Stack`:**线程同步**。继承自 Vector,添加了几个方法来完成栈的功能。现在已经不推荐使用 Stack,在栈和队列中有限使用 ArrayDeque,其次是 LinkedList。 * `TreeSet`:**线程不同步**,内部使用`NavigableMap`操作。默认元素 “自然顺序” 排列,可以通过`Comparator`改变排序。TreeSet 里面有一个 TreeMap(适配器模式) * `HashSet`:**线程不同步**,内部使用 HashMap 进行数据存储,提供的方法基本都是调用 HashMap 的方法,所以两者本质是一样的。集合元素可以为 NULL。 * `Set`:Set 是一种不包含重复元素的 Collection,Set 最多只有一个 null 元素。Set 集合通常可以通过 Map 集合通过适配器模式得到。 * `PriorityQueue`:Java 中 PriorityQueue 实现了 Queue 接口,不允许放入 null 元素;其通过堆实现,具体说是通过完全二叉树(complete binary tree)实现的**小顶堆**(任意一个非叶子节点的权值,都不大于其左右子节点的权值),也就意味着可以通过数组来作为 PriorityQueue 的底层实现。 * **优先队列的作用是能保证每次取出的元素都是队列中权值最小的**(Java 的优先队列每次取最小元素,C++ 的优先队列每次取最大元素)。这里牵涉到了大小关系,**元素大小的评判可以通过元素本身的自然顺序(natural ordering),也可以通过构造时传入的比较器**(*Comparator*,类似于 C++ 的仿函数)。 * `NavigableSet`:添加了搜索功能,可以对给定元素进行搜索:小于、小于等于、大于、大于等于,放回一个符合条件的最接近给定元素的 key。 * `EnumSet`:线程不同步。内部使用 Enum 数组实现,速度比`HashSet`快。**只能存储在构造函数传入的枚举类的枚举值**。    ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#map)Map * `TreeMap`:线程不同步,基于**红黑树**(Red-Black tree)的 NavigableMap 实现,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用 Iterator 遍历 TreeMap 时,得到的记录是排过序的。 * **TreeMap 底层通过红黑树(Red-Black tree)实现**,也就意味着`containsKey()`,`get()`,`put()`,`remove()`都有着`log(n)`的时间复杂度。其具体算法实现参照了《算法导论》。 * `HashTable`:**线程安全**,HashMap 的迭代器 (Iterator) 是`fail-fast`迭代器。**HashTable 不能存储 NULL 的 key 和 value。** * `HashMap`:线程不同步。根据`key`的`hashcode`进行存储,内部使用静态内部类`Node`的数组进行存储,默认初始大小为 16,每次扩大一倍。当发生 Hash 冲突时,采用拉链法(链表)。JDK 1.8中:**当单个桶中元素个数大于等于8时,链表实现改为红黑树实现;当元素个数小于6时,变回链表实现。由此来防止hashCode攻击。** * Java HashMap 采用的是冲突链表方式。 * HashMap 是 Hashtable 的轻量级实现,可以接受为 null 的键值 (key) 和值 (value),而 Hashtable 不允许。 * `LinkedHashMap`:**保存了记录的插入顺序**,在用 Iterator 遍历 LinkedHashMap 时,先得到的记录肯定是先插入的。也可以在构造时用带参数,按照应用次数排序。在遍历的时候会比 HashMap 慢,不过有种情况例外,当 HashMap 容量很大,实际数据较少时,遍历起来可能会比 LinkedHashMap 慢,因为 LinkedHashMap 的遍历速度只和实际数据有关,和容量无关,而 HashMap 的遍历速度和他的容量有关。 * `WeakHashMap`:从名字可以看出它是某种 Map。它的特殊之处在于 WeakHashMap 里的 entry 可能会被 GC 自动删除,即使程序员没有调用`remove()`或者`clear()`方法。 WeakHashMap 的存储结构类似于HashMap * 既然有 WeekHashMap,是否有 WeekHashSet 呢?答案是没有!不过 Java Collections 工具类给出了解决方案,`Collections.newSetFromMap(Map<E,Boolean> map)`方法可以将任何 Map包装成一个Set。 ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#工具类)工具类 * `Collections`、`Arrays`:集合类的一个工具类帮助类,其中提供了一系列静态方法,用于对集合中元素进行排序、搜索以及线程安全等各种操作。 * `Comparable`、`Comparator`:一般是用于对象的比较来实现排序,两者略有区别。 > * 类设计者没有考虑到比较问题而没有实现 Comparable 接口。这是我们就可以通过使用 Comparator,这种情况下,我们是不需要改变对象的。 > * 一个集合中,我们可能需要有多重的排序标准,这时候如果使用 Comparable 就有些捉襟见肘了,可以自己继承 Comparator 提供多种标准的比较器进行排序。 **说明**:线程不同步的时候可以通过,Collections.synchronizedList() 方法来包装一个线程同步方法 ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#通用实现)通用实现 :-: <table align="center"><tr><td colspan="2" rowspan="2" align="center" border="0"></td><th colspan="5" align="center">Implementations</th></tr><tr><th>Hash Table</th><th>Resizable Array</th><th>Balanced Tree</th><th>Linked List</th><th>Hash Table + Linked List</th></tr><tr><th rowspan="4">Interfaces</th><th>Set</th><td><tt>HashSet</tt></td><td></td><td><tt>TreeSet</tt></td><td></td><td><tt>LinkedHashSet</tt></td></tr><tr><th>List</th><td></td><td><tt>ArrayList</tt></td><td></td><td><tt>LinkedList</tt></td><td></td></tr><tr><th>Deque</th><td></td><td><tt>ArrayDeque</tt></td><td></td><td><tt>LinkedList</tt></td><td></td></tr><tr><th>Map</th><td><tt>HashMap</tt></td><td></td><td><tt>TreeMap</tt></td><td></td><td><tt>LinkedHashMap</tt></td></tr></table> **参考资料:** * [CarpenterLee/JCFInternals:深入理解Java集合框架](https://github.com/CarpenterLee/JCFInternals) * [Java基础-集合框架 - 掘金](https://juejin.im/post/5af86ac8f265da0ba063410e)