day16
集合遍历的三种方式
- 迭代器
- 增强for循环
- foreach循环
迭代器
迭代器代码的原理如下：
- 当调用iterator()方法获取迭代器时，当前指向第一个元素
- hasNext()方法则判断这个位置是否有元素，如果有则返回true，进入循环
- 调用next()方法获取元素，并将当月元素指向下一个位置，
- 等下次循环时，则获取下一个元素，依此内推
增强for循环
增强for不适用于要对集合元素进行修改的操作
可以遍历集合和数组
- 遍历集合时，底层是迭代器
- 遍历数组时，底层就是普通的for循环
foreach遍历
foreach方法的参数是一个函数式接口Consumer所以可用lambda表达式简化匿名内部类book
接口里面有一个accept方法，方法的形参就是集合中的每一个元素
list.forEach((String s )->{System.out.println(s)});
list.forEach(( s ->System.out.println(s));
List集合
list集合特有方法
| 方法名 | 说明 |
|---|---|
| void add(int index,E element) | 在此集合中的指定位置插入指定的元素 |
| E remove(int index) | 删除指定索引处的元素，返回被删除的元素 |
| E set(int index,E element) | 修改指定索引处的元素，返回被修改的元素 |
| E get(int index) | 返回指定索引处的元素 |
List系列集合特点
有序，可重复，有索引
ArrayList和LinkedList
ArrayList：数组链表
LinkedList：双向链表
适合使用队列和栈的操作，适用于对首尾进行操作
Set集合特点
HashSet、TreeSet：无序，不重复，无索引
LinkedHashSet：有序、不重复、无索引
set集合与collection集合拥有一样的方法，没有增加新方法
HashSet底层原理
哈希值
- 就是一个int类型的数值，Java中每个对象都有一个哈希值
- Java中的所有对象都可以调用Objective类提供的hashCode方法，返回该对象自己的哈希值
对象哈希值的特点
- 同一个对象的哈希值永远不会变多次调用hashCode（）返回的值不会变
- 不同的对象，他们的哈希值一般不相同，但也有可能会相同（哈希碰撞）
HashSet底层
- 基于哈希表实现
- 哈希表是一种增删改查数据，性能都较好的数据结构
哈希表
- JDK8之前，哈希表 = 数组+链表
- JDK8之后，哈希表 = 数组+链表+红黑树
JDK8之前，哈希表 = 数组+链表实现
创建一个默认长度为length的数组，默认加载因子为0.75，数组名table（默认因子的作用是用来扩容的，当集合里的元素添加到length*默认因子个数时，数组扩容2倍）
- 使用元素的哈希值对数组长度求余计算出应存入的位置
- 判断当前位置是否为null，如果是null直接存入
- 如果不为null，表示有元素，则调用equals方法比较，相等，则不存；不相等，则存入数组
- JDK8之前，新元素存入数组，占老元素位置，老元素挂下面
- JDK8之后，新元素直接挂老元素下面
为什么添加的元素无序，不重复，无索引？
添加数据的顺序和取元素的顺序不一致
调用equals方法比较，相等，则不存；
因为存的位置是通过计算来存的，所以不能确定索引
JDK8之后，哈希表 = 数组+链表实现+红黑树
JDK8之后，当链表长度超过8，且数组长度>=64,自动将链表转换为红黑树
数据结构-树
二叉树：
每个节点存值：父节点地址、左子节点地址、右子节点地址
度：每个节点的子节点数量
树高：树的总层数
根节点：最顶层的节点
二叉查找树（二叉排序树）：
小的存左边，大的存右边，一样的不存（左子节点<父节点<右子节点）
平衡二叉树
-
在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查询数据的性能
-
红黑树，就是可以自动平衡的二叉树
-
红黑树是一种增删改查都比较高效的数据结构
红黑树
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色的。
- 每个叶子节点（NIL节点，空节点）是黑色的。
- 如果一个节点是红色的，则其子节点必须是黑色的。
- 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
深入理解HashSet集合去重复的机制
HashSet集合默认不能对内容一样的两个对象去重
因为两个对象的内容一样但是哈希值不一定一样
可以利用重写hashCode和equals方法去重
重写hashCode方法之后，利用属性值计算哈希值，这样内容一样的对象的hashCode就会一样
如果希望Set集合认为2个内容一样的对象是重复的，必须重写对象的hashCode和equals方法，没重写之前是用地址值比较，重写之后利用属性值比较
LinkedListSet底层原理
- 依旧是基于哈希表（数组+链表实现+红黑树）实现的
- 但是，他的每个元素都额外的多了一个双链表的机制记录它前后元素的位置
TreeSet
- 特点：不重复、无索引、无序（添加顺序和打印顺序不以言）可排序（默认升序，按照元素的大小，由小到大排序）
- 底层数据结构是红黑树
TreeSet排序规则
TreeSet集合的内部排序机制有两种方式：自然排序和定制排序。
自然排序是指根据元素的自然顺序来排序，例如整数按照大小排序，字符串按照字典序排序。自然排序要求元素实现Comparable接口，并重写compareTo方法。
定制排序是指根据提供的比较器来排序，例如按照元素的长度或者其他属性排序。定制排序要求创建一个实现Comparator接口的类，并重写compare方法2。然后在创建TreeSet集合时，传入该比较器的实例。
为什么Comparable接口重写compareTo方法里this.属性-object.属性是按照升序排序？
并不是重写了方法this.属性-object.属性就是按照升序排序
compareTo方法只返回三个值正数 0 和负数，排序时，根据compareTo的返回值来进行指定排序规则，具体规则得看集合或者方法的具体实现方式。
集合的并发修改异常
- 使用迭代器遍历集合时，又同时在删除集合中的数据，程序就会出现并发修改异常的错误
- 由于增强for循环遍历集合就是迭代器遍历集合的简化写法，因此，使用增强for循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误
怎么保证遍历集合同时删除数据时不出bug？
-
使用迭代器遍历集合，但使用迭代器自己的删除方法删除数据即可
-
如果用for循环遍历时：可以倒着遍历并删除；或者从前往后遍历，但删除元素后做i--操作