Java中的集合概述
1. 概述
Java中的集合主要有两种：
- Collection
- Map
集合的本质是用来存储批量的对象。
2. Collection接口
Collection 类是一个接口类，定义了集合中最基本的常用方法。
继承了Collection的接口类有：
- List
- Set
- Queue
实现了Collection的抽象类有：
- AbstractCollection
AbstractCollection衍生了两个子抽象类，分别是：
- AbstractList
- AbstractSet
图示如下：
我们主要还是关注下具体的实现类吧。
2.1 List
List接口有四个实现类
- LinkedList
- ArrayList
- Vector
- Stack（Vector的子类）
2.1.1 LinkedList
- 基于双向链表实现
- 支持任意性的访问，便于插入和删除，不便于遍历
- 非线程安全（即支持多个线程并发读取）
2.1.2 ArrayList
- 基于数组实现
- 初始容量是10，快要溢出时会进行动态扩容（1.5倍扩容）
- 支持任意性的访问（根据索引）
- 非线程安全（即支持多个线程并发读取）
2.1.3 Vector（基本不使用，被ArrayList取代）
- 基于数组实现
- 支持任意性的访问（根据索引）
- 线程安全（同一时刻，只能有一个线程读取Vector）
2.1.4 Stack
- 继承于Vector
- 实现了数据结构中后进先出的堆栈
- 主要方法有：
- push（）// 添加元素到栈顶
- pop（）//删除栈顶的元素
- peek（） 获取栈顶元素
- empty（） 判断是否为空
2.2 Set
Set是元素不可重复（根据元素的hashCode()和equals()方法来判断两个元素是否相同）的集合，允许null的存在，但仅能存在一个（因为set的元素不能重复）；不支持随机访问（ 无序）， 虽然Set中元素没有顺序，但是元素在set中的位置是由该元素的HashCode决定的，其具体位置其实是固定的。
2.2.1 HashSet
- 元素不可重复
- 底层是HashMap，存储的key是插入的元素，value是一个Object
- 非同步（线程不安全）
- 不保证插入顺序和读取顺序一致
2.2.2 LinkedHashSet
- 继承于HashSet
- 底层是LinkedHashMap，
- 有序（链表维护顺序），
- 非同步（线程不安全）
2.2.3 TreeSet
- 有序
- 底层是TreeMap
- 非同步（线程不安全）
- 通过compare或者comparaeTo函数来判断元素是否相等
3. Map接口
Map没有继承Collection，是多个键值对元素组成的集合，提供了键（key）到值（value）的映射，key不可重复。
3.1 HashMap
- 以哈希表的数据结构（数组+链表）实现，查找对象时通过哈希函数计算其位置，查询效率高
- 内部定义有hash表数组，通过哈希函数将元素（键值对）的哈希地址，转换为hash表数组的索引（下标）
- 如果有两个元素计算出来的索引值相同，则用链表的数据结构将两个元素串起来，此时，两个元素的hash值相同
- 线程不安全
- 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
3.2 HashTable
- 线程安全版的HashMap，一般用于多线程中
- 键值都不允许为null
- 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口
3.3 LinkedHashMap
- 继承于HashMap
- 通过链表的数据结构（ 双链表 ）来保证读取顺序和插入顺序一致
- 非线程安全
3.4 TreeMap
- 有序
- 非线程安全
- 基于红黑树实现
- 每一个key-value节点作为红黑树的一个节点。TreeMap存储时会进行排序
- 其中排序方式也是分为两种，一种是自然排序，一种是定制排序
- 自然排序： TreeMap中所有的key必须实现Comparable接口，并且所有的key都应该是同一个类的对象，否则会报ClassCastException异常。
- 定制排序： 定义TreeMap时，创建一个comparator对象，该对象对所有的treeMap中所有的key值进行排序，采用定制排序的时候不需要TreeMap中所有的key必须实现Comparable接口
- 判断元素相等的依据： 两个key通过compareTo()方法返回0，则认为这两个key相等。
3.5 WeakHashMap
- 继承于AbstractMap
- 键和值都可以是null
- 键是”弱键“
- 线程不安全
- 数据结构是哈希表（还有单项链表）