集合

集合是java中的一个容器，可以在里面存放数据，容量可以发生改变

从集合框架结构可以分析得知：
1、集合主要分为Collection和Map两个接口
2、Collection又分别被List和Set继承
3、List被AbstractList实现，然后分为3个子类，ArrayList，LinkList和Vector
4、Set被AbstractSet实现，又分为2个子类，HashSet和TreeSet
5、Map被AbstractMap实现，又分为2个子类，HashMap和TreeMap
6、Map被Hashtable实现

List

是一个有序集合，可以放重复的数据

ArrayList

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量，这可以减少递增式再分配的数量

LinkedList

LinkedList是采用双向链表实现的
LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性。
LinkedList不是线程安全的，如果想使其变成线程安全，可以调用静态类Collections类中的synchronizedList方法

Set

是一个无序集合，不允许放重复的数据

HashSet

HashSet是哈希表结构，主要利用HashMap的key来存储元素
HashSet实现Set接口，底层由HashMap来实现，新增元素相当于HashMap的key，value默认为一个固定的Object。HashSet相当于一个阉割版的HashMap

HashSet具有如下特点：

• 不允许出现重复因素

• 允许插入Null值

• 元素无序（添加顺序和遍历顺序不一致）

TreeSet

TreeSet是树结构，每一个元素都是树中的一个节点，插入的元素都会进行排序
从名字上可以看出，TreeSet的实现和树结构有关。与HashSet集合类似，TreeSet也是基于Map来实现，与HashSet不同的是，TreeSet具有排序功能，分为自然排序和自定义排序两类，默认是自然排序。它继承自AbstractSet，实现了NavigableSet, Cloneable, Serializable接口。

具有如下特点：

• 对插入的元素进行排序，是一个有序的集合

• 允许插入Null值

• 不允许插入重复元素

Map

是一个无序集合，集合中包含一个键对象，一个值对象，键对象不允许重复，值对象可以重复

HashMap

HashMap 主要用来存放键值对，它基于哈希表的Map接口实现

HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

HashMap 特点：

• 存储无序的。

• 键和值位置都可以是 null，但是键位置只能存在一个 null。

• 键位置是唯一的，是底层的数据结构控制的。

• jdk1.8 前数据结构是链表+数组，jdk1.8 之后是链表+数组+红黑树。

• 阈值（边界值）> 8 并且数组长度大于 64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

TreeMap

基于红黑树(Red-Black tree)的 NavigableMap实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法

TreeMap是一个基于key有序的key value散列表。

• map根据其键的自然顺序排序，或者根据map创建时提供的Comparator排序
• 不是线程安全的
• key 不可以存入null
• 底层是基于红黑树实现的

集合与数组的区别

• 数组特点：类型固定，长度固定

• 集合特点：类型不固定，长度也不固定，随意存放任何数据