做一个网站的建设过程,appcan wordpress插件,发广告,工具网站有哪些视频地址#xff1a;https://www.yuque.com/linxun-bpyj0/linxun/vy91es9lyg7kbfnr
大纲 基础篇
基础篇要点#xff1a;算法、数据结构、基础设计模式
1. 二分查找
要求
能够用自己语言描述二分查找算法能够手写二分查找代码能够解答一些变化后的考法
算法描述
前提https://www.yuque.com/linxun-bpyj0/linxun/vy91es9lyg7kbfnr
大纲 基础篇
基础篇要点算法、数据结构、基础设计模式
1. 二分查找
要求
能够用自己语言描述二分查找算法能够手写二分查找代码能够解答一些变化后的考法
算法描述
前提有已排序数组 A假设已经做好定义左边界 L、右边界 R确定搜索范围循环执行二分查找3、4两步获取中间索引 M Floor((LR) /2)中间索引的值 A[M] 与待搜索的值 T 进行比较 ① A[M] T 表示找到返回中间索引 ② A[M] T中间值右侧的其它元素都大于 T无需比较中间索引左边去找M - 1 设置为右边界重新查找 ③ A[M] T中间值左侧的其它元素都小于 T无需比较中间索引右边去找 M 1 设置为左边界重新查找当 L R 时表示没有找到应结束循环
更形象的描述请参考binary_search.html
算法实现
public static int binarySearch(int[] a, int t) {int l 0, r a.length - 1, m;while (l r) {m (l r) / 2;if (a[m] t) {return m;} else if (a[m] t) {r m - 1;} else {l m 1;}}return -1;
}测试代码
public static void main(String[] args) {int[] array {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};int target 47;int idx binarySearch(array, target);System.out.println(idx);
}解决整数溢出问题
当 l 和 r 都较大时l r 有可能超过整数范围造成运算错误解决方法有两种
int m l (r - l) / 2;还有一种是
int m (l r) 1;其它考法
有一个有序表为 1,5,8,11,19,22,31,35,40,45,48,49,50 当二分查找值为 48 的结点时查找成功需要比较的次数使用二分法在序列 1,4,6,7,15,33,39,50,64,78,75,81,89,96 中查找元素 81 时需要经过 次比较在拥有128个元素的数组中二分查找一个数需要比较的次数最多不超过多少次
对于前两个题目记得一个简要判断口诀奇数二分取中间偶数二分取中间靠左。对于后一道题目需要知道公式 其中 n 为查找次数N 为元素个数
2. 冒泡排序
要求
能够用自己语言描述冒泡排序算法能够手写冒泡排序代码了解一些冒泡排序的优化手段
算法描述
依次比较数组中相邻两个元素大小若 a[j] a[j1]则交换两个元素两两都比较一遍称为一轮冒泡结果是让最大的元素排至最后重复以上步骤直到整个数组有序
更形象的描述请参考bubble_sort.html
算法实现
public static void bubble(int[] a) {for (int j 0; j a.length - 1; j) {// 一轮冒泡boolean swapped false; // 是否发生了交换for (int i 0; i a.length - 1 - j; i) {System.out.println(比较次数 i);if (a[i] a[i 1]) {Utils.swap(a, i, i 1);swapped true;}}System.out.println(第 j 轮冒泡 Arrays.toString(a));if (!swapped) {break;}}
}优化点1每经过一轮冒泡内层循环就可以减少一次优化点2如果某一轮冒泡没有发生交换则表示所有数据有序可以结束外层循环
进一步优化
public static void bubble_v2(int[] a) {int n a.length - 1;while (true) {int last 0; // 表示最后一次交换索引位置for (int i 0; i n; i) {System.out.println(比较次数 i);if (a[i] a[i 1]) {Utils.swap(a, i, i 1);last i;}}n last;System.out.println(第轮冒泡 Arrays.toString(a));if (n 0) {break;}}
}每轮冒泡时最后一次交换索引可以作为下一轮冒泡的比较次数如果这个值为零表示整个数组有序直接退出外层循环即可
3. 选择排序
要求
能够用自己语言描述选择排序算法能够比较选择排序与冒泡排序理解非稳定排序与稳定排序
算法描述
将数组分为两个子集排序的和未排序的每一轮从未排序的子集中选出最小的元素放入排序子集重复以上步骤直到整个数组有序
更形象的描述请参考selection_sort.html
算法实现
public static void selection(int[] a) {for (int i 0; i a.length - 1; i) {// i 代表每轮选择最小元素要交换到的目标索引int s i; // 代表最小元素的索引for (int j s 1; j a.length; j) {if (a[s] a[j]) { // j 元素比 s 元素还要小, 更新 ss j;}}if (s ! i) {swap(a, s, i);}System.out.println(Arrays.toString(a));}
}优化点为减少交换次数每一轮可以先找最小的索引在每轮最后再交换元素
与冒泡排序比较
二者平均时间复杂度都是 选择排序一般要快于冒泡因为其交换次数少但如果集合有序度高冒泡优于选择冒泡属于稳定排序算法而选择属于不稳定排序 稳定排序指按对象中不同字段进行多次排序不会打乱同值元素的顺序不稳定排序则反之
稳定排序与不稳定排序
System.out.println(不稳定);
Card[] cards getStaticCards();
System.out.println(Arrays.toString(cards));
selection(cards, Comparator.comparingInt((Card a) - a.sharpOrder).reversed());
System.out.println(Arrays.toString(cards));
selection(cards, Comparator.comparingInt((Card a) - a.numberOrder).reversed());
System.out.println(Arrays.toString(cards));System.out.println(稳定);
cards getStaticCards();
System.out.println(Arrays.toString(cards));
bubble(cards, Comparator.comparingInt((Card a) - a.sharpOrder).reversed());
System.out.println(Arrays.toString(cards));
bubble(cards, Comparator.comparingInt((Card a) - a.numberOrder).reversed());
System.out.println(Arrays.toString(cards));都是先按照花色排序♠♥♣♦再按照数字排序AKQJ…
不稳定排序算法按数字排序时会打乱原本同值的花色顺序
[[♠7], [♠2], [♠4], [♠5], [♥2], [♥5]]
[[♠7], [♠5], [♥5], [♠4], [♥2], [♠2]]原来 ♠2 在前 ♥2 在后按数字再排后他俩的位置变了
稳定排序算法按数字排序时会保留原本同值的花色顺序如下所示 ♠2 与 ♥2 的相对位置不变
[[♠7], [♠2], [♠4], [♠5], [♥2], [♥5]]
[[♠7], [♠5], [♥5], [♠4], [♠2], [♥2]]4. 插入排序
要求
能够用自己语言描述插入排序算法能够比较插入排序与选择排序
算法描述
将数组分为两个区域排序区域和未排序区域每一轮从未排序区域中取出第一个元素插入到排序区域需保证顺序重复以上步骤直到整个数组有序
更形象的描述请参考insertion_sort.html
算法实现
// 修改了代码与希尔排序一致
public static void insert(int[] a) {// i 代表待插入元素的索引for (int i 1; i a.length; i) {int t a[i]; // 代表待插入的元素值int j i;System.out.println(j);while (j 1) {if (t a[j - 1]) { // j-1 是上一个元素索引如果 t后移a[j] a[j - 1];j--;} else { // 如果 j-1 已经 t, 则 j 就是插入位置break;}}a[j] t;System.out.println(Arrays.toString(a) j);}
}与选择排序比较
二者平均时间复杂度都是 大部分情况下插入都略优于选择有序集合插入的时间复杂度为 插入属于稳定排序算法而选择属于不稳定排序
提示
插入排序通常被同学们所轻视其实它的地位非常重要。小数据量排序都会优先选择插入排序
5. 希尔排序
要求
能够用自己语言描述希尔排序算法
算法描述
首先选取一个间隙序列如 (n/2n/4 … 1)n 为数组长度每一轮将间隙相等的元素视为一组对组内元素进行插入排序目的有二 ① 少量元素插入排序速度很快 ② 让组内值较大的元素更快地移动到后方当间隙逐渐减少直至为 1 时即可完成排序
更形象的描述请参考shell_sort.html
算法实现
private static void shell(int[] a) {int n a.length;for (int gap n / 2; gap 0; gap / 2) {// i 代表待插入元素的索引for (int i gap; i n; i) {int t a[i]; // 代表待插入的元素值int j i;while (j gap) {// 每次与上一个间隙为 gap 的元素进行插入排序if (t a[j - gap]) { // j-gap 是上一个元素索引如果 t后移a[j] a[j - gap];j - gap;} else { // 如果 j-1 已经 t, 则 j 就是插入位置break;}}a[j] t;System.out.println(Arrays.toString(a) gap: gap);}}
}参考资料
https://en.wikipedia.org/wiki/Shellsort
6. 快速排序
要求
能够用自己语言描述快速排序算法掌握手写单边循环、双边循环代码之一能够说明快排特点了解洛穆托与霍尔两种分区方案的性能比较
算法描述
每一轮排序选择一个基准点pivot进行分区 让小于基准点的元素的进入一个分区大于基准点的元素的进入另一个分区当分区完成时基准点元素的位置就是其最终位置 在子分区内重复以上过程直至子分区元素个数少于等于 1这体现的是分而治之的思想 divide-and-conquer从以上描述可以看出一个关键在于分区算法常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案
更形象的描述请参考quick_sort.html
单边循环快排lomuto 洛穆托分区方案
选择最右元素作为基准点元素j 指针负责找到比基准点小的元素一旦找到则与 i 进行交换i 指针维护小于基准点元素的边界也是每次交换的目标索引最后基准点与 i 交换i 即为分区位置
public static void quick(int[] a, int l, int h) {if (l h) {return;}int p partition(a, l, h); // p 索引值quick(a, l, p - 1); // 左边分区的范围确定quick(a, p 1, h); // 左边分区的范围确定
}private static int partition(int[] a, int l, int h) {int pv a[h]; // 基准点元素int i l;for (int j l; j h; j) {if (a[j] pv) {if (i ! j) {swap(a, i, j);}i;}}if (i ! h) {swap(a, h, i);}System.out.println(Arrays.toString(a) i i);// 返回值代表了基准点元素所在的正确索引用它确定下一轮分区的边界return i;
}双边循环快排不完全等价于 hoare 霍尔分区方案
选择最左元素作为基准点元素j 指针负责从右向左找比基准点小的元素i 指针负责从左向右找比基准点大的元素一旦找到二者交换直至 ij 相交最后基准点与 i此时 i 与 j 相等交换i 即为分区位置
要点
基准点在左边并且要先 j 后 iwhile( i j a[j] pv ) j–while ( i j a[i] pv ) i
private static void quick(int[] a, int l, int h) {if (l h) {return;}int p partition(a, l, h);quick(a, l, p - 1);quick(a, p 1, h);
}private static int partition(int[] a, int l, int h) {int pv a[l];int i l;int j h;while (i j) {// j 从右找小的while (i j a[j] pv) {j--;}// i 从左找大的while (i j a[i] pv) {i;}swap(a, i, j);}swap(a, l, j);System.out.println(Arrays.toString(a) j j);return j;
}快排特点
平均时间复杂度是 最坏时间复杂度 数据量较大时优势非常明显属于不稳定排序
洛穆托分区方案 vs 霍尔分区方案
霍尔的移动次数平均来讲比洛穆托少3倍https://qastack.cn/cs/11458/quicksort-partitioning-hoare-vs-lomuto
补充代码说明
day01.sort.QuickSort3 演示了空穴法改进的双边快排比较次数更少day01.sort.QuickSortHoare 演示了霍尔分区的实现day01.sort.LomutoVsHoare 对四种分区实现的移动次数比较
7. ArrayList
要求
掌握 ArrayList 扩容规则
扩容规则
ArrayList() 会使用长度为零的数组ArrayList(int initialCapacity) 会使用指定容量的数组public ArrayList(Collection? extends E c) 会使用 c 的大小作为数组容量add(Object o) 首次扩容为 10再次扩容为上次容量的 1.5 倍addAll(Collection c) 没有元素时扩容为 Math.max(10, 实际元素个数)有元素时为 Math.max(原容量 1.5 倍, 实际元素个数)
其中第 4 点必须知道其它几点视个人情况而定
提示
测试代码见 day01.list.TestArrayList 这里不再列出要注意的是示例中用反射方式来更直观地反映 ArrayList 的扩容特征但从 JDK 9 由于模块化的影响对反射做了较多限制需要在运行测试代码时添加 VM 参数 --add-opens java.base/java.utilALL-UNNAMED 方能运行通过后面的例子都有相同问题
代码说明
day01.list.TestArrayList#arrayListGrowRule 演示了 add(Object) 方法的扩容规则输入参数 n 代表打印多少次扩容后的数组长度
8. Iterator
要求
掌握什么是 Fail-Fast、什么是 Fail-Safe
Fail-Fast 与 Fail-Safe
ArrayList 是 fail-fast 的典型代表遍历的同时不能修改尽快失败CopyOnWriteArrayList 是 fail-safe 的典型代表遍历的同时可以修改原理是读写分离
提示
测试代码见 day01.list.FailFastVsFailSafe这里不再列出
9. LinkedList
要求
能够说清楚 LinkedList 对比 ArrayList 的区别并重视纠正部分错误的认知
LinkedList
基于双向链表无需连续内存随机访问慢要沿着链表遍历头尾插入删除性能高占用内存多
ArrayList
基于数组需要连续内存随机访问快指根据下标访问尾部插入、删除性能可以其它部分插入、删除都会移动数据因此性能会低可以利用 cpu 缓存局部性原理
代码说明
day01.list.ArrayListVsLinkedList#randomAccess 对比随机访问性能day01.list.ArrayListVsLinkedList#addMiddle 对比向中间插入性能day01.list.ArrayListVsLinkedList#addFirst 对比头部插入性能day01.list.ArrayListVsLinkedList#addLast 对比尾部插入性能day01.list.ArrayListVsLinkedList#linkedListSize 打印一个 LinkedList 占用内存day01.list.ArrayListVsLinkedList#arrayListSize 打印一个 ArrayList 占用内存
10. HashMap
要求
掌握 HashMap 的基本数据结构掌握树化理解索引计算方法、二次 hash 的意义、容量对索引计算的影响掌握 put 流程、扩容、扩容因子理解并发使用 HashMap 可能导致的问题理解 key 的设计
1基本数据结构
1.7 数组 链表1.8 数组 链表 | 红黑树
更形象的演示见资料中的 hash-demo.jar运行需要 jdk14 以上环境进入 jar 包目录执行下面命令
java -jar --add-exports java.base/jdk.internal.miscALL-UNNAMED hash-demo.jar2树化与退化
树化意义
红黑树用来避免 DoS 攻击防止链表超长时性能下降树化应当是偶然情况是保底策略hash 表的查找更新的时间复杂度是 而红黑树的查找更新的时间复杂度是 TreeNode 占用空间也比普通 Node 的大如非必要尽量还是使用链表hash 值如果足够随机则在 hash 表内按泊松分布在负载因子 0.75 的情况下长度超过 8 的链表出现概率是 0.00000006树化阈值选择 8 就是为了让树化几率足够小
树化规则
当链表长度超过树化阈值 8 时先尝试扩容来减少链表长度如果数组容量已经 64才会进行树化
退化规则
情况1在扩容时如果拆分树时树元素个数 6 则会退化链表情况2remove 树节点时若 root、root.left、root.right、root.left.left 有一个为 null 也会退化为链表
3索引计算
索引计算方法
首先计算对象的 hashCode()再进行调用 HashMap 的 hash() 方法进行二次哈希 二次 hash() 是为了综合高位数据让哈希分布更为均匀 最后 (capacity – 1) 得到索引
数组容量为何是 2 的 n 次幂
计算索引时效率更高如果是 2 的 n 次幂可以使用位与运算代替取模扩容时重新计算索引效率更高 hash oldCap 0 的元素留在原来位置 否则新位置 旧位置 oldCap
注意
二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提如果 hash 表的容量不是 2 的 n 次幂则不必二次 hash容量是 2 的 n 次幂 这一设计计算索引效率更好但 hash 的分散性就不好需要二次 hash 来作为补偿没有采用这一设计的典型例子是 Hashtable
4put 与扩容
put 流程
HashMap 是懒惰创建数组的首次使用才创建数组计算索引桶下标如果桶下标还没人占用创建 Node 占位返回如果桶下标已经有人占用 已经是 TreeNode 走红黑树的添加或更新逻辑是普通 Node走链表的添加或更新逻辑如果链表长度超过树化阈值走树化逻辑 返回前检查容量是否超过阈值一旦超过进行扩容
1.7 与 1.8 的区别
链表插入节点时1.7 是头插法1.8 是尾插法1.7 是大于等于阈值且没有空位时才扩容而 1.8 是大于阈值就扩容1.8 在扩容计算 Node 索引时会优化
扩容加载因子为何默认是 0.75f
在空间占用与查询时间之间取得较好的权衡大于这个值空间节省了但链表就会比较长影响性能小于这个值冲突减少了但扩容就会更频繁空间占用也更多
5并发问题
扩容死链1.7 会存在
1.7 源码如下
void transfer(Entry[] newTable, boolean rehash) {int newCapacity newTable.length;for (EntryK,V e : table) {while(null ! e) {EntryK,V next e.next;if (rehash) {e.hash null e.key ? 0 : hash(e.key);}int i indexFor(e.hash, newCapacity);e.next newTable[i];newTable[i] e;e next;}}
}e 和 next 都是局部变量用来指向当前节点和下一个节点线程1绿色的临时变量 e 和 next 刚引用了这俩节点还未来得及移动节点发生了线程切换由线程2蓝色完成扩容和迁移 线程2 扩容完成由于头插法链表顺序颠倒。但线程1 的临时变量 e 和 next 还引用了这俩节点还要再来一遍迁移 第一次循环 循环接着线程切换前运行注意此时 e 指向的是节点 anext 指向的是节点 be 头插 a 节点注意图中画了两份 a 节点但事实上只有一个为了不让箭头特别乱画了两份当循环结束是 e 会指向 next 也就是 b 节点 第二次循环 next 指向了节点 ae 头插节点 b当循环结束时e 指向 next 也就是节点 a
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A3enIgab-1691920287269)()]
第三次循环 next 指向了 nulle 头插节点 aa 的 next 指向了 b之前 a.next 一直是 nullb 的 next 指向 a死链已成当循环结束时e 指向 next 也就是 null因此第四次循环时会正常退出 数据错乱1.71.8 都会存在
代码参考 day01.map.HashMapMissData具体调试步骤参考视频
补充代码说明
day01.map.HashMapDistribution 演示 map 中链表长度符合泊松分布day01.map.DistributionAffectedByCapacity 演示容量及 hashCode 取值对分布的影响 day01.map.DistributionAffectedByCapacity#hashtableGrowRule 演示了 Hashtable 的扩容规律day01.sort.Utils#randomArray 如果 hashCode 足够随机容量是否是 2 的 n 次幂影响不大day01.sort.Utils#lowSameArray 如果 hashCode 低位一样的多容量是 2 的 n 次幂会导致分布不均匀day01.sort.Utils#evenArray 如果 hashCode 偶数的多容量是 2 的 n 次幂会导致分布不均匀由此得出对于容量是 2 的 n 次幂的设计来讲二次 hash 非常重要 day01.map.HashMapVsHashtable 演示了对于同样数量的单词字符串放入 HashMap 和 Hashtable 分布上的区别
6key 的设计
key 的设计要求
HashMap 的 key 可以为 null但 Map 的其他实现则不然作为 key 的对象必须实现 hashCode 和 equals并且 key 的内容不能修改不可变key 的 hashCode 应该有良好的散列性
如果 key 可变例如修改了 age 会导致再次查询时查询不到
public class HashMapMutableKey {public static void main(String[] args) {HashMapStudent, Object map new HashMap();Student stu new Student(张三, 18);map.put(stu, new Object());System.out.println(map.get(stu));stu.age 19;System.out.println(map.get(stu));}static class Student {String name;int age;public Student(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;return age student.age Objects.equals(name, student.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}}
}String 对象的 hashCode() 设计
目标是达到较为均匀的散列效果每个字符串的 hashCode 足够独特字符串中的每个字符都可以表现为一个数字称为 其中 i 的范围是 0 ~ n - 1散列公式为 31 代入公式有较好的散列特性并且 31 * h 可以被优化为 即 $32 ∗h -h $即 即
11. 单例模式
要求
掌握五种单例模式的实现方式理解为何 DCL 实现时要使用 volatile 修饰静态变量了解 jdk 中用到单例的场景
饿汉式
public class Singleton1 implements Serializable {private Singleton1() {if (INSTANCE ! null) {throw new RuntimeException(单例对象不能重复创建);}System.out.println(private Singleton1());}private static final Singleton1 INSTANCE new Singleton1();public static Singleton1 getInstance() {return INSTANCE;}public static void otherMethod() {System.out.println(otherMethod());}public Object readResolve() {return INSTANCE;}
}构造方法抛出异常是防止反射破坏单例readResolve() 是防止反序列化破坏单例
枚举饿汉式
public enum Singleton2 {INSTANCE;private Singleton2() {System.out.println(private Singleton2());}Overridepublic String toString() {return getClass().getName() Integer.toHexString(hashCode());}public static Singleton2 getInstance() {return INSTANCE;}public static void otherMethod() {System.out.println(otherMethod());}
}枚举饿汉式能天然防止反射、反序列化破坏单例
懒汉式
public class Singleton3 implements Serializable {private Singleton3() {System.out.println(private Singleton3());}private static Singleton3 INSTANCE null;// Singleton3.classpublic static synchronized Singleton3 getInstance() {if (INSTANCE null) {INSTANCE new Singleton3();}return INSTANCE;}public static void otherMethod() {System.out.println(otherMethod());}}其实只有首次创建单例对象时才需要同步但该代码实际上每次调用都会同步因此有了下面的双检锁改进
双检锁懒汉式
public class Singleton4 implements Serializable {private Singleton4() {System.out.println(private Singleton4());}private static volatile Singleton4 INSTANCE null; // 可见性有序性public static Singleton4 getInstance() {if (INSTANCE null) {synchronized (Singleton4.class) {if (INSTANCE null) {INSTANCE new Singleton4();}}}return INSTANCE;}public static void otherMethod() {System.out.println(otherMethod());}
}为何必须加 volatile
INSTANCE new Singleton4() 不是原子的分成 3 步创建对象、调用构造、给静态变量赋值其中后两步可能被指令重排序优化变成先赋值、再调用构造如果线程1 先执行了赋值线程2 执行到第一个 INSTANCE null 时发现 INSTANCE 已经不为 null此时就会返回一个未完全构造的对象
内部类懒汉式
public class Singleton5 implements Serializable {private Singleton5() {System.out.println(private Singleton5());}private static class Holder {static Singleton5 INSTANCE new Singleton5();}public static Singleton5 getInstance() {return Holder.INSTANCE;}public static void otherMethod() {System.out.println(otherMethod());}
}避免了双检锁的缺点
JDK 中单例的体现
Runtime 体现了饿汉式单例Console 体现了双检锁懒汉式单例Collections 中的 EmptyNavigableSet 内部类懒汉式单例ReverseComparator.REVERSE_ORDER 内部类懒汉式单例Comparators.NaturalOrderComparator.INSTANCE 枚举饿汉式单例
并发篇
1. 线程状态
要求
掌握 Java 线程六种状态掌握 Java 线程状态转换能理解五种状态与六种状态两种说法的区别
六种状态及转换 分别是
新建 当一个线程对象被创建但还未调用 start 方法时处于新建状态此时未与操作系统底层线程关联 可运行 调用了 start 方法就会由新建进入可运行此时与底层线程关联由操作系统调度执行 终结 线程内代码已经执行完毕由可运行进入终结此时会取消与底层线程关联 阻塞 当获取锁失败后由可运行进入 Monitor 的阻塞队列阻塞此时不占用 cpu 时间当持锁线程释放锁时会按照一定规则唤醒阻塞队列中的阻塞线程唤醒后的线程进入可运行状态 等待 当获取锁成功后但由于条件不满足调用了 wait() 方法此时从可运行状态释放锁进入 Monitor 等待集合等待同样不占用 cpu 时间当其它持锁线程调用 notify() 或 notifyAll() 方法会按照一定规则唤醒等待集合中的等待线程恢复为可运行状态 有时限等待 当获取锁成功后但由于条件不满足调用了 wait(long) 方法此时从可运行状态释放锁进入 Monitor 等待集合进行有时限等待同样不占用 cpu 时间当其它持锁线程调用 notify() 或 notifyAll() 方法会按照一定规则唤醒等待集合中的有时限等待线程恢复为可运行状态并重新去竞争锁如果等待超时也会从有时限等待状态恢复为可运行状态并重新去竞争锁还有一种情况是调用 sleep(long) 方法也会从可运行状态进入有时限等待状态但与 Monitor 无关不需要主动唤醒超时时间到自然恢复为可运行状态
其它情况只需了解
可以用 interrupt() 方法打断等待、有时限等待的线程让它们恢复为可运行状态parkunpark 等方法也可以让线程等待和唤醒
五种状态
五种状态的说法来自于操作系统层面的划分 运行态分到 cpu 时间能真正执行线程内代码的就绪态有资格分到 cpu 时间但还未轮到它的阻塞态没资格分到 cpu 时间的 涵盖了 java 状态中提到的阻塞、等待、有时限等待多出了阻塞 I/O指线程在调用阻塞 I/O 时实际活由 I/O 设备完成此时线程无事可做只能干等 新建与终结态与 java 中同名状态类似不再啰嗦
2. 线程池
要求
掌握线程池的 7 大核心参数
七大参数
corePoolSize 核心线程数目 - 池中会保留的最多线程数maximumPoolSize 最大线程数目 - 核心线程救急线程的最大数目keepAliveTime 生存时间 - 救急线程的生存时间生存时间内没有新任务此线程资源会释放unit 时间单位 - 救急线程的生存时间单位如秒、毫秒等workQueue - 当没有空闲核心线程时新来任务会加入到此队列排队队列满会创建救急线程执行任务threadFactory 线程工厂 - 可以定制线程对象的创建例如设置线程名字、是否是守护线程等handler 拒绝策略 - 当所有线程都在繁忙workQueue 也放满时会触发拒绝策略 抛异常 java.util.concurrent.ThreadPoolExecutor.AbortPolicy由调用者执行任务 java.util.concurrent.ThreadPoolExecutor.CallerRunsPolicy丢弃任务 java.util.concurrent.ThreadPoolExecutor.DiscardPolicy丢弃最早排队任务 java.util.concurrent.ThreadPoolExecutor.DiscardOldestPolicy
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U9e6Mevj-1691920287271)()]
代码说明
day02.TestThreadPoolExecutor 以较为形象的方式演示了线程池的核心组成
3. wait vs sleep
要求
能够说出二者区别
一个共同点三个不同点
共同点
wait() wait(long) 和 sleep(long) 的效果都是让当前线程暂时放弃 CPU 的使用权进入阻塞状态
不同点
方法归属不同 sleep(long) 是 Thread 的静态方法而 wait()wait(long) 都是 Object 的成员方法每个对象都有 醒来时机不同 执行 sleep(long) 和 wait(long) 的线程都会在等待相应毫秒后醒来wait(long) 和 wait() 还可以被 notify 唤醒wait() 如果不唤醒就一直等下去它们都可以被打断唤醒 锁特性不同重点 wait 方法的调用必须先获取 wait 对象的锁而 sleep 则无此限制wait 方法执行后会释放对象锁允许其它线程获得该对象锁我放弃 cpu但你们还可以用而 sleep 如果在 synchronized 代码块中执行并不会释放对象锁我放弃 cpu你们也用不了
4. lock vs synchronized
要求
掌握 lock 与 synchronized 的区别理解 ReentrantLock 的公平、非公平锁理解 ReentrantLock 中的条件变量
三个层面
不同点
语法层面 synchronized 是关键字源码在 jvm 中用 c 语言实现Lock 是接口源码由 jdk 提供用 java 语言实现使用 synchronized 时退出同步代码块锁会自动释放而使用 Lock 时需要手动调用 unlock 方法释放锁 功能层面 二者均属于悲观锁、都具备基本的互斥、同步、锁重入功能Lock 提供了许多 synchronized 不具备的功能例如获取等待状态、公平锁、可打断、可超时、多条件变量Lock 有适合不同场景的实现如 ReentrantLock ReentrantReadWriteLock 性能层面 在没有竞争时synchronized 做了很多优化如偏向锁、轻量级锁性能不赖在竞争激烈时Lock 的实现通常会提供更好的性能
公平锁
公平锁的公平体现 已经处在阻塞队列中的线程不考虑超时始终都是公平的先进先出公平锁是指未处于阻塞队列中的线程来争抢锁如果队列不为空则老实到队尾等待非公平锁是指未处于阻塞队列中的线程来争抢锁与队列头唤醒的线程去竞争谁抢到算谁的 公平锁会降低吞吐量一般不用
条件变量
ReentrantLock 中的条件变量功能类似于普通 synchronized 的 waitnotify用在当线程获得锁后发现条件不满足时临时等待的链表结构与 synchronized 的等待集合不同之处在于ReentrantLock 中的条件变量可以有多个可以实现更精细的等待、唤醒控制
代码说明
day02.TestReentrantLock 用较为形象的方式演示 ReentrantLock 的内部结构
5. volatile
要求
掌握线程安全要考虑的三个问题掌握 volatile 能解决哪些问题
原子性
起因多线程下不同线程的指令发生了交错导致的共享变量的读写混乱解决用悲观锁或乐观锁解决volatile 并不能解决原子性
可见性
起因由于编译器优化、或缓存优化、或 CPU 指令重排序优化导致的对共享变量所做的修改另外的线程看不到解决用 volatile 修饰共享变量能够防止编译器等优化发生让一个线程对共享变量的修改对另一个线程可见
有序性
起因由于编译器优化、或缓存优化、或 CPU 指令重排序优化导致指令的实际执行顺序与编写顺序不一致解决用 volatile 修饰共享变量会在读、写共享变量时加入不同的屏障阻止其他读写操作越过屏障从而达到阻止重排序的效果注意 volatile 变量写加的屏障是阻止上方其它写操作越过屏障排到 volatile 变量写之下volatile 变量读加的屏障是阻止下方其它读操作越过屏障排到 volatile 变量读之上volatile 读写加入的屏障只能防止同一线程内的指令重排
代码说明
day02.threadsafe.AddAndSubtract 演示原子性day02.threadsafe.ForeverLoop 演示可见性 注意本例经实践检验是编译器优化导致的可见性问题 day02.threadsafe.Reordering 演示有序性 需要打成 jar 包后测试 请同时参考视频讲解
6. 悲观锁 vs 乐观锁
要求
掌握悲观锁和乐观锁的区别
对比悲观锁与乐观锁
悲观锁的代表是 synchronized 和 Lock 锁 其核心思想是【线程只有占有了锁才能去操作共享变量每次只有一个线程占锁成功获取锁失败的线程都得停下来等待】线程从运行到阻塞、再从阻塞到唤醒涉及线程上下文切换如果频繁发生影响性能实际上线程在获取 synchronized 和 Lock 锁时如果锁已被占用都会做几次重试操作减少阻塞的机会 乐观锁的代表是 AtomicInteger使用 cas 来保证原子性 其核心思想是【无需加锁每次只有一个线程能成功修改共享变量其它失败的线程不需要停止不断重试直至成功】由于线程一直运行不需要阻塞因此不涉及线程上下文切换它需要多核 cpu 支持且线程数不应超过 cpu 核数
代码说明
day02.SyncVsCas 演示了分别使用乐观锁和悲观锁解决原子赋值请同时参考视频讲解
7. Hashtable vs ConcurrentHashMap
要求
掌握 Hashtable 与 ConcurrentHashMap 的区别掌握 ConcurrentHashMap 在不同版本的实现区别
更形象的演示见资料中的 hash-demo.jar运行需要 jdk14 以上环境进入 jar 包目录执行下面命令
java -jar --add-exports java.base/jdk.internal.miscALL-UNNAMED hash-demo.jarHashtable 对比 ConcurrentHashMap
Hashtable 与 ConcurrentHashMap 都是线程安全的 Map 集合Hashtable 并发度低整个 Hashtable 对应一把锁同一时刻只能有一个线程操作它ConcurrentHashMap 并发度高整个 ConcurrentHashMap 对应多把锁只要线程访问的是不同锁那么不会冲突
ConcurrentHashMap 1.7
数据结构Segment(大数组) HashEntry(小数组) 链表每个 Segment 对应一把锁如果多个线程访问不同的 Segment则不会冲突并发度Segment 数组大小即并发度决定了同一时刻最多能有多少个线程并发访问。Segment 数组不能扩容意味着并发度在 ConcurrentHashMap 创建时就固定了索引计算 假设大数组长度是 key 在大数组内的索引是 key 的二次 hash 值的高 m 位假设小数组长度是 key 在小数组内的索引是 key 的二次 hash 值的低 n 位 扩容每个小数组的扩容相对独立小数组在超过扩容因子时会触发扩容每次扩容翻倍Segment[0] 原型首次创建其它小数组时会以此原型为依据数组长度扩容因子都会以原型为准
ConcurrentHashMap 1.8
数据结构Node 数组 链表或红黑树数组的每个头节点作为锁如果多个线程访问的头节点不同则不会冲突。首次生成头节点时如果发生竞争利用 cas 而非 syncronized进一步提升性能并发度Node 数组有多大并发度就有多大与 1.7 不同Node 数组可以扩容扩容条件Node 数组满 3/4 时就会扩容扩容单位以链表为单位从后向前迁移链表迁移完成的将旧数组头节点替换为 ForwardingNode扩容时并发 get 根据是否为 ForwardingNode 来决定是在新数组查找还是在旧数组查找不会阻塞如果链表长度超过 1则需要对节点进行复制创建新节点怕的是节点迁移后 next 指针改变如果链表最后几个元素扩容后索引不变则节点无需复制 扩容时并发 put 如果 put 的线程与扩容线程操作的链表是同一个put 线程会阻塞如果 put 的线程操作的链表还未迁移完成即头节点不是 ForwardingNode则可以并发执行如果 put 的线程操作的链表已经迁移完成即头结点是 ForwardingNode则可以协助扩容 与 1.7 相比是懒惰初始化capacity 代表预估的元素个数capacity / factory 来计算出初始数组大小需要贴近 loadFactor 只在计算初始数组大小时被使用之后扩容固定为 3/4超过树化阈值时的扩容问题如果容量已经是 64直接树化否则在原来容量基础上做 3 轮扩容
8. ThreadLocal
要求
掌握 ThreadLocal 的作用与原理掌握 ThreadLocal 的内存释放时机
作用
ThreadLocal 可以实现【资源对象】的线程隔离让每个线程各用各的【资源对象】避免争用引发的线程安全问题ThreadLocal 同时实现了线程内的资源共享
原理
每个线程内有一个 ThreadLocalMap 类型的成员变量用来存储资源对象
调用 set 方法就是以 ThreadLocal 自己作为 key资源对象作为 value放入当前线程的 ThreadLocalMap 集合中调用 get 方法就是以 ThreadLocal 自己作为 key到当前线程中查找关联的资源值调用 remove 方法就是以 ThreadLocal 自己作为 key移除当前线程关联的资源值
ThreadLocalMap 的一些特点
key 的 hash 值统一分配初始容量 16扩容因子 2/3扩容容量翻倍key 索引冲突后用开放寻址法解决冲突
弱引用 key
ThreadLocalMap 中的 key 被设计为弱引用原因如下
Thread 可能需要长时间运行如线程池中的线程如果 key 不再使用需要在内存不足GC时释放其占用的内存
内存释放时机
被动 GC 释放 key 仅是让 key 的内存释放关联 value 的内存并不会释放 懒惰被动释放 value get key 时发现是 null key则释放其 value 内存set key 时会使用启发式扫描清除临近的 null key 的 value 内存启发次数与元素个数是否发现 null key 有关 主动 remove 释放 keyvalue 会同时释放 keyvalue 的内存也会清除临近的 null key 的 value 内存推荐使用它因为一般使用 ThreadLocal 时都把它作为静态变量即强引用因此无法被动依靠 GC 回收
