集合框架之单列集合
Java中整个集合框架分为单列和双列集合。
1. 单列集合
Collection是整个单列集合的父接口，它的功能是全部单列集合都可以继承使用的。 
- List系列集合特点: 添加的元素是有序、可重复、有索引
- Set系列集合: 添加的元素是无序、不重复、无索引
1.1 Collection接口
| 方法名称 | 说明 |
|---|---|
| boolean add(E e) | 把给定的对象添加到当前集合中 |
| void clear() | 清空集合中所有的元素 |
| boolean remove(E e) | 把给定的对象在当前集合中删除 |
| boolean contains(object obj) | 判断当前集合中是否包含 |
| boolean isEmpty() | 给定的对象判断当前集合是否为空 |
| int size() | 返回集合中元素的个数/集合的长度 |
需要注意的是contains方法底层通过equals方法判断对象是否一致，如果是自定义对象没有重写equals方法，那么默认使用Object类的equals方法进行判断，而Object类的equals方法使用地址值进行比较。
2. 遍历集合
2.1 迭代器遍历
迭代器在Java中的类是Iterator，迭代器是集合专用的遍历方式：
List<Integer> list = List.of(1, 2, 5, 8, 2, 9, 3);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer next = iterator.next();
System.out.println(next);
}- 遍历完毕后，iterator指向末尾，不会复位
- 迭代器遍历时，不能用集合的方法进行增加或者删除
在遍历的时候，如果想删除元素，可以使用迭代器提供的remove()方法:
// 调用List.of得到的是不可变列表，这里不能用
List<Integer> list = new ArrayList();
list.add(1); list.add(2); list.add(5);
list.add(8); list.add(3); list.add(9);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer item = iterator.next();
if(item == 2){
iterator.remove();
}
}
System.out.println(list);2.2 List迭代器遍历
List<Integer> list = List.of(1, 2, 5, 8, 2, 9, 3);
ListIterator<Integer> listedIterator = list.listIterator();
while (listedIterator.hasNext()){
Integer item = listedIterator.next();
System.out.println(item);
}ListIterator是List特有的迭代器，遍历的时候额外提供添加和修改方法：
List<Integer> list = new ArrayList();
list.add(1); list.add(2); list.add(5);
list.add(8); list.add(3); list.add(9);
ListIterator<Integer> listedIterator = list.listIterator();
while (listedIterator.hasNext()){
Integer item = listedIterator.next();
// 删除元素
if(item == 2){
listedIterator.remove();
}
// 添加元素
if(item == 3){
listedIterator.add(10);
}
}
System.out.println(list);2.3 普通for遍历
单列集合只能实现List接口的子类才能for遍历，Set接口的不支持
List<Integer> list = List.of(1, 2, 5, 8, 2, 9, 3);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}2.4 增强for遍历
所有的单列集合和数组才能用增强for进行遍历。
List<Integer> list = List.of(1, 2, 5, 8, 2, 9, 3);
for (Integer item : list) {
System.out.println(item);
}2.5 lambda遍历
List<Integer> list = List.of(1, 2, 5, 8, 2, 9, 3);
list.forEach(System.out::println);3. List集合特有方法
List集合因为有索引，所以多了很多索引操作的方法。
| 方法名称 | 说明 |
|---|---|
| void add(int index,E element) | 在此集合中的指定位置插入指定的元素 |
| E remove(int index) | 删除指定索引处的元素，返回被删除的元素 |
| E set(int index,E element) | 修改指定索引处的元素，返回被修改的元素 |
| E get(int index) | 返回指定索引处的元素 |
特别说明的是remove()方法，出现了重载的现象，优先调用实参和形参一致的那个方法，并不会自动装箱。
4. ArrayList集合
4.1 底层原理
- ArrayList底层是数组结构的(名字叫elementData)，利用空参创建的集合，在底层创建一个默认长度为0的数组。
- 添加第一个元素时，底层会创建一个新的长度为10的数组。
此时会触发grow()方法： 
- 当数组添加满了之后，会自动扩容为1.5倍。
newCapacity的计算是在newLength()方法中实现的：
返回新数组长度15后，调用Arrays.copyOf()方法进行拷贝数据。 - 如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度以实际为准。
4.2 迭代器源码分析
在ArrayList内部有一个内部类Itr, 它就是迭代器，每次都是创建新的：
其中checkForComodification()就是检查expectedModCount和modCount是否不再相等，不相等就抛出ConcurrentModificationException异常：
5. LinkedList集合
底层数据结构是双链表，查询慢，首尾操作的速度是极快的，所以多了很多首尾操作的特有API。
| 特有方法 | 说明 |
|---|---|
| public void addFirst(E e) | 在该列表开头插入指定的元素 |
| public void addLast(E e) | 将指定的元素追加到此列表的末尾 |
| public E getFirst() | 返回此列表中的第一个元素 |
| public E getLast() | 返回此列表中的最后一个元素 |
| public E removeFirst() | 从此列表中删除并返回第一个元素 |
| public E removeLast() | 从此列表中删除并返回最后一个元素 |
5.1 内部数据结构
在LinkedList内部维护节点对象Node, 由于是双链表，所以Node对象有指向上一个和下一个的指针:
而LinkedList维护头节点和尾节点信息，在执行new LinkedList()后，first和last都为null: 
5.2 add源码分析
执行add()方法时，实际底层执行linkLast()方法： 
linkLast()方法中构造Node对象，并更新last对象信息和first对象信息：
如果last不为空，也就是不是空链表时，只更新最后一个Node的尾指针和last的引用。
6. Set集合
6.1 Set集合特点
- 无序:存取顺序不一致
- 不重复:可以去除重复
- 无索引:没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素
6.2 Set的主要实现类
Hashset:无序、不重复、无索引
LinkedHashset:有序、不重复、无索引
Treeset:可排序、不重复、无索引
7. HashSet底层原理
Hashset集合底层采取哈希表存储数据(所以就叫Hash+Set😂)。哈希表是一种对于增删改查数据性能都较好的结构。Hash表的组成：
- JDK8之前:数组+链表
- JDK8开始:数组+链表+红黑树
整个HashSet的数据结构在JDK8之后会出现上图中三种结构。
7.1 哈希值
根据hashcode方法算出来的int类型的整数。该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算。一般情况下，会重写hashcode方法，利用对象内部的属性值计算哈希值。哈希值有如下特性：
- 如果没有重写hashcode方法，不同对象计算出的哈希值是不同的。
- 如果已经重写hashcode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的。
- 在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。(哈希碰撞)
比如Byte对象，它的范围是-128-127，如果此时有200多个Byte对象，毫无疑问就会出现哈希碰撞。再比如： 
7.2 数据保存分析
- 创建一个默认长度16，默认加载因为0.75的数组，数组名table。
- 根据元素的哈希值跟数组的长度计算出应存入的位置。
- 判断当前位置是否为null，如果是null直接存入。
- 如果位置不为null，表示有元素，则调用equals方法比较属性值。
- 存入值一样:不存；存入值不一样:存入数组，形成链表。新元素保存位置：
- JDK8以前:新元素存入数组，老元素挂在新元素下面。
- IDK8以后:新元素直接挂在老元素下面
- 如果继续添加数据，达到阈值(16*0.75=12)的时候，底层数组就会发生扩容，扩容是2倍，也就是32。
- 如果添加数据多次出现哈希碰撞，达到当链表长度大于8而且数组长度大于等于64条件时，链表会转换为红黑树。
7.3 存取数据顺序不一致
首先存数据是将值进行Hash，得到hash值也就是得到数组索引值进行存放数据，不一定第一个数据的hash值就是0，但是取数据肯定是从索引0开始的。还有一个原因就是取数据的时候，如果遇到链表和红黑树，会先遍历完毕整个数据结构后，才会继续往数组后面取数据。但是我们存数据的时候不可能有连续发生哈希碰撞的情况，这就是说碰撞数据很大几率不会都在同一一个地方发生。
7.3 为何没有索引
HashSet发展这么多年，为何没有设计索引值么，主要是因为HashSet内部同时存在3种数据结构，三种数据结构的确支持索引，但是使用其中哪一个索引都不准确，不太好定义。
7.4 如何保证数据去重的
底层提供HashCode()方法和Equals()方法, HashCode()方法确保相同的数据存放在底层数组相同的位置，相同位置会使用quals方法确定数据内容是否相同，相同就不处理就使得数据不重复。因此如果存入的是自定义对象，一定要提供hashcode和equals方法
8. LinkedHashSet底层原理
LinkedHashSet是HashSet基础上实现了有序的特性，底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序。在遍历的时候直接通过双向链表进行遍历。
8. TreeSet底层原理
TreeSet特点是不重复、无索引、可排序。其中可排序:按照元素的默认规则(有小到大)排序。Treeset集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好。 
8.1 默认排序规则
- 对于数值类型:Integer，Double，默认按照从小到大的顺序进行排序。
- 对于字符、字符串类型:按照字符在ASCII码表中的数字升序进行排序。
8.2 自定义排序
- 默认排序/自然排序: Javabean类实现Comparable接口指定比较规则。
- 比较器排序: 创建TreeSet对象时候，传递比较器Comparator指定规则。
第二种方式主要是针对使用别人的代码的时候，在不能更改源码的时候，使用Comparator来实现比较规则：
TreeSet<String> treeSet = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() == o2.length()) {
return o1.compareTo(o2);
} else if (o1.length() > o2.length()) {
// 大就排在后面
return 1;
}else {
// 小就排在前面
return -1;
}
}
});
treeSet.add("2");
treeSet.add("55");
treeSet.add("4444");
treeSet.add("11");
treeSet.forEach(System.out::println);运行结果：
此时TreeSet会按照我们实现Comparator接口的逻辑进行排序，而不是按照String实现Comparable接口的逻辑进行排序。