集合类简述

在没有集合类之前，实际上在JAVA语言里已经有一种方法可以存储对象，那就是数组。数组不仅可以存放基本数据类型也可以容纳属于同一种类型的对象。数组的操作是高效率的，但也有缺点。比如数组的长度是不可以变的，数组只能存放同一种类型的对象（或者说对象的引用）。

为了使程序方便地存储和操纵数目不固定的一组数据，JDK中提供了Java集合类，所有Java集合类都位于Java.util包中，与Java数组不同，Java集合不能存放基本数据类型数据，而只能存放对象的引用。

集合特点

集合类的特点有三个：

第一点，集合类这种框架是高性能的。对基本类集（动态数组，链接表，树和散列表）的实现是高效率的。一般人很少去改动这些已经很成熟并且高效的APl；

第二点，集合类允许不同类型的集合以相同的方式和高度互操作方式工作；

第三点，集合类容易扩展和修改，程序员可以很容易地稍加改造就能满足自己的数据结构需求。

集合分类

Java中的集合类可以分为两大类：一类是实现Collection接口；另一类是实现Map接口。

Collection是一个基本的集合接口，Collection中可以容纳一组集合元素（Element）。

Collection接口中定义了一些操作集合的API：

Collection有两个重要的子接口List和Set，它们都有各自经常使用的实现类，关系如下：

Map没有继承Collection接口，与Collection是并列关系。Map提供键（key）到值（value）的映射。一个Map中不能包含相同的键，每个键只能映射一个值。

Map中也提供了一些操作Map的API：

Map接口的一些常用实现类如下：

List

List表达一个有序的集合，List中的每个元素都有索引，使用此接口能够准确的控制每个元素插入的位置。用户也能够使用索引来访问List中的元素，List类似于Java的数组。

List接口有两个经常使用的实现类，ArrayList和LinkedList。还有一个实现类Vector，不过实际开发中很少用。它们之间的区别为：

• ArrayList的底层数据结构是一个数组，查询通过数组下标查询，查询速度快，增删慢，线程不安全。
• LinkedList的底层数据结构是一个链表，增删元素快，查询慢，线程不安全。
• Vector的底层数据结构也是一个数组，查询速度快。它的方法上加了synchronized关键字，所以它是线程安全的，但也因此，它的效率很低，几乎已经被淘汰了。

适用场景分析：当需要对数据进行对此访问的情况下选用ArrayList，当需要对数据进行多次增加删除修改时采用LinkedList。

Set

Set接口的特点是不能包含重复的元素。对Set中任意的两个元素element1和element2都有elementl.equals(element2)= false。另外，Set最多有一个null元素。

Set接口常用的两个实现类是HashSet和TreeSet，两者的区别如下：

• HashSet底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性。
• TreeSet底层数据结构采用红黑树来实现，元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法；

适用场景分析：HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。为快速查找而设计的Set，我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。

此外，还有一种Set类型，LinkedHashSet，它是HashSet的子类，底层数据结构采用链表+哈希表，链表保证元素的添加顺序，哈希表保证元素的唯一性。

延伸一个面试题：HashSet是如何保证元素的唯一性？

当调用add()方法向集合中存入对象的时候，首先会使用 hash() 函数生成一个 int 类型的 hashCode 散列值，然后与已经存储的元素的 hashCode 值作比较，如果 hashCode 值不相等，则所存储的两个对象一定不相等，此时把这个新元素存储在它的 hashCode 位置上；如果 hashCode 相等，存储元素的对象还是不一定相等，此时会调用 equals() 方法判断两个对象的内容是否相等，如果 equals() 返回true，则是同一个对象，无需存储；如果 equals() 返回 false，那么就是不同的对象，就需要存储，不过由于 hashCode 相同，HashSet会以链式结构将两个对象保存在同一位置，这将导致性能下降，因此在编码时应避免出现这种情况。

List与Set选型

List与Set都是存储对象的，那我们实际开发中应该如何选择呢？可以参考下图：

Map

Map用于保存具有映射关系的数据，Map里保存着两组数据：key和value，它们都可以使任何引用类型的数据，但key不能重复。所以通过指定的key就可以取出对应的value。

Map接口有四个比较重要的实现类，分别是HashMap、LinkedHashMap、TreeMap和HashTable。它们的区别如下：

• HashMap的key值可以为null，但只能有一个key为null；它是线程不安全的，如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
• LinkedHashMap继承自HashMap，它主要是用链表实现来扩展HashMap类，HashMap中条目是没有顺序的，但是在LinkedHashMap中元素既可以按照它们插入的顺序排序，也可以按它们最后一次被访问的顺序排序。
• TreeMap基于红黑树数据结构的实现，键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap，同时实现了接口NavigableMap，而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口，使用它可以确保图中的条目是排好序的。
• Hashtable和HashMap很类似，它也是一个散列表，存储的内容是键值对映射，不同之处在于，Hashtable是继承自Dictionary的，Hashtable中的函数都是同步的，这意味着它也是线程安全的，另外，Hashtable中key和value都不可以为null。

在实际使用中，如果更新时不需要保持元素的顺序，就使用HashMap，如果需要保持元素的插入顺序或者访问顺序，就使用LinkedHashMap，如果需要使图按照键值排序，就使用TreeMap。

遍历Map的四种方式

Map不同于List和Set，它存储的是key-value的键值对，不能像List和Set那样直接使用 for 循环遍历，可以通过下面四种方式遍历Map：

必问面试题：HashMap的底层实现

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。 只是在JDK1.8中，链表长度大于8的时候，链表会转成红黑树。

在调用 HashMap 的 put 方法添加元素时，会对key的hashCode()做hash运算，计算index; 如果没碰撞直接放到bucket里； 如果碰撞了，以链表的形式存在buckets后； 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)； 如果节点已经存在就替换old value(保证key的唯一性) 如果bucket满了(超过load factor*current capacity)，就要resize。

在调用 HashMap 的 get 方法获取元素时，会对key的hashCode()做hash运算，计算index; 如果在bucket里的第一个节点里直接命中，则直接返回； 如果有冲突，则通过key.equals(k)去查找对应的Entry。

上面只是简单的说了下 HashMap 在 put 和 get 时的主要过程，后期我会单独开一篇文章，根据 HashMap 的源码来说明它的具体原理。