集合

要想深刻理解集合知识，必须明确“集合”的存在是为了解决什么样的问题？

如何解决该类问题？在将大问题细分的过程中，“集合”为了一一解决小问题，又一步步细分成哪些小知识，他们之间构成怎样的逻辑关系？

集合--存在的意义？

O-O思想中，万物皆对象。集合的意义就是： 对对象的存储。

区别于Array, 集合更强大，体现在,集合是动态的，而Array是静态的

集合的第一次划分

Collection和Map的区别在于容器中每个位置保存的元素个数:

1) Collection 每个位置只能保存一个元素(对象)

2) Map保存的是"键值对"，就像一个小型数据库。我们可以通过"键"找到该键对应的"值"，键值都可以是任何应用类型的数据

Collection

1. Interface Iterable

迭代器接口，Collection接口的父接口，在Collection这一房份，都实现了Iterable接口。都可以通过iterator()方法创建迭代器对象，进而遍历集合

2. Collection

该房份的第一代创始人，祖先。 是一个接口，只提供规范定义，不能被实例化。意义就是代表一组Object对象的集合

2.1 List

List接口，解决数组的局限性，其最接近数组。

特点： 元素有序且可重复，每个元素都有其对应的顺序索引

2.1.1 类 ArrayList

本质上是对象引用的一个“变长”数组

2.1.2 类LinkedList

双向链表，内部没有声明数组，而是定义了Node类型的first和last， 用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基本结构。Node除了保存数据，还定义了两个变量： prev变量记录前一个元素的位置 ,next变量记录下一个元素的位置

2.1.3 类Vector

大多数操作与ArrayList 相同，区别之处在于Vector是线程安全的。

2.1.4 类Stack

Vector的子类，模拟“栈”这种数据结构。

List三个实现类的特点：

数组方便遍历查找 ---> ArrayList

链表方便增删Node---> LinkedList

为了线程安全--->vector

2.2 Queue

集合的队列实现： 先进先出，不予许随机访问队列中的元素

2.2.1 PriorityQueue

以自定义的优先级作为先后，而不以进入Queue的顺序作为先后

2.2.2 Deque

接口，是一个双端队列：两端都可以实现进出操作，所以它可以被改造成栈或者队列

2.2.3 ArrayDeque

是一个基于数组的双端队列，和ArrayList类似，它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素，当集合元素超出该数组的容量时，系统会在底层重新分配一个Object[]数组来存储集合元素

2.3 set 接口

接口，元素无序，不可重复

使用equals()方法判断元素是否相等

2.3.1 HashSet 类

Set的典型实现，拉链法数据结构

HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除 性能。 其中hashCode() 充当hash函数，计算出元素的hashCord值作为下标。 使用equals()判断元素值是否相等，进而决定添加是否成功。

原则：相等的对象必须具有相等的散列码

2.3.2 LinkedHashSet 类

HashSet的子类，在HashSet的数据结构基础上，增加双向链表将元素按照插入顺序连接。增删性能降低，但迭代访问元素性能很高

2.3.3 SortedSet 接口

此接口主要用于排序操作，即实现此接口的子类都属于排序的子类

2.3.4 TreeSet

TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态

底层使用红黑树结构存储数据，两种排序方法：自然排序，定制排序

2.3.5 EnumSet

EnumSet是一个专门为枚举类设计的集合类，EnumSet中所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显式、或隐式地指定。EnumSet的集合元素也是有序的，它们以枚举值在Enum类内的定义顺序来决定集合元素的顺序

Set子接口子类的特点：

1.HashSet： 将哈希表原理应用在集合中

2.LinkedHashSet: 在HashSet上增加双向链表，将元素按插入顺序连接，遍历更方便

3.SortSet接口： 实现此接口的子类都属于排序的子类

4.TreeSet实现了SortSet接口：底层红黑树，确保元素处于排序状态

5.EnumSet: 元素皆为统一类的枚举对象，实现了排序

Map

意义：实现两组对象之间的映射关系

特点： 1.Map中的键和值都可以是对象.一个键只对应唯一的值（映射）

1. HashMap

1.1是什么：

每一个键值对作为一个实体，在存储中视为Node.

将Key作为输入，应用HashSet的实现方法，构建Hash表，只不过存储的是键值对实体. HashMap的键和值均可以使用null

1.2 key-value：

1.Key构成的集合是Set： 无序的，不可重复的。所以，key所在的类要重写：equals(), 和hashCode()

2. Vaule构成的集合是Collection: 无序，可以重复的。所以value所在的类要重写：equals()

1.3 数据结构--->Node数组+Node链

1.创建长度为Capacity的Entry数组。（Capacity称为容量）

2.数组中可以存放元素的位置称为“桶” (bucket)，数组元素有下标，可以快速索引

3.bucket中存放实体Node,因为Node带有引用变量，所以数组中的元素可以作为链表的head

1.4 添加元素entry1(key , value)：

1. 计算entry1中key的哈希值(根据 key所在类的hashCode()计算得到)，此哈希值经过处理以后，得到在底层Entry[]数组中要存储的位置i。

2.如果位置i上没有元素，则entry1直接添加成功。

3.如果位置i上 已经存在entry2(或还有链表存在的entry3，entry4)，则需要通过循环的方法，依次 比较entry1中key和其他的entry。

4.如果彼此的Hash值不同，则直接添加成功

5.如果Hash值相同，继续比较二者是否equals

6.如果返回值为true，则使用entry1的value 去替换equals为true的entry的value

7.如果遍历一遍以后，发现所有的equals返回都 为false,则entry1仍可添加成功。entry1指向原有的entry元素。

注意点：

1.形成链表结构时，新添加的key-value对在链表的尾部（七上八下）

2.当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置 上的所有key-value对使用红黑树进行存储。

总结：1.是否已经存在元素 2.Hash值 3.key对象

1.5 扩容

临界值：Capacity*loadFactor  达到临界值时，数组大小扩大到两倍，Capacity*2.    数组大小改变后，需要重新计算每个元素的位置，这个过程非常消耗性能，所以往往要恰当的预设元素的个数来提高性能。

1.6 树形化

当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有 达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后， 下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。

2.LinkedHashMap

同LinkedHashSet的功能

3.TreeMap

同TreeSet的功能，是在Key上进行排序

4.Hashtable

功能类似于HashMap，但是不能使用空值，HashTable是线程安全的

5.Properties

是Hashtable的子类，用于处理属性文件，键值都是String类型

存取数据时，建议使用setProperty(String key,String value)方法和 getProperty(String key)方法

工具类（注意： 加了s）

Collections

Collections 是一个操作 Set、List 和 Map 等集合的工具类

Collections 中提供了一系列静态的方法对集合元素进行：排序、查询和修改等操作， 还提供了对集合对象设置不可变、对集合对象实现同步控制等方

Arrays

操作数组的工具类