数据结构与算法系列 (1) 基础数据结构-->java篇(Lis
2019-06-16 本文已影响0人
suxin1932
算法是程序的灵魂
1.概念
什么是数据结构
数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
数据结构往往同高效的检索算法和索引技术有关。
数据结构的主要功能是: 如何采用何种方式对数据集进行"增删改查"。
| 数据结构 | 优点 | 缺点 | 典型实现 |
|---|---|---|---|
| 有序数组 | 查询快 | 插入慢, 容量固定 | 数组,ArrayList<E> |
| 无序数组 | 插入快 | 查询慢, 容量固定 | 数组,ArrayList<E> |
| 链表 | 插入快,删除快 | 查询慢 | LinkedList<E> |
| 堆 | 插入快,删除快,对最大数据项存储快 | 对其他数据项存储慢 | PriorityQueue<E> |
| 栈 | 后进先出(LIFO) | 存取其他项慢 | Stack<E> |
| 队列 | 先进先出(FIFO) | 存取其他项慢 | BlockingQueue<E>系列 |
| 哈希表 | 若已知关键字,则存取快 | 删除慢,若不知关键字则存取慢,对存储空间应用不充分 | HashMap,HashSet(基于HashMap) |
| 二叉树 | 平衡树时, 增删查都快 | 删除算法复杂 | |
| 红黑树 | 增删查都快, 树总是平衡的算法复杂 | 算法复杂 | TreeMap,TreeSet(基于TreeMap) |
| 2-3-4树 | 是平衡树, 增删查都快,类似的树对磁盘存储有效 | 算法复杂 | |
| 图 | 对现实世界建模 | 有些算法慢而复杂 |
数组和链表都是通用的数据结构，能用来实现栈、队列等很多数据结构。
什么是算法
算法即是从问题初始状态到达问题终止状态的过程, 简言之, 就是解决问题的步骤与方法。
#五个特征
①有穷性
②确定性
③可行性
④有输入
⑤有输出
#设计原则
①正确性
②可读性
③健壮性
④高效率与低存储量需求：
效率指的是算法执行时间(时间复杂度)；
存储量是指算法执行过程中所需要的最大存储空间(空间复杂度),
包括程序本身所占空间；输入数据所占空间；辅助变量所占空间；
一个算法的效率越高越好，而存储量是越低越好。
3.数组
Java中，数组是用来存放同一种数据类型的集合(Object类型数组除外)。
"可以分为有序数组&无序数组(不传入下标进行查询, 可理解为无序)"
#相关类
'集合类'
java.util.ArrayList
'工具类'
java.util.Arrays
#缺点
在无序数组中，搜索性能差;
在有序数组中，插入效率又很低;
两种数组的删除效率都很低;
数组在创建后，其大小是固定了，设置的过大会造成内存的浪费，过小又不能满足数据量的存储。
4.链表
链表通常由一连串节点组成，每个节点包含:
a.数据域("data fields"): 储存节点含有的数据信息
b.引用域:储存下一个节点或者上一个节点的地址的链接("links")/指针("pointer")
"也可以分为有序链表和无序链表"
4.1单向链表
单向链表只可向一个方向遍历，
一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。
插入一个节点时，在链表头插入，将当前插入的节点设置为头节点，next指向原头节点即可。
删除一个节点时，将该节点的上一个节点的next指向该节点的下一个节点。
单向链表查询节点.png
单向链表插入节点.png
单向链表删除节点.png
4.2双向链表
双向链表可以从两个方向遍历。相关类: java.util.LinkedList
双向链表.png
5.堆
1.堆：
堆是一种树，由它实现的优先级队列的插入和删除的时间复杂度都是O(logn)，
用堆实现的优先级队列虽然和数组实现相比较删除慢了些，但插入的时间快的多了。
当速度很重要且有很多插入操作时，可以选择堆来实现优先级队列。
2.java的堆和数据结构堆：
java的堆是程序员用new能得到的计算机内存的可用部分。
数据结构的堆是一种特殊的二叉树。
3.堆是具有如下特点的二叉树：
3.1.是完全二叉树，也就是说除了树的最后一层节点不需要是满的，其他的每一层从左到右都必须是满的。
3.2.常常用数组实现。
3.3.堆中每一个节点都满足堆的条件，也就是说每一个关键字的值都大于或等于这个节点的子节点的关键字值。
堆是完全二叉树的事实说明了表示堆的数组中没有空项，即从0-->n-1的每个数据单元都有数据项。
3.4用数组表示一棵树时，如果数组中节点的索引位x，则
a.它的父节点的下标是：(x-1)/2；
b.它的左子节点的下标为: 2*x + 1；
c.它的右子节点的下标是: 2*x + 2；
4.堆在存储器中的表示是数组，堆只是一个概念上的表示。
5.堆的弱序：
堆和二叉搜索树相比是弱序的，
在二叉搜索树中，当前节点的值总是比左子节点的值大，却比它的右子节点的值小，因此按序遍历相对容易。
而堆的组织规则弱，它只要求从根到叶子节点的每一条路径，节点都是按降序排列的。
同一节点的左右子节点都没有规律。因此，堆不支持按序遍历，也不能在堆上便利的查找指定关键字，
因为在查找的过程中，没有足够的信息决定选择通过节点的两个那一个走向下一层。
它也不能在少于O(logn)的时间内删除一个指定的节点，因为没有办法找到这个节点。
因此，堆的这种近乎无序的规则似乎毫无用处，
不过对于快速移除最大节点的操作，以及快速插入新节点的操作，这种顺序已经足够了。
这些操作是使用堆作为优先级队列所需要的全部操作。
6.移除操作：移除是指删掉关键字值最大的节点，即根节点。移除思路如下：
6.1.移走根，
6.2.把左后一个节点移到根的位置，
6.3.一直向下筛选这个节点，知道它在一个大于它的节点之下，小于它的节点之上为止。
说明：
在被筛选节点的每个暂时停留的位置，向下筛选的算法总是要检查那一个子节点更大，
然后目标节点和较大的子节点交换位置，如果要把目标节点和较小的子节点交换，
那么这个子节点就会变成大子节点的父节点，这就违背了堆的条件。
7.堆的插入
说明：
向上筛选的算法比向下筛选的算法相对简单，因为它不需要比较两个子节点关键字值的大小，节点只有一个父节点。
目标节点主要和它的父亲节点换位即可。
完全二叉树和非完全二叉树.png
堆及其实现数组.png
移除堆节点.png
插入堆节点.png
插入堆节点-复制和交换.png
https://www.cnblogs.com/g177w/p/8469399.html
https://www.cnblogs.com/ysocean/p/8032660.html
https://blog.csdn.net/m0_37264516/article/details/84941656
6.栈
栈（stack）是一种只能在一端进行插入和删除操作的特殊线性表。
插入一般称为压栈（PUSH），删除则称为弹栈（POP）。
栈也称为后进先出表。特点(LIFO):
last in, first out
栈可以由数组结构实现, 也可以由链表结构实现
#应用场景
a.利用栈实现字符串逆序
b.子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
c.处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
d.表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
e.二叉树的遍历。
f.图形的深度优先(depth一first)搜索法。
栈.png
6.1 前缀, 中缀, 后缀表达式
6.1.1 前缀表达式(波兰表达式)
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
#前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，
遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；
重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:
>> 从右至左扫描，将6、5、4、3压入堆栈
>> 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
>> 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
>> 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
6.1.2 中缀表达式
中缀表达式就是常见的运算表达式，如(3+4)×5-6
中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作，
因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)
6.1.3 后缀表达式(逆波兰表达式)
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
#举例说明：
(3+4)×5-6 后缀表达式是 3 4 + 5 × 6 –
a+b 后缀表达式是 a b +
a+(b-c) 后缀表达式是 a b c - +
a+(b-c)*d 后缀表达式是 a b c - d * +
a+d*(b-c) 后缀表达式是 a d b c - * +
a=1+3 后缀表达式是 a 1 3 + =
#后缀表达式的计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，
遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；
重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
#例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
>> 从左至右扫描，将3和4压入堆栈；
>> 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
>> 将5入栈；
>> 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
>> 将6入栈；
>> 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
6.1.4 将中缀表达式转成后缀表达式
#具体步骤如下:
1.初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2.从左至右扫描中缀表达式；
3.遇到操作数时，将其压s2；
4.遇到运算符时，比较其与s1栈顶运算符的优先级：
4.1如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
4.2否则，若优先级比栈顶运算符的高，也将运算符压入s1；
4.3否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
5.遇到括号时：
(1) 如果是左括号“(”，则直接压入s1
(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6.重复步骤2至5，直到表达式的最右边
7.将s1中剩余的运算符依次弹出并压入s2
8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
将中缀表达式转成后缀表达式.png
7.队列
队列（queue）是一种特殊的线性表，
特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
和栈一样，队列是一种操作受限制的线性表。
进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列中没有元素时，称为空队列。
队列在队尾插入，在队首删除，故队列又称为先进先出（FIFO—first in first out）线性表。
如火车过隧道, 排队打饭等
#队列分为：
①单向队列（Queue）：只能在一端插入数据，另一端删除数据。
②双向队列（Deque）：每一端都可以进行插入数据和删除数据操作(栈+队列)。
#优先级队列:
队列中的数据项按照关键字进行排序，
关键字最小（或者最大）的数据项往往在队列的最前面，
而数据项在插入的时候都会插入到合适的位置以确保队列的有序。
单端队列.png
①栈、队列（单向队列）、优先级队列通常是用来"简化某些程序操作"的数据结构，而不是主要作为存储数据的。
②在这些数据结构中，只有一个数据项可以被访问。
③栈允许在栈顶压入（插入）数据，在栈顶弹出（移除）数据，但是只能访问最后一个插入的数据项，也就是栈顶元素。
④队列（单向队列）只能在队尾插入数据，队头删除数据，并且只能访问对头的数据。
而且队列还可以实现循环队列，它基于数组，数组下标可以从数组末端绕回到数组的开始位置。
⑤优先级队列是有序的插入数据，并且只能访问当前元素中优先级别最大（或最小）的元素。
⑥这些数据结构都能由数组实现，但是可以用链表、堆等数据结构实现。
9.树
https://www.jianshu.com/p/6a08b42750ad (树)
--------------- jdk中部分class(集合)数据结构开始(jdk8) ---------------
99.Map<K,V>接口相关实现类数据结构 -->研究 hash碰撞问题
99.1 HashMap<K,V>
数组+链表+红黑树实现的。
添加、查询、删除元素的效率都很高。
线程不安全。
key和value都允许为null。
从源码可知，HashMap类中有一个字段(取自其静态内部类):
就是Node[]table, 即哈希桶数组，是一个Node的数组。
HashMap使用哈希表存储，使用哈希表来解决哈希冲突。
Java中的HashMap采用了链地址法。数组加链表的结合。
在每个数组元素上都是一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表。
例如：
map.put("键","值");
系统将调用"键"这个key的hashCode()方法得到其hashCode，
然后通过Hash算法的后两步运算（高位运算和取模运算）来定位该键值对的存储位置，
有时两个key会定位到相同的位置，表示发生了Hash碰撞。
当然Hash算法计算结构越分散均匀，Hash碰撞的概率就越小，map的存取效率就越高。
好的Hash算法和扩容机制来控制map使得Hash碰撞的概率变小，哈希桶数组Node[]table占用空间又少。
下图讲述了"扩容过程"及"链表转红黑树"的过程, 以及扩容过程。
>> HashMap相关参数
// 初始化容量16, 2倍速扩容
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 装载因子, 扩容用, 2倍速变化
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 桶的树化阈值：当链表长度 >8时，则调用将链表转换成红黑树的方法
static final int TREEIFY_THRESHOLD = 8;
// 最小树形化容量阈值：当哈希表中的容量 >= 64时，将链表转换成红黑树
// // 否则，若桶内元素太多时，则直接扩容，而不是树形化
static final int MIN_TREEIFY_CAPACITY = 64;
// 桶的链表还原阈值：resize后, 当原红黑树size < 6时，红黑树转成链表
static final int UNTREEIFY_THRESHOLD = 6;
HashMap的put过程1.png
HashMap的put过程2.png
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤①：tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤③：节点key存在，直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤④：判断该链为红黑树
else if (p instanceof TreeNode)
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调用treeifyBin方法判断是否树化处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤⑥：超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
* 当map的容量大于等于MIN_TREEIFY_CAPACITY即64时, 才允许树化,此时将所有链表树化
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
HashMap的put过程3--红黑树.png
HashMap的扩容过程.png
HashMap的另一个扩容算法.png
Node中的hash值是用hash算法得到的，目的是均匀放置，
那如果put的过于频繁，会造成不同的key-value计算出了同一个hash，
这个时候hash冲突了，那么这2个Node都放置到了数组的同一个位置。
HashMap是怎么处理这个问题的呢？
JDK8解决hash冲突
在JDK8之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。
在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。
为了解决在频繁冲突时HashMap性能降低的问题，JDK8中使用平衡树来替代链表存储冲突的元素。
这意味着我们可以将最坏情况下的性能从O(n)提高到O(logN)。
在JDK8中使用'常量TREEIFY_THRESHOLD'来控制是否从链表切换到平衡树来存储。
JDK8解决hash冲突问题.png
JDK7解决hash冲突
Hashmap里面的bucket出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题。
#通常是两种方法：链表法和开放地址法。
>> 链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；
>> 开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。
HashMap采用的链表法的方式，链表是单向链表。
#解决方案：
HashMap的数据结构是：数组Node[]与链表Node中有next Node.
(1)如果persons.put(“ad”,”jack”);persons.put(“bc”,”john”); 同时计算到 key 的hash值都为123:
那么jack先放在第一列的第一个位置Node-jack;
persons.put(“bc”,”john”) 执行时会将Node-jack的next(Node) = Node(john)，Jack的下个节点将指向Node(john)。
(2)那么取的时候呢，persons.get(“bc”)，这个时候取得的hash值是123，即table[123]，
这时table[123]首位是Node-jack，Key值(ad≠bc)不相等，取Node-jack的next下个Node，
即Node-John，这时Key值相等了，然后返回对应的person.
JDK7解决hash冲突.png
https://www.jianshu.com/p/d86618c549a6 (参看此文)
关于HashMap初始容量设置的问题
假设真实的需要传入的k-v对的个数为n, 则其初始容量公式为:
count = n / loadFactor(负载因子, 默认0.75f) + 1.0f
即:
HashMap<String, String> map = new HashMap<>(count);
或: (Maps 为 google-guava 中工具类)
HashMap<String, String> hashMap = Maps.newHashMapWithExpectedSize(n);
Maps.newHashMapWithExpectedSize.png
https://blog.csdn.net/Muyu_Z/article/details/80519123
https://blog.csdn.net/u010890358/article/details/80496144
https://blog.csdn.net/u010775025/article/details/79474023 (jdk7解决Hash冲突)
99.2 LinkedHashMap<K,V>
数组+链表+红黑树实现的，由双向链表实现元素的顺序。
添加、查询、删除元素的效率都高，且元素都是有序的(按插入顺序)。
线程不安全。
key和value都允许为null。
继承自HashMap, 扩容及存储机制与HashMap类似。
LinkedHashMap其实就是可以看成HashMap的基础上，多了一个双向链表来维持顺序。
putVal时重写了newNode(hash, key, value, null) 方法
#额外属性:
/**
* The head (eldest) of the doubly linked list.
* 记录第一个 key—value 对象
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
* 保存最后一个 key—value 对象
*/
transient LinkedHashMap.Entry<K,V> tail;
99.3 TreeMap<K,V>
是通过红黑树实现的。
查询效率高，且元素是排过序的。线程不安全。
key不允许为null, value可以为null。
java.util.TreeMap#put.png
TreeMap之红黑树.png
关于Comparator<T>与Comparable<T>接口实现排序
package com.zy.netty.compare;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class CompareTest {
@Test
public void fn01() {
// 方法一: 利用Comparable的compareTo方法
List<Person> list = new ArrayList<>();
list.add(new Person(3));
list.add(new Person(1));
list.add(new Person(2));
Collections.sort(list);
System.out.println(list);
// 方法二: 利用Comparator的compare方法
List<Stu> list1 = new ArrayList<>();
list1.add(new Stu(3));
list1.add(new Stu(1));
list1.add(new Stu(2));
list1.sort(new StuComparator().reversed());
System.out.println(list1);
// 方法三: 利用lambda来排序, 本质上还是Comparator
List<Stu> list2 = new ArrayList<>();
list2.add(new Stu(3));
list2.add(new Stu(1));
list2.add(new Stu(2));
list2.sort(Comparator.comparingInt(Stu::getAge).reversed());
System.out.println(list2);
}
@Data
@AllArgsConstructor
@NoArgsConstructor
private class Person implements Comparable<Person> {
private Integer age;
@Override
public int compareTo(Person o) {
return this.getAge() - o.getAge();
}
}
@Data
@AllArgsConstructor
@NoArgsConstructor
private class Stu {
private Integer age;
}
private class StuComparator implements Comparator<Stu> {
@Override
public int compare(Stu o1, Stu o2) {
return o1.getAge() - o2.getAge();
}
}
}
99.4 ConcurrentHashMap<K,V>
数组+链表+红黑树的实现方式来设计。
内部大量采用CAS操作, 内置变量volatile保证可见性, 同时也运用了synchronized锁机制。
所以是线程安全的容器类。
JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。
ConcurrentHashMap的put过程1.png
>> 1.根据 key 计算出 hashcode 。
>> 2.判断是否需要进行初始化。
>> 3.f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，
利用 CAS 尝试写入，失败则自旋保证成功。
>> 4.如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
>> 5.如果都不满足，则利用 synchronized 锁写入数据。
>> 6.如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
ConcurrentHashMap的put过程2.png
ConcurrentHashMap树化的树.png
99.5 Hashtable<K,V>
由hash表实现，为了成功地在哈希表中存储和获取对象，用作键的对象必须实现hashCode和equals方法。
元素无序, 效率低, 线程安全。
"不允许插入 null 值。"
java.util.Hashtable#put.png
99.6 ConcurrentSkipListMap<K,V>
ConcurrentSkipListMap提供的功能类似于TreeSet，能够并发的访问有序的set。
因为ConcurrentSkipListMap是基于“跳跃列表（skip list）”实现的，
只要多个线程没有同时修改集合的同一个部分，
那么在正常读、写集合的操作中不会出现竞争现象。
>> 所有操作都是无阻塞的，所有操作都可以并行，包括写
>> 实现了ConcurrentMap接口，直接支持一些原子复合操作(与ConcurrentHashMap类似)
>> 可排序(与TreeMap一样)，默认按键自然有序，可以传递比较器自定义排序，实现了SortedMap和NavigableMap接口。
ConcurrentSkipListMap.png
99.7 WeakHashMap<K,V>
由数组+单向链表实现, 无序, 线程不安全, 键和值都可以是null.
默认情况下，初始容量为16，负载因子为0.75.
扩容为原来的两倍大, 将元素从旧Map迁移到新表时，若size小于threshold/2，
重新将数据从新表迁移到旧表(因为迁移的时候会删除已经被回收的条目：key为null)
其内部维护了一个 ReferenceQueue:
/**
* Reference queue for cleared WeakEntries
*/
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
99.8 IdentityHashMap<K,V>
此类实现 Map 接口时，它有意违反 Map 的常规协定，该协定在比较对象时强制使用 equals 方法。此类设计仅用于其中需要引用相等性语义的罕见情况。
由数组实现, 无序, 线程不安全, 键和值都可以是null.
采用 == 的方法比较key是否相等.
>> IdentityHashMap的实现不同于HashMap，虽然也是数组，
不过IdentityHashMap中没有用到链表，解决冲突的方式是计算下一个有效索引，
并且将数据key和value紧挨着存在map中，即table[i]=key，那么table[i+1]=value。
比如对于要保存的key，k1和k2，当且仅当k1== k2的时候，IdentityHashMap才会相等，
而对于HashMap来说，相等的条件则是：(k1==null ? k2==null : k1.equals(k2))。
>> IdentityHashMap的hash的计算没有使用Object的hashCode方法，
而是使用的System.identityHashCode方法，
这是Object.hashCode方法根据对象的内存地址来计算散列码时所使用的方式。
>> 其实有的时候我们常说的IdentityHashMap能保存重复的key是一种不太恰当的说法，
因为IdentityHashMap的==操作是比较的内存地址，如果不是指向同一块内存，那这时候才可以保存相同的数据。
IdentityHashMap.png
99.9 EnumMap<K extends Enum<K>, V>
EnumMap是专门为枚举类型量身定做的Map实现
《Effective Java》中作者建议用EnumMap取代叙述索引
由数组组成, 不允许空的键, 允许空值, 线程不安全, 按照枚举key中的顺序排序.
用于枚举类型键的专用Map实现。
EnumMap映射中的所有键必须来自创建映射时显式或隐式指定的单个枚举类型。
枚举映射在内部表示为数组， 枚举映射按其键的自然顺序（枚举常量的声明顺序）维护。
这反映在集合视图keySet()，entrySet()和values()返回的迭代器中。
集合视图返回的迭代器非常一致：它们永远不会抛出ConcurrentModificationException，
它们可能会也可能不会显示出迭代进行过程中对映射所做的修改的而对其造成的影响。
EnumMap.png
100.List<E>接口相关实现类数据结构
100.1 ArrayList<E>
由数组实现。
访问元素的效率比较高，删除和添加元素效率低。线程不安全。
允许插入 null 值。
ArrayList的底层数据结构就是一个数组，数组元素的类型为Object类型，对ArrayList的所有操作底层都是基于数组的。
它实现了List<E>, RandomAccess, Cloneable, java.io.Serializable 接口:
>> RandomAccess 代表List获取了随机访问功能，也就是通过下标获取元素对象的功能。
>> 实现了Cloneable接口可以被克隆。
>> 实现了Serializable了接口并重写了序列化和反序列化方法，使得ArrayList可以拥有更好的序列化的性能。
#基本属性
//默认的数组存储容量
private static final int DEFAULT_CAPACITY = 10;
//当指定数组的容量为0的时候使用这个变量赋值
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认的实例化的时候使用此变量赋值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//真正存放数据的对象数组，并不被序列化
transient Object[] elementData;
//数组中的真实元素个数它小于或等于elementData.length
private int size;
//数组中最大存放元素的个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8;
ArrayList的扩容
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 按照旧容量的1.5倍扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果旧容量的1.5倍仍小于minCapacity, 那新容量就取minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于MAX_ARRAY_SIZE, 就取MAX_ARRAY_SIZE或者Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 利用native方法进行数组的copy
elementData = Arrays.copyOf(elementData, newCapacity);
}
100.2 LinkedList<E>
由链表实现。
插入、删除元素效率比较高，访问效率比较低。线程不安全。
允许插入 null 值。
>> LinkedList 是一个继承于AbstractSequentialList的双向链表。
它也可以被当作堆栈、队列或双端队列进行操作。
>> LinkedList 实现 List 接口，能对它进行队列操作。
>> LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
>> LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
>> LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
>> LinkedList 是非同步的。
>> LinkedList实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。
#基本属性
//当前有多少个节点
transient int size = 0;
//第一个节点
transient Node<E> first;
//最后一个节点
transient Node<E> last;
"详细图见本文 4.2双向链表"
LinkedList的add方法分析
public boolean add(E e) {
linkLast(e); // add方法, 默认加到链表尾部
return true;
}
void linkLast(E e) {
final Node<E> l = last; // 将最后一个节点赋值给变量l
final Node<E> newNode = new Node<>(l, e, null); // 新建一个节点
last = newNode; // 将新节点赋值给最后一个节点
if (l == null) // 若l为null, 则将新节点赋值处理成第一个节点
first = newNode;
else
l.next = newNode; // 否则,将上一个节点的next指向新节点
size++; // 链表容量++
modCount++; // 修改次数++
}
private static class Node<E> { // 链表的数据结构Node
E item; // 当前元素
Node<E> next; // 下一个元素
Node<E> prev; // 上一个元素
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
100.3 CopyOnWriteArrayList<E>
由数组实现。
线程安全的并发容器类。
允许插入 null 值。
CopyOnWriteArrayList实现了List接口,
实现了RandomAccess接口，表示可以随机访问（数组具有随机访问的特性）；
实现了Cloneable接口，表示可克隆；
也实现了Serializable接口，表示可被序列化。
#基本属性
// 可重入锁, 此处是非公平锁
final transient ReentrantLock lock = new ReentrantLock();
// volatile对象数组，用于存放元素, 保证内存可见性
private transient volatile Object[] array;
// 反射机制获取底层Unsafe类
private static final sun.misc.Unsafe UNSAFE;
// lock域的内存偏移量
private static final long lockOffset;
CopyOnWriteArrayList的add方法
public boolean add(E e) {
final ReentrantLock lock = this.lock; // 可重入锁
lock.lock(); // 加锁
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); // 调用navtive的copy方法进行数组copy
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock(); // 释放锁
}
}
100.4 Vector<E>
由数组实现。
访问元素的效率比较高，删除和添加元素效率低。线程安全。
允许插入 null 值。
其实现原理与ArrayList大体类似, 只是各方法上多了synchronized同步锁, 保证线程安全。
101.Set<E>接口相关实现类数据结构
101.1 HashSet<E>
由哈希表实现。
添加、查询、删除元素的效率都很高，元素无序, 线程不安全。
通过hashcode与equals方法确保元素的唯一。
允许插入 null 值。
实现原理参考HashMap
101.2 LinkedHashSet<E>
由哈希表实现元素的存储，由链表实现元素的顺序(插入顺序即为元素顺序)。
添加、查询、删除元素的效率都高，线程不安全。
允许插入 null 值。
实现原理参考LinkedHashMap
101.3 TreeSet<E>
由二叉树实现。
查询效率高，且元素有序的。线程不安全。
存放自定义类型的对象需要实现Comparable接口，重写compareTo方法，提供对象排序的方式。
"不允许插入 null 值。"
实现原理参考TreeMap
101.4 CopyOnWriteArraySet<E>
由数组实现。
允许插入 null 值。
#基本属性
private final CopyOnWriteArrayList<E> al;
实现原理参考CopyOnWriteArrayList
101.5ConcurrentSkipListSet<K,V>
并发可排序Set集合
实现原理参考ConcurrentSkipListMap
102.Queue<E>接口相关实现类数据结构
https://blog.csdn.net/Muyu_Z/article/details/80519123
https://www.cnblogs.com/leesf456/archive/2016/03.html
https://blog.csdn.net/xzp_12345/article/details/79251174
--------------- jdk中部分class(集合)数据结构结束 ---------------
参考资源
