6.1 数据结构
1、数据结构定义
数据结构是指逻辑意义上的数据组织方式及其相应的处理方式。
2、数据结构分类
- 线性结构
- 树结构
- 图结构
- 哈希结构
数据结构的复杂度分为空间复杂度和时间复杂度。
从最好到最坏的常用算法复杂度排序如下：常数级$O(1)$、对数级$O(logn)$、线性级$O(n)$、线性对数级$O(nlogn)$、平方级$O(n^2)$、立方级$O(n^3)$、指数级$O(2^n)$。
6.2 集合框架图
6.2.1 List集合
List集合是线性数据结构的主要实现。最常用的是ArrayList和LinkedList。
ArrayList是容量可以改变的非线程安全集合。内部实现使用数组进行存储，集合扩容时会创建更大的数组空间，把原有数据复制到新数组中。ArrayList支持对元素的快速随机访问，但是插入与删除时速度通常很慢。
LinkedList的本质是双向链表。与ArrayList相比，LinkedList的插入与删除速度更快，但是随机访问速度则很慢。LinkedList的优点在于可以将零散的内存单元通过附加引用的方式关联起来，形成按链路顺序查找的线性结构，内存利用率较高。
6.2.2 Queue集合
Queue是一种先进先出的线性结构。由于本身FIFO的特性和阻塞操作的特点，经常被作为Buffer（数据缓存区）使用。
6.2.3 Map集合
Map集合是以key-value键值对作为存储元素实现的哈希结构。HashMap是线程不安全的，ConcurrentHashMap是线程安全的，TreeMap是Key有序的Map类集合。
6.2.4 Set集合
Set是不允许出现重复元素的集合类型。HashSet从源码分析是使用HashMap来实现的。TreeSet从源码分析是使用TreeMap来实现的，底层为树结构。LinkedHashSet继承自HashSet，具有HashSet的优点，内部使用链表维护了元素插入顺序。
6.3 集合初始化
集合初始化通常进行分配容量、设置特定参数等相关工作。
HashMap容量并不会在new的时候分配，而是在第一次put的时候完成创建的。
集合初始化时，指定集合初始值大小。如果暂时无法确定集合大小，那么指定相应的默认值。
6.4 数组与集合
数组是一种顺序表，它是组织和处理数据的一种常见方式，我们可以使用索引下标进行快速定位并获取指定位置的元素。
为什么下标不从1开始呢？如果从1开始，计算偏移量就要使用当前下标减1的操作。加减法运算对CPU来说是一种双数运算，在数组下标使用频率极高的场景下，这种运算是十分耗时的。
数组与集合都是用来存储对象的容器，前者性质单一，方便易用；后者类型安全，功能强大，且两者之间必然有相互转换的方式。
在数组转集合的过程中，注意是否使用了视图方式直接返回数组中的数据。
使用集合的toArray(T[] array)方法，转换为数组时，注意需要传入类型完全一样的数组，并且它的容量大小为list.size()。
6.5 集合与泛型
<? extends T>是Get First，适用于，消费集合元素为主的场景；<? super T>是Put First，适用于，生产集合元素为主的场景。
<? extends T>可以赋值给任何T及T子类的集合，上界为T，取出来的类型带有泛型限制，向上强制转型为T。null可以表示任何元素，所以除开null外，任何元素都不得添加进<? extends T>集合内。
<? super T>可以赋值给任何T及T的父类集合，下界为T。
6.6 元素的比较
6.6.1 Comparable和Comparator
Java中两个对象相比较的方法通常用在元素排序中，常用的两个接口分别是Comparable和Comparator，前者是自己和自己比，可以看作是自营性质的比较器；后者是第三方比较器，可以看作是平台性质的比较器。
6.6.2 hashCode和equals
Object类定义中对hashCode和equals要求如下：
- 如果两个对象的equals的结果是相等的，则两个对象的hashCode的返回结果也必须是相同的
- 任何时候覆写equals，都必须同时覆写hashCode
6.7 fail-fast机制
fail-fast机制是集合世界中比较常见的错误检测机制，通常出现在遍历集合元素的过程中。
它是一种在集合遍历操作时的错误检测机制，在遍历中途出现意料之外的修改时，通过unchecked异常暴力地反馈出来。
fail-safe是在安全的副本上进行遍历，集合修改与副本的遍历是没有任何关系的，但是缺点也很明显，就是读取不到最新的数据。这也是CAP理论中C（Consistency）与A（Availability）的矛盾。
6.8 Map类集合
6.8.1 红黑树
1、树（Tree）
树结构的特点如下：
- 一个节点，即只有一个根节点，也可以是一棵树
- 其中任何一个节点与下面所有节点构成的树称为子树
- 根节点没有父节点，而叶节点没有子节点
- 除根结点外，任何节点有且仅有一个父节点
- 任何节点可以有0~n个子节点
每个节点至多有两个子节点的树称为二叉树。
2、平衡二叉树
平衡二叉树的性质如下：
- 树的左右高度差不能超过1
- 任何往下递归的左子树与右子树，必须符合第一条性质
- 没有任何节点的空树或只有根节点的树也是平衡二叉树
3、二叉查找树
二叉查找树额外增加了如下要求：
对于任意节点来说，它的左子树上所有节点的值都小于它，而它的右子树上所有节点的值都大于它。
遍历所有节点的常用方式有三种：前序遍历、中序遍历和后序遍历。它们三者的规律如下：
- 在任何递归子树中，左节点一定在右节点之前先遍历
- 前序、中序、后序，仅指根节点在遍历时的位置顺序
4、AVL树
AVL树是一种平衡二叉查找树，增加和删除节点后通过树形旋转重新达到平衡。
右旋是以某个节点为中心，将它沉入当前右子节点的位置，而让当前的左子节点作为新树的根节点，也称为顺时针旋转；同理，左旋是指以某个节点为中心，将它沉入当前左子节点的位置，而让当前右子节点作为新树的根节点，也称为逆时针旋转。
5、红黑树
红黑树本质上还是二叉查找树，它额外引入了五个约束条件：
- 节点只能是红色或黑色
- 根节点必须是黑色
- 所有NIL节点都是黑色
- 一条路径上不能出现相邻的两个红色节点
- 在任何递归子树内，根节点到叶节点的所有路径上包含相同数目的黑色节点
NIL可以形象理解为Nothing In Leaf，是红黑树中特殊的存在，即在叶子节点上不存在的两个虚拟节点。
6、红黑树与AVL树的比较
红黑树的平衡性不如AVL树，它维持的只是一种大致上的平衡，并不严格保证左右子树的高度差不超过1。这导致在相同节点的情况下，红黑树的高度可能更高。
面对频繁的插入和删除，红黑树更为合适；面对低频修改，大量查询时，AVL树更为合适。
6.8.2 TreeMap
TreeMap是按照key的排序结果来组织内部结构的Map类集合。
在树的演化过程中，插入节点的过程中，如果需要重新着色或旋转，存在三种情形：
- 节点的父亲是红色的，叔叔是红色的，则重新着色
- 节点的父亲是红色的，叔叔是黑色的，而新节点是父亲的左节点，进行右旋
- 节点的父亲是红色的，叔叔是黑色的，而新节点是父亲的右节点，进行左旋
6.8.3 HashMap
除局部方法或绝对线程安全的情形外，优先推荐使用ConcurrentHashMap。HashMap的死链问题及扩容数据丢失问题是慎用HashMap的两个主要原因。
HashMap在高并发场景中，新增对象丢失原因如下：
- 并发赋值时被覆盖
- 已遍历区间新增元素会丢失
- “新表”被覆盖
- 迁移丢失。在迁移过程中，有并发时，next被提前置成null
对于死链的生成，需要先明确三点：
- 原先没有死链的同一个slot上节点遍历一定能够按顺序走完
- table数组时各线程都可以共享修改的对象
- put()、get()、transfer()三种操作在运行到此拥有死链的slot上，CPU使用率都会飙升
6.8.4 ConcurrentHashMap
CAS（Compare And Swap）。CAS就是先比较，如果不符合预期，则进行重试。CAS操作包含三个操作要素：内存位置、预期原值（假设为A）和新值（假设为B）。