ArrayList
文章目录
- ArrayList
- 集合与数组
- ArrayList
- 集合进阶
- 集合体系结构
- Collection集合
- List集合（接口）
- 数据结构
- ArrayList集合
- LinkedList集合
- Set集合
- HashSet
- 双列集合
- 创建不可变集合
集合与数组
自动扩容
无法存储基本数据类型，只能将其变为包装类进行存储
集合与数组的区别
长度：数组长度固定
集合长度可变
存储类型：数组可以存储 基本数据类型和引用数据类型
集合只能存引用数据类型，基本数据类型需要转换为包装类存入集合
ArrayList
对象的创建
JDK7以前：
ArrayList<E> list = new ArrayList<E>();
<E> ：泛型，限定集合中存储的数据类型。
JDK7以后：
ArrayList<E> list = new ArrayList<>();
<E> ：泛型，限定集合中存储的数据类型。
注：打印对象不是地址值，而是集合中存储的数据内容，在展示时会使用[ ] 把所有的数据进行包裹
char => Character
int => Integer
集合对象的操作
list.add();//添加元素
list.remove();//删除指定元素
list.remove();//删除指定索引的元素
list.set();//修改指定索引下的元素
list.get();//获取指定索引元素
list.size();//返回集合长度
集合进阶
集合体系结构
Collection：单列集合 一次只能添加一个
Map：双列集合 一次可以添加一对（两个）
Collection集合
Collection是单列集合的顶级父接口，他的功能是全部单列集合都可以继承使用的
常见方法：
contains（）; 该方法底层是依赖equals方法进行判断是否存在的，所以如果集合中存储的是自定义对象，也想通过contains方法来判断是否包含，那么在JavaBean类中，一定要重写equals方法
Collection的遍历方式
迭代器遍历：不依赖索引
迭代器在Java中的类是Iterator，迭代器是集合专用的遍历方式
迭代器的获取：
Iterator iterator（）； 返回迭代器对象，默认指向档期集合的0索引
常用方法：
boolean hasNext();//判断当前位置是否有元素，有元素返回true，否则false
E next();//获取当前位置的元素，并将迭代器对象移项下一个位置
注:迭代器遍历完毕，指针不会复位
循环中只能用一次next方法，多次使用会导致指针越界
迭代器遍历时，不能用集合的方法进行增加，删除时只能用迭代器提供的删除方法
报错NoSuchElementException (类似于索引越界)
拓展：hasPrevious();
previous(); 倒序遍历
局限性：新创建的新集合时指针默认指向0索引，所以会出现错误
增强for遍历（foreach遍历）：
底层就是迭代器，为了简化迭代器的代码书写，JDK5出现
使用：所有的单列集合和数组才能用增强for遍历
格式：
for(数据类型 变量名：集合/数组){
sout(变量名)；
}
注：修改增强for中的变量，不会改变集合中原本的数据
Lambda表达式遍历：
得益于JDK8开始的技术Lambda表达式，提供了一种更简单，更直接的遍历集合的方式
coll.forEach(new Consumer<String>){
public void accept(String s){
sout(s);
}
}
Lambda简化：
coll.forEach(s->sout(s));
List集合（接口）
添加元素是有序、可重复、有索引
List集合有索引，多了一些索引操作的方法
细节：add(int index , E element); 原来索引上的元素会依次往后移
remove（）；优先删除索引对应的值（优先调用是参与形参一致的方法）
列表迭代器：list.listIterator();
用法与迭代器相同，在迭代是可以增加或删除元素
数据结构
计算机底层存储、组织数据的方式，是指数据相互之间事宜什么样的方式排列在一起的。数据节后是为了更方便的管理和使用数据，需要结合具体的业务场景来进行选择。一般情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
栈
特点：后进先出，先进后出（类似于弹夹）
数据进入栈模型的过程称为：压栈或进栈
数据离开栈模型的过程称为：弹栈或出栈
队列
特点：先进先出，后进后出
数据从后端进入队列模型的过程称为：入队列
数据从前端离开队列模型的过程称为：出队列
数组
特点：查询速度快，查询数据通过地址值和索引定位，查询任意数据耗时相同。（元素在内存中还是连续存储的）
弊端：删除效率低，将原始数据删除，同时后面每个数据前移
链表
有多个节点连接而成，每个节点中存储一个具体的数据和下一个节点的地址，依次连接形成链表
链表中的节点是独立的对象，在内存中时不连续的，每个节点包含数据值和下一个节点的地址
优点：增删相对数组快
弊端：链表查询慢，无论查询哪个数据都要从头开始找
拓展：双向链表
泛型
JDK5中引入的特性，可以在编译阶段 约束操作的数据类型，并进行检查
格式：<数据类型>
注意:泛型只能支持引用数据类型
指定泛型的具体类型后，传递数据时，可以传入该类型及其子类型
如果我们没有给集合指定类型，默认认为所有数据类型都为Object，此时可以向集合中添加任意数据类型，但获取数据时无法使用对象的特有方法
优点：把运行时期的问题提前到编译期间，避免了强制类型转换可能出现的异常，因为在编译阶段类型就能确定下来
拓展：Java中的泛型是伪泛型
泛型类：
使用场景：当一个类中，某个变量的数据类型不确定时，就可以定义带有泛型的类
格式：
修饰符 class 类名 <类型>{}
public class ArrayList<E>{}
//此处的E可以理解为变量，但不实用来记录数据的，而是记录数据的类型，可以写成T，E,K,V等等
泛型方法：
方法中形参类型不确定时，可以使用类名后面定义的泛型，所有方法都能用；
也可以在方法申明上定义自己的泛型，只有本方法能用
格式：
修饰符 <类型> 返回值类型 方法名 （类型 变量名） {
}
public <T> void show (T t){
}
拓展：多个泛型变量可用 E...e 代替
public <T> void addAll(E...e){
e.for
}
泛型接口：
格式：
修饰符 interface 接口名 <类型>{
}
public interface List<E>{
}
使用方式：1.实现类给出具体类型
2.实现类延续泛型，创建对象时在确定
1：实现类给出具体类型
public class MyList implements List<String>{
}
2.实现类延续泛型，创建对象时在确定
public class MyList<E> implements List<E>{
}
MyList<String> list = new MyList<>();
泛型的继承和通配符：
泛型不具备继承性，但数据具备继承性
泛型的通配符：？ 表示不确定的类型，可以进行类型的限定
？extends E：表示可以传递E或者E所有的子类类型
？ super E：表示可以传递E或者E所有的父类类型
应用场景：在定义类，方法，接口的时候，如果类型不确定，就可以定义泛型类，泛型方法，泛型接口
如果类型不确定，但是能知道以后只能传递某个继承体系中的，就可以泛型的通配符
关键点：可以限定类型的范围
二叉树
基本结构：
节点：每个节点中包含父节点地址，值，左子节点地址，右子节点值
度：每一个节点的子节点数量
二叉树：任意节点的度 <= 2
高度：树的总层数
根节点：最顶层的节点
左子节点：左下方的节点
右子节点：右下方的节点
根节点的左子树：所有左边的子节点
根节点的右子树：所有右边的子节点
二叉查找树
二叉查找树：又叫做二叉排序树或者二叉搜索树
特点：每一个节点上最多有两个子节点
任意节点左子树上的值都小于当前节点
任意节点右子树上的值都大于当前节点
添加节点：小的存左边，大的存右边，一样的不存
二叉树的四种遍历方式：
前序遍历：从根节点开始，然后按照当前节点，左子结点，右子节点的顺序遍历
中序遍历：从最左边的子节点开始，然后按照左子结点，当前节点，右子节点的顺序遍历
后序遍历：从最左边的子节点开始，然后按照左子结点，右子节点，当前节点的顺序遍历
层序遍历：从根节点开始，一层一层的遍历
当前节点在那个位置就属于那种遍历
弊端：容易形成链表结构
平衡二叉树
规则：任意节点左右子树高度差不超过1
机制：旋转机制分为左旋 和右旋
触发时机：当添加一个节点后，该树不再是一颗平衡二叉树
左旋：
-
确定支点：从添加的节点开始，不断地往父节点找不平衡的节点
-
把支点左旋降级，变成左子节点
-
晋升原来的右子节点
复杂情况：
- 确定支点：从添加的节点开始，不断地往父节点找不平衡的节点
- 将根节点的右侧往左拉
- 原来的右子节点变成新的父节点，并把多余的左子节点让出，给已降级的节点当做右子节点
右旋：
-
确定支点：从添加的节点开始，不断地往父节点找不平衡的节点
-
把支点右旋降级，变成右子节点
-
晋升原来的右子节点
复杂情况：
- 确定支点：从添加的节点开始，不断地往父节点找不平衡的节点
- 将根节点的左侧往右拉
- 原来的左子节点变成新的父节点，并把多余的右子节点让出，给已降级的节点当做左子节点
需要旋转的四种情况：
- 左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡。右旋一次
- 左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡。局部进行左旋，变为左左的情况后，在整体进行一次右旋
- 右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡。左旋一次
- 右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡。局部进行右旋，变为右右的情况后，在整体进行一次左旋
红黑树
一种自平衡的二叉树，是计算机科学中用到的一种数据结构，1972年出现，当时被称为平衡二叉B数。后来1978年别修改为“红黑树”。它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色，每一个节点可以是红或者黑；红黑树不是高度平衡的，他的平衡是通过“红黑规则”进行实现的。(特有的红黑规则)
红黑树增删改查的性能都很好
红黑规则：
- 每一个节点或是红色，或者黑色
- 根节点必须是黑色的
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值位Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的
- 如果某一个节点是红色的，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
添加节点的规则：
默认颜色：添加节点默认是红色的（效率高）
ArrayList集合
底层原理
利用空参构创建的集合，在底层创建一个默认长度为0的数组，添加第一个元素时，底层会创建一个新的长度为10的数组，存满时会自动扩容1.5倍；如果一次添加多个元素，扩容1.5倍后还是放不下，则新创建数组的长度以实际为准
LinkedList集合
底层数据结构是双链表，查询慢，增删快，弹是如果操作的是首尾元素，速度也是极快的
特有方法：
底层逻辑：
迭代器底层：
Set集合
添加的元素是无序、不重复、无索引
无序：存取顺序不一致
不可重复：可以去除重复
无索引：没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素
Set集合的实现类：HashSet：无序，不重复，无索引
LinkedHashSet：有序，不重复，无索引
TreeSet：可排序，不重复，无索引
Set接口中的方法基本上与Collection的API一致
HashSet
哈希值
哈希值：根据hashCode方法算出来的int类型的整数
该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
对象的哈希值特点：
- 如果没有重写hashCode方法，不同对象计算出的哈希值是不同的
- 如果已经重写了hashCode方法，不同对象只要属性值相同，计算出来的哈希值就是一样的
- 在小部分的情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样（哈希碰撞）
HashSet底层原理
HashSet集合底层采取哈希表存储数据，哈希表是一种对于增删改查数据性能都较好的结构
哈希表的组成：JDK8之前：数组+链表 JDK8开始：数组+链表+红黑树
JDK8之前:
- 创建一个默认长度16，默认加载因为0.75的数组，数组名table 当数据到达（长度*加载因）时，触发自动扩容 JDK8以后，当链表长度大于8，且数组长度大于等于64时，此时的链表会转变成红黑树 【HashSet hm = new HashSet<>();】
- 根据元素的哈希值跟数组的长度计算出应存入的位置 【int index = (数组长度-1) & 哈希值】
- 判断当前位置是否为null，如果是null直接存入
- 如果不为null，表示有元素，则调用equals方法比较属性值
- 一样：不存 不一样：存入数组，形成链表 【JDK8以前：新元素存入数组，老元素挂在新元素下面】 【JDK8开始：新元素直接挂在老元素下面】
HashSet的三个问题
问题1：HashSet为什么存和取的顺序不一样
在链表中添加的位置时根据HashCode值计算出的地址存入的，所以存取顺序不一致
问题2：HashSet为什么没有索引
存入的索引为HashCode计算出的地址值，固无索引
问题3：HashSet是利用什么机制去保证数据去重
利用HashCode方法计算地址值与equals方法比较数据内部的属性值，相同则无法存入
LinkedHashSet
有序，不重复，无索引
这里的有序指的是保证存储和取出的元素顺序一致，底层数据结构依然是哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序
TreeSet
特点：不重复、无索引。可排序
可排序：按照元素的默认规则（由小到大）排序
TreeSet集合底层是基于红黑树的数据结构实现排序的，增删改查都较好
默认排序规则：
- 对于数字类型：Integer，Double 等类型按照从小到大的顺序进行排序
- 对于字符，字符串类型：按照字符在ASCII码表中的数字升序进行排序（字符和字符串默认的顺序是按照字典的顺序进行排列的，碰巧与ASCII表相同）
自定义比较规则：
- 默认排序/自然排序：JavaBean类实现Comparable接口并实现comparaTo方法，返回想根据排序顺序的字段，从而指定比较规则【
注意：当返回 this.getAge()-o.getAge()时,其中this表示当前要添加的元素，o表示已经在红黑树存在的元素 返回值：负数：认为要添加的元素是小的，存左边； 正数：认为要添加的元素是大的，存右边 ； 0：认为要添加的元素已存在，舍弃】 - 比较器排序：创建TreeSet对象的时候，传递比较器Comparator制定规则
使用规则：默认使用第一种，第一中无法满足时，用第二种
双列集合
键值对
特点：
- 双列集合一次需要存一对数据，分别为键和值
- 键不能重复，值可以重复
- 键和值是一一对应的，每一个键只能找自己对应的 值
- “键+值” 这个整体我们称之为“键值对”或“键值对对象”，在Java中叫做Entry对象
Map常见的API：Map是双列集合的顶层接口，他的功能是全部双列集合都可以集成使用的
put（）方法：添加或覆盖，在添加数据时如果键是存在的，那么会把原有的键值对进行覆 盖，并返回被覆盖的值
Map的遍历：
-
键找值：调用keySet()方法获取Map集合所有的键，通过get()方法获取相应的值
-
键值对：调用entrySet()方法获取Entry对象的Set集合，获取每一个Entry对象，然后调用Entry对象的getKey（）和getValue （）方法进行遍历
-
Lambda表达式：调用forEach（）方法,并传入 new Biconsumer匿名对象，在accept（）方法体内进行<K,V>的遍历（可进行Lambda简化代码）
HashMap
特点：HashMap是Map的一个实现类
键：无序，不重复，无索引
HashMap跟HashSet底层原理是一样的，都是哈希表结构
注意：依赖HashCode方法和equals方法保证键的唯一，自定义对象需要重写hashCode和equals方法。
LinkedHashMap
特点：有序，不重复，无索引
有序：保证存储和取出的顺序是一致的，底层数据结构依然为哈希表，只是每个键值对元素又额外的多了一个双链表的机制记录存储的顺序
TreeMap
特点：底层与TreeSet原理一样，都是红黑树结构的
不重复，无索引，可排序
可排序：对键进行排序
注意：默认按照键的从小到大进行排序，也可以自己规定键的排序规则
规则：
- 实现Comparable接口，指定比较规则
- 创建集合时传递Comparator比较器对象，指定比较规则
注：如果不要求对结果进行排序，使用HashMap，要求则使用TreeMap
HashMap源码解析
1.看源码之前需要了解的一些内容
Node<K,V>[] table 哈希表结构中数组的名字
DEFAULT_INITIAL_CAPACITY： 数组默认长度16
DEFAULT_LOAD_FACTOR： 默认加载因子0.75
HashMap里面每一个对象包含以下内容：
1.1 链表中的键值对对象
包含：
int hash; //键的哈希值
final K key; //键
V value; //值
Node<K,V> next; //下一个节点的地址值
1.2 红黑树中的键值对对象
包含：
int hash; //键的哈希值
final K key; //键
V value; //值
TreeNode<K,V> parent; //父节点的地址值
TreeNode<K,V> left; //左子节点的地址值
TreeNode<K,V> right; //右子节点的地址值
boolean red; //节点的颜色
2.添加元素
HashMap<String,Integer> hm = new HashMap<>();
hm.put("aaa" , 111);
hm.put("bbb" , 222);
hm.put("ccc" , 333);
hm.put("ddd" , 444);
hm.put("eee" , 555);
添加元素的时候至少考虑三种情况：
2.1数组位置为null
2.2数组位置不为null，键不重复，挂在下面形成链表或者红黑树
2.3数组位置不为null，键重复，元素覆盖
//参数一：键
//参数二：值
//返回值：被覆盖元素的值，如果没有覆盖，返回null
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//利用键计算出对应的哈希值，再把哈希值进行一些额外的处理
//简单理解：返回值就是返回键的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//参数一：键的哈希值
//参数二：键
//参数三：值
//参数四：如果键重复了是否保留
// true，表示老元素的值保留，不会覆盖
// false，表示老元素的值不保留，会进行覆盖
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//定义一个局部变量，用来记录哈希表中数组的地址值。
Node<K,V>[] tab;
//临时的第三方变量，用来记录键值对对象的地址值
Node<K,V> p;
//表示当前数组的长度
int n;
//表示索引
int i;
//把哈希表中数组的地址值，赋值给局部变量tab
tab = table;
if (tab == null || (n = tab.length) == 0){
//1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组
//2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件
//如果没有达到扩容条件，底层不会做任何操作
//如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中
tab = resize();
//表示把当前数组的长度赋值给n
n = tab.length;
}
//拿着数组的长度跟键的哈希值进行计算，计算出当前键值对对象，在数组中应存入的位置
i = (n - 1) & hash;//index
//获取数组中对应元素的数据
p = tab[i];
if (p == null){
//底层会创建一个键值对对象，直接放到数组当中
tab[i] = newNode(hash, key, value, null);
}else {
Node<K,V> e;
K k;
//等号的左边：数组中键值对的哈希值
//等号的右边：当前要添加键值对的哈希值
//如果键不一样，此时返回false
//如果键一样，返回true
boolean b1 = p.hash == hash;
if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
} else if (p instanceof TreeNode){
//判断数组中获取出来的键值对是不是红黑树中的节点
//如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
//如果从数组中获取出来的键值对不是红黑树中的节点
//表示此时下面挂的是链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//此时就会创建一个新的节点，挂在下面形成链表
p.next = newNode(hash, key, value, null);
//判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin
//treeifyBin方法的底层还会继续判断
//判断数组的长度是否大于等于64
//如果同时满足这两个条件，就会把这个链表转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//e： 0x0044 ddd 444
//要添加的元素： 0x0055 ddd 555
//如果哈希值一样，就会调用equals方法比较内部的属性值是否相同
if (e.hash == hash && ((k = e.key) == key || (key != null &&
key.equals(k)))){
break;
}
p = e;
}
}
//如果e为null，表示当前不需要覆盖任何元素
//如果e不为null，表示当前的键是一样的，值会被覆盖
//e:0x0044 ddd 555
//要添加的元素： 0x0055 ddd 555
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null){
//等号的右边：当前要添加的值
//等号的左边：0x0044的值
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
//threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机 16 * 0.75 = 12
if (++size > threshold){
resize();
}
//表示当前没有覆盖任何元素，返回null
return null;
}
TreeMap源码解析
1.TreeMap中每一个节点的内部属性
K key; //键
V value; //值
Entry<K,V> left; //左子节点
Entry<K,V> right; //右子节点
Entry<K,V> parent; //父节点
boolean color; //节点的颜色
2.TreeMap类中中要知道的一些成员变量
public class TreeMap<K,V>{
//比较器对象
private final Comparator<? super K> comparator;
//根节点
private transient Entry<K,V> root;
//集合的长度
private transient int size = 0;
3.空参构造
//空参构造就是没有传递比较器对象
public TreeMap() {
comparator = null;
}
4.带参构造
//带参构造就是传递了比较器对象。
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
5.添加元素
public V put(K key, V value) {
return put(key, value, true);
}
参数一：键
参数二：值
参数三：当键重复的时候，是否需要覆盖值
true：覆盖
false：不覆盖
private V put(K key, V value, boolean replaceOld) {
//获取根节点的地址值，赋值给局部变量t
Entry<K,V> t = root;
//判断根节点是否为null
//如果为null，表示当前是第一次添加，会把当前要添加的元素，当做根节点
//如果不为null，表示当前不是第一次添加，跳过这个判断继续执行下面的代码
if (t == null) {
//方法的底层，会创建一个Entry对象，把他当做根节点
addEntryToEmptyMap(key, value);
//表示此时没有覆盖任何的元素
return null;
}
//表示两个元素的键比较之后的结果
int cmp;
//表示当前要添加节点的父节点
Entry<K,V> parent;
//表示当前的比较规则
//如果我们是采取默认的自然排序，那么此时comparator记录的是null，cpr记录的也是null
//如果我们是采取比较去排序方式，那么此时comparator记录的是就是比较器
Comparator<? super K> cpr = comparator;
//表示判断当前是否有比较器对象
//如果传递了比较器对象，就执行if里面的代码，此时以比较器的规则为准
//如果没有传递比较器对象，就执行else里面的代码，此时以自然排序的规则为准
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
} else {
//把键进行强转，强转成Comparable类型的
//要求：键必须要实现Comparable接口，如果没有实现这个接口
//此时在强转的时候，就会报错。
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//把根节点当做当前节点的父节点
parent = t;
//调用compareTo方法，比较根节点和当前要添加节点的大小关系
cmp = k.compareTo(t.key);
if (cmp < 0)
//如果比较的结果为负数
//那么继续到根节点的左边去找
t = t.left;
else if (cmp > 0)
//如果比较的结果为正数
//那么继续到根节点的右边去找
t = t.right;
else {
//如果比较的结果为0，会覆盖
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
}
//就会把当前节点按照指定的规则进行添加
addEntry(key, value, parent, cmp < 0);
return null;
}
private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
Entry<K,V> e = new Entry<>(key, value, parent);
if (addToLeft)
parent.left = e;
else
parent.right = e;
//添加完毕之后，需要按照红黑树的规则进行调整
fixAfterInsertion(e);
size++;
modCount++;
}
private void fixAfterInsertion(Entry<K,V> x) {
//因为红黑树的节点默认就是红色的
x.color = RED;
//按照红黑规则进行调整
//parentOf:获取x的父节点
//parentOf(parentOf(x)):获取x的爷爷节点
//leftOf:获取左子节点
while (x != null && x != root && x.parent.color == RED) {
//判断当前节点的父节点是爷爷节点的左子节点还是右子节点
//目的：为了获取当前节点的叔叔节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//表示当前节点的父节点是爷爷节点的左子节点
//那么下面就可以用rightOf获取到当前节点的叔叔节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
//叔叔节点为红色的处理方案
//把父节点设置为黑色
setColor(parentOf(x), BLACK);
//把叔叔节点设置为黑色
setColor(y, BLACK);
//把爷爷节点设置为红色
setColor(parentOf(parentOf(x)), RED);
//把爷爷节点设置为当前节点
x = parentOf(parentOf(x));
} else {
//叔叔节点为黑色的处理方案
//表示判断当前节点是否为父节点的右子节点
if (x == rightOf(parentOf(x))) {
//表示当前节点是父节点的右子节点
x = parentOf(x);
//左旋
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
//表示当前节点的父节点是爷爷节点的右子节点
//那么下面就可以用leftOf获取到当前节点的叔叔节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//把根节点设置为黑色
root.color = BLACK;
}
6.课堂思考问题：
6.1TreeMap添加元素的时候，键是否需要重写hashCode和equals方法？
此时是不需要重写的。
6.2HashMap是哈希表结构的，JDK8开始由数组，链表，红黑树组成的。
既然有红黑树，HashMap的键是否需要实现Compareable接口或者传递比较器对象呢？
不需要的。
因为在HashMap的底层，默认是利用哈希值的大小关系来创建红黑树的
6.3TreeMap和HashMap谁的效率更高？
如果是最坏情况，添加了8个元素，这8个元素形成了链表，此时TreeMap的效率要更高
但是这种情况出现的几率非常的少。
一般而言，还是HashMap的效率要更高。
6.4你觉得在Map集合中，java会提供一个如果键重复了，不会覆盖的put方法呢？
此时putIfAbsent本身不重要。
传递一个思想：
代码中的逻辑都有两面性，如果我们只知道了其中的A面，而且代码中还发现了有变量可以控制两面性的发生。
那么该逻辑一定会有B面。
习惯：
boolean类型的变量控制，一般只有AB两面，因为boolean只有两个值
int类型的变量控制，一般至少有三面，因为int可以取多个值。
6.5三种双列集合，以后如何选择？
HashMap LinkedHashMap TreeMap
默认：HashMap（效率最高）
如果要保证存取有序：LinkedHashMap
如果要进行排序：TreeMap
可变参数
方法参数的个数是可以发生改变的,底层就是一个数组
格式：属性类型…名字 int…args
使用方法：可变参数即为一个数组，数据可遍历得到（增强for循环）
注意：方法的形参中最多只能写一个可变参数；若还有其它参数，则可变参数必须 写在最后
Collections
作用：集合的工具类
常用API：
创建不可变集合
应用场景：如果某个数据不能被修改，把他防御性的拷贝到不可变集合中是个很好的实践。当集合对象被不可信的库调用时，不可变形式是安全的
简单理解：不想让别人修改集合中的内容
书写格式
List<String> list = List.of("zhang", "li");
Map<String , String> map = Map.of("河南"，"郑州","河北","保定")；//键不能重复；参数最多20个（十个键值对）
map不可变集合多添加方法：
HashMap<String , String> hm = new HashMap()；
hm.put("1","1");
hm.put("2","2");
hm.put("3","3");
Set<Map.Entry<String,String>> entrise = hm.entrySet();
Map.Entry[] arr1 = new Map.Entry[0];
Map.Entry[] arr2 = entries.toArray(arr1);
Map map = Map.ofEntries(arr2);
简化如下：
Map<Object, Object> map = Map.ofEntries(hm.entrySet().toArray(new Map.Entry[0]));
Map<String, String> map =Map.copyOf（hm）；//JDK10才出现的新方法
Stream流
调用List对象的stream方法中的filter进行过滤，符合条件的留下，否则舍弃
代码实现：
List<string> list = new ArrayList()；
list.add("张三丰")；
list.add("张无忌")；
list.add("张三")；
list.stream().filter（name->name.startsWith("张")).filter（name->name.length()==3）.forEach（name->sout(name)）
流：结合了Lambda表达式，简化集合、数组的操作
使用步骤：
-
先得到一条Stream流（流水线），并把数据放上去
-
利用Stream流中的API进行各种操作：
中间方法：过滤，转换 （链式编程）
终结方法：统计，打印 （链式编程）
注:终结方法的最后一步调用完后，不能调用其他方法
流的获取方法：
双列集合必须先转为keySet()或者entrySet()后，再使用单列集合的方式获取流
Streamof();传递的参数必须是引用数据类型，如果传递的是基本数据类型，则会把整个数组当做一个数组对象放到Stream流中去，打印出来为该对象的地址值
中间方法：
注意：
- 中间方法，返回新的Stream流，原来的Stream流只能使用一次，建议使用链式编程
- 修改Stream流中的数据，不会影响原来集合或数组中的数据
filter方法：
filter(new Predicate<String>{
public boolean test(String s){
retuen s.startsWith(" ");//true:表示留下当前数据；false“表示舍弃当前数据
// !s.startsWith(" ") 是否可行？
}
}).forEach(s -> sout(s));
map方法：
//第一个泛型类型：流中原本的数据类型
//第二个泛型类型：要转成之后的类型
list.stream（）.map(new Function<String , Integer>(){
//apply的形参s:依次表示流里面的每一个数据；返回值：表示转换之后的数据
public Integer apply(String s){
String[] arr = s.split("-");
String a = arr[1];
return Integer.parseInt(a);
}
}).forEach(s->sout(s));//map方法执行完毕后，流中的数据变成了整数，所以打印是不需要加双引号
Lambda简化：
list.stream（）.map(s-> Integer.parseInt(s.split("-")[1]).forEach(s->sout(s));
终结方法：
toArry方法：
//IntFunction的泛型：具体类型的数组
String[] arr = list.stream().toArray(new IntFunction<String[]>(){
//apply的形参：流中数据的个数，要跟数组的长度保持一致
//apply的返回值：具体类型的数组
//方法体：创建数组
public String[] apply(int value){
return new String[value];
}
} )；
sout(Arrays.toString(arr));
toArray方法参数的作用：负责创建一个指定类型的数组
toArray方法的底层：会依次得到流里面的每一个数据，并把数据放到数组当中
toArray方法的返回值：使一个装着流里面所有数据的数组
Lambda简洁写法：
String[] arr = list.stream().toArray(value -> new String[value])；
collect方法：
List<String> newList = list.stream().filter("筛选条件").collect(Collectors.toList());
Set<String> newSet = list.stream().filter("筛选条件").collect(Collectors.toSet());
Map<String,Integer> newMap = list.stream().filter("筛选条件")
.collect(Collectors.toMap(new Function<String,String>{
/*
Function参数一：表示键的生成规则
泛型一：表示流中每一个数据的类型
泛型二：表示Map集合中键的数据类型
方法apply形参:依次表示流里面的每一个数据
方法体：生成键的代码
返回值：以及生成的键
*/
public String apply(String s){
return s.split("-")[0];
}
}),new Function<String,Integer>(){
/*
Function参数二：表示值得生成规则
泛型一：表示流中的每一个数据类型
泛型二：生成值的代码
方法apply形参:依次表示流里面的每一个数据
方法体：生成值的代码
返回值：已经生成的值
*/
public String apply(String s){
return Integer.parseInt(s.split("-")[2]);
}
});
//注意：将数据收集到Map集合中时，键不能重复，否则会报错
Lambda简洁写法：
Map<String,Integer> newMap = list.stream().filter("筛选条件")
.collect(Collectors.toMap(s-> s.split("-")[0],
s-> Integer.parseInt(s.split("-")[2])));
