目录
- 一.Collection集合体系
-
- ①.List集合
-
- 1.1 ArrayList底层原理
-
- 1.1.1 单个存储
- 1.1.2 多个存储
- 1.2 LinkedList底层原理
- ②.Collection遍历方式
-
- 2.1 迭代器遍历
- 2.2 增强for遍历
- 2.3 Lambda表达式遍历
- 2.4 迭代器源码分析
- ③.Set集合
-
- 3.1 HashSet
-
- 3.1.1 HashSet底层结构
- 3.1.2 HashSet存储原理
- 3.1.3 HashSet三个疑惑
- 3.2 LinkedHashSet
- 3.3 TreeSet
-
- 3.3.1 排序规则
- 3.3.2 默认排序/自然排序
- 3.3.3 比较器排序/定制排序
- ④.集合工具类Collections
- ⑤.Collection集合总结
- 二.Map集合体系
-
- 1. HashMap
- 2. HashMap底层源码解析
- 3. TreeMap
- 4. TreeMap底层源码解析
- 5. Map结合总结与思考
前言：这些底层原理的图画的可能不太清晰，但整体流程是完善出来了，多多琢磨，定会霍然开朗。因为个人能力有限，不足之处望诸位多多包涵，也欢迎您的补充与指正，最后感谢您的阅览，也希望您能有所收获
一.Collection集合体系
Collection是单列集合的祖宗接口，它的功能是全部单列集合都可以继承使用的。
Collection常用方法如下
注意
因为contains方法在底层依赖equals方法判断对象是否一致的。
如果存的是自定义对象（如student），没有重写equals方法，那么默认使用object类中的equals方法进行判断，而object类中equals方法，依赖地址值进行判断.需求:如果同姓名和同年龄，就认为是同一个学生。
所以，需要在自定义的Javabean类中，重写equals方法就可以了。
①.List集合
List系列集合：添加元素是有序（存和取顺序一致），可重复，有索引的
由于List集合有索引，所以出来Collection的共性方法外，还有多了一些索引操作的方法
下面是根据索引的增，删，改，查四个方法
细节注意
使用指定索引插入方法，原来索引上的元素依次向后移
使用指定索引删除方法，会将被删除元素作为返回
使用指定索引修改方法，会将被修改元素作为返回
1.1 ArrayList底层原理
JDK7：初始化时，底层创建长度为10的数组
JDK8：初始化创建一个空数组，没有长度，只有调用add时才创建长度为10的数组
1.1.1 单个存储
elementData是它底层数组的名称
当存满后，自动扩容为原数组的1.5倍，再将原数组的内容拷贝到新数组中
起始创建时，数组容量为0，添加第一个元素，数组初始化容量为10，源码调用逻辑如下图，注：这是JDK11的底层源码和JDK8不一样
下面是添加第一个元素，数组初始化容量为10的，调用过程
1.1.2 多个存储
如果一次添加多个数据，数组放不下，则新创建数组以实际长度为准，比如新添加100个元素，新数组的长度就是100
数组扩容的两种情况
一. 单个单个元素增加时扩容为之前的1.5倍（数组右移一位就是除以2，新增的容量为之前的一半，那合起来就是1.5倍）
二. 多个元素一起添加，addAll的情况，数组扩容为实际要存放的元素的总数量，例如之前初始化容量为10，添加100个元素，这时数组长度为110
以下是数组容量为10，添加第11个元素源码调用及一次添加100个元素详细过程解析
1.2 LinkedList底层原理
与ArrayList底层为数组不同，LinkedList底层是一个双向列表结构，秉承列表特点，查询慢，增删快
底层源码调用
最终双向链表形成的结果图
②.Collection遍历方式
由于Colllectino集合下的set集合没有索引，所以不能再用以前的for循环遍历了，下面是提供的三种遍历方式
2.1 迭代器遍历
迭代器不依赖索引，迭代器是集合专用的遍历方式
细节注意点:
1，如果迭代器指针已遍历到最后，再次调用next()方法获取元素，会报错NoSuchElementException
2，迭代器遍历完毕，指针不会复位；如果要把该集合再次遍历一遍，只能重新获取一个新的迭代器对象
3，循环中只能用一次next方法；next方法执行的是获取元素，移动指针，如果循环体内再来一个it.next()，一次循环中指针会后移两次，最后会报NoSuchElementException（没有这个元素异常）
4，迭代器遍历时，不能用集合的方法进行增加或者删除；如果使用了集合的方法，会报并发修改异常，详细见下面迭代器源码分析位置
便于遍历过程中删除元素，用迭代器的删除方法
2.2 增强for遍历
增强for的底层就是迭代器，为了简化迭代器代码书写的
所有的单列集合和数组才能用增强for进行遍历
注意细节：
修改增强for中的变量，不会改变集合中原本的数据。
2.3 Lambda表达式遍历
得益于JDK8开始的新技术Lambda表达式，提供了一种更简单、更直接的遍历集合的方式。
例如下
2.4 迭代器源码分析
迭代器回顾
迭代器源码调用分析
调用解析
并发修改异常原理
结论
在以后如何避免并发修改异常
在使用迭代器或者是增强for遍历集合的过程中，不要使用集合的方法去添加或者删除元素即可。
③.Set集合
Set系列集合：添加的元素是无序（存和取的顺序不一致），不重复（常用来去重），无索引（不能根据索引获取元素）
set集合下的所有实现类底层，都是new了一个map对象
3.1 HashSet
使用格式如下（泛型不是一定的），它的api方法就是Collection的共性方法
3.1.1 HashSet底层结构
- HashSet集合底层采取哈希表存储数据
- 哈希表是一种对于增删改查数据性能都较好的结构
而哈希表的组成
JDK8之前: 数组 + 链表
JDK8开始 :数组 + 链表 + 红黑树
哈希值，哈希表灵魂所在
哈希值就是对象的整数表现形式
哈希表底层是以数组存在的，它并不是从0索引开始的，依次往后存储的，而是依据下面的公式，算出得到存储的索引
int index =（数组长度-1）&哈希值;
哈希值概念
- 根据hashcode方法算出来的int类型的整数
- 该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
- 一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
对象的哈希值特点
- 如果没有重写hashCode方法，不同对象计算出的哈希值是不同的（因为对象地址值不可能一样）
- 如果已经重写hashcode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
- 在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。(哈希碰撞)
3.1.2 HashSet存储原理
int index =（数组长度-1）&哈希值;
扩容方式
①当存入了16*0.75（默认加载因子）=12个元素后，数组就会扩容为原来的两倍，比如上面例子就是扩容到32
②当链表长度大于8而且数组长度大于等于64时，当前链表就会自动转为红黑树，提高查找效率
注意
如果集合中存储的是自定义对象，必须要重写hashCode和equals方法（和重写getset方法方式一样），不重写比较的就是地址值，这样导致即使创建两个属性相同的对象，也可以存入set集合中。
而String，Integer这些不需要重写，因为这些类java底层已经重写好了
3.1.3 HashSet三个疑惑
1.为什么HashSet存和取的顺序不一样
HashSet遍历是从数组0下标开始的，但是HashSet存入是按数组长度和哈希值的计算公式得到存储的位置，可以说是存入即无序，那么按顺序遍历，自然不会有序。
2.为什么HashSet没有索引
因为HashSet底层结构就是数组+链表+红黑树，使用索引显然不太合适，不能说一个索引下还挂着一串链表，这怎么用索引表示
3.HashSet利用什么机制保证数据去重
这里依靠两个方法，一个是HashCode方法，一个是equals方法
通过HashCode方法计算出哈希值，通过equals方法判断属性是否相同，上面底层存储原理已经说明过了，若相同则不存储
3.2 LinkedHashSet
LinkedHashSet：有序，不重复，无索引
原理∶底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序。
有序原因如下
遍历的时候就不会从数组的0索引开始，而是根据第一个存入元素的双向链表来遍历
3.3 TreeSet
- 不重复、无索引、可排序
- 可排序:按照元素的默认规则(有小到大)排序。
- TreeSet集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好。
3.3.1 排序规则
- 对于数值类型:Integer , Double，默认按照从小到大的顺序进行排序。
- 对于字符、字符串类型:按照字符在ASCII码表中的数字升序进行排序。比较过程中只要有一个字符能确定大小关系，后面字母就不会再看了（不是和起来比大小）
注意添加自定义对象时，需要自己指定比较规则
3.3.2 默认排序/自然排序
javabean类实现Comparable接口，重写里面的抽象方法，再指定比较规则
如下
返回值:
负数:认为要添加的元素是小的，存左边
正数:认为要添加的元素是大的，存右边
0:认为要添加的元素已经存在，舍弃
注意这个o不是固定的，代指当前元素需要对比的元素，比如存入一个23，o开始是代表25，比完后放左边，左边有了24，又要和24比，这是o代表24。插入元素的同时也要注意红黑规则，不满足红黑规则就需要按照添加规则表来操作旋转。
这里添加元素，如果违背了红黑树的红黑规则，就需要对照红黑树添加规则表来操作，不然很迷糊
地址：
红黑树添加规则表
3.3.3 比较器排序/定制排序
比较器排序:创建TreeSet对象时候，传递比较器Comparator指定规则
使用原则:默认使用第一种，如果第一种不能满足当前需求，就使用第二种
下面是指定先按长度排序，一样再按首字母排序范例
TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//按照长度排序
int i = o1.length() - o2.length();
//如果一样长则按照首字母排序
i = i == 0 ? o1.compareTo(o2) : i;
return i;
}
});
i = i == 0 ? o1.compareTo(o2) : i;
这里用了三位运算和链式编程，把最后的结果赋值给i
④.集合工具类Collections
常用api如下
使用格式如下
⑤.Collection集合总结
二.Map集合体系
map集合是一种双列集合
双列集合的特点
①双列集合一次需要存一对数据，分别为键和值
②键不能重复，值可以重复
③键和值是一 一对应的，每一个键只能找到自己对应的值
④键＋值这个整体我们称之为“键值对”或者“键值对对象”，在Java中叫做“Entry对象”
Map集合常见的API（共性方法）
put方法细节处
- 在添加数据的时候，如果键不存在，那么直接把键值对对象添加到map集合当中,方法返回null
- 在添加数据的时候，如果键是存在的，那么会把原有的键值对对象覆盖，会把被覆盖的值进行返回。
①map集合遍历键值方式之一（键找值），for循环遍历（迭代器也可以下面只是示例）
遍历方式，把key放入单列集合，根据遍历的key，利用map集合中的键获取对应值得规则，遍历key，value
Set<String> set = map.keySet();
for (String key : set) {
String value = map.get(key);
System.out.println(key+"="+value);
}
②map集合遍历键值方式之二（键值对），通过一个方法获取所有的键值对对象，返回一个set集合，遍历entrySet 这个集合，去得到里面的每一个键值对对象
Set<Map.Entry<String, String>> entrySet = map.entrySet();
for (Map.Entry<String, String> entry : entrySet) {
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key+"="+value);
}
③map集合遍历键值方式之三（Lambda表达式）
底层:|
forEach其实就是利用第二种方式进行遍历，依次得到每一个键和值再调用accept方法
下面分别是匿名对象和lambda方式来遍历
map.forEach(new BiConsumer<String, String>() {
public void accept(String key, String value) {
System.out.println(key+"="+value);
}
});
map.forEach((String key, String value)->{
System.out.println(key+"="+value);
});
1. HashMap
特点都是由键决定的:无序、不重复、无索引
HashMap跟HashSet底层原理是一模一样的，都是哈希表结构（数组+链表+红黑树）
但是有一个区别，HashSet添加元素，一样的不存，而HashMap添加元素，相同的覆盖，这就是为什么map的put方法存入key相同时，覆盖之前的value
其余的和HashSet差不多，存储位置相同时，JDK7新元素存数组，老元素挂新元素下面，JDK8以后，新元素直接挂老元素下面就完了。当链表长度超过8且数组长度大于等于64时，链表自动转化成红黑树
总结
- HashMap底层是哈希表结构的
- 依赖hashcode方法和equals方法保证键的唯一
- 如果键存储的是自定义对象，需要重写hashCode和equals方法；如果值存储自定义对象，不需要重写hashCode和equals方法
2. HashMap底层源码解析
由于查看源码，需要不断跟进，转换页面很多，也不连贯，文字描述想要让人看懂是很难的，我自认为我没有用文字全面解析底层源码的能力，文字描述还能让人意会逻辑我也不知道如何去写
不如看看视频解析，视频连贯且清晰，逻辑更容易明悟。地址：阿玮老师讲的超赞的
属性，方法解释分析
1.看源码之前需要了解的一些内容
Node<K,V>[] table 哈希表结构中数组的名字 HashMap底层结构是哈希表， 而哈希表在JDK8以后是有数组+链表+红黑树构成
DEFAULT_INITIAL_CAPACITY： 数组默认长度16
DEFAULT_LOAD_FACTOR： 默认加载因子0.75
HashMap里面每一个对象包含以下内容：
1.1 链表中的键值对对象 ——entry对象
包含：
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<>(); 创建map集合时，数组是null，还未给数组长度赋值
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.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件
//如果没有达到扩容条件，底层不会做任何操作
//如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中
//扩容条件为数组元素数量达到了（加载因子*数组长度），扩容操作也时这个resize()方法做的
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; //就是把新的value覆盖给了原来的value，其实整个entry并没有覆盖还是以前的，只是value被覆盖了
}
afterNodeAccess(e);
return oldValue;
}
}
//threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机 16 * 0.75 = 12
if (++size > threshold){
resize();
}
//表示当前没有覆盖任何元素，返回null
return null;
}
LinkedHashMap和LinkedHashSet，底层原理基本一致，有序，唯一，无索引
3. TreeMap
- TreeMap跟TreeSet底层原理一样，都是红黑树结构的。
- 由键决定特性:不重复、无索引、可排序
- 可排序:对键进行排序。
- 注意:默认按照键的从小到大进行排序，也可以自己规定键的排序规则
排序规则也是和TreeSet一样有两种
- 实现Comparable接口，指定比较规则。
- 创建集合时传递Comparator比较器对象，指定比较规则。
不指定排序规则，默认按照键的升序来排序，这个默认的排序规则和TreeMap的一样
对于数值类型:Integer , Double，默认按照从小到大的顺序进行排序。
对于字符、字符串类型:按照字符在ASCII码表中的数字升序进行排序。比较过程中只要有一个字符能确定大小关系，后面字母就不会再看了（不是和起来比大小）
4. 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;
}
代码都给了详细的注解，每段代码的意思应该都很明确，看懂应该不难，这就是一个整体初始化及添加元素时，代码的调用过程
5. Map结合总结与思考
1.TreeMap添加元素的时候，键是否需要重写hashCode和equals方法？
此时是不需要重写的。
2.HashMap是哈希表结构的，JDK8开始由数组，链表，红黑树组成的。
既然有红黑树，HashMap的键是否需要实现Compareable接口或者传递比较器对象呢？
不需要的。
因为在HashMap的底层，默认是利用哈希值的大小关系来创建红黑树的
3.TreeMap和HashMap谁的效率更高？
如果是最坏情况，添加了8个元素，这8个元素形成了链表，此时TreeMap的效率要更高
但是这种情况出现的几率非常的少。
一般而言，还是HashMap的效率要更高。因为HashMap底层数组对于访问查询元素操作效率更高
4.你觉得在Map集合中，java会提供一个如果键重复了，不会覆盖的put方法呢？
此时 p u t I f A b s e n t 本身不重要。（就是不会覆盖键值的方法） \color{blue} {此时putIfAbsent本身不重要。（就是不会覆盖键值的方法）} 此时putIfAbsent本身不重要。（就是不会覆盖键值的方法）
传递一个思想：
代码中的逻辑都有两面性，如果我们只知道了其中的A面，而且代码中还发现了有变量可以控制面性的发生。
那么该逻辑一定会有B面。
习惯：
boolean类型的变量控制，一般只有AB两面，因为boolean只有两个值
int类型的变量控制，一般至少有三面，因为int可以取多个值。
5.三种双列集合，以后如何选择？
HashMap LinkedHashMap TreeMap
默认： HashMap（效率最高） 如果要保证存取有序：LinkedHashMap 如果要进行排序：TreeMap