每周基本上最耗时的还是在算法上,这周因为是hashtable本身比较熟悉,所以整体花时间比较少。
除了散列表,还研究了两个一直不清楚基础概念,Java的垃圾回收机制、双亲委派机制。
算法:
- hashtable
基础:
- 垃圾回收机制
- 双亲委派机制
- 构造函数、静态代码块、构造代码块
1. although
1.1. 散列表(hashtable,Java:HashMap)
对于Java的HashMap我曾经写过一篇文章,专门讲解其源码部分,→ Java8-HashMap原理分析 。
简单概况:散列表随机索引快,本质上是数组的特性,底层将数组作为容器。每个存入的对象都有一个hash值,以此为对应的数组位置存放。但是hash值可能相同,于是就需要解决冲突,称之为hash冲突。
散列表关键点:
- 重要参数
装载因子=已有元素数量/散列表长度
- 初始容量
- hash算法
- 要尽可能的均匀分布在数组中
- Java的解决方案:
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
,高位与低位充分混合。
- key冲突解决方式
- 链表(Java HashMap使用)
- 开放寻址法
- 正常开发寻址
- 当遇到冲突键时,向下寻找,直到最终找到空位(到底后从开头开始)
- 二次探测
- 与普通探测差不多,步数探测为原来的二次方
- 双重散列
- 多次hash,直到不重合
- 正常开发寻址
1.2. 存在重复元素
/**
* 217. 存在重复元素
* <p>
* 给定一个整数数组,判断是否存在重复元素。
* <p>
* 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。
* <p>
* 示例 1:
* <p>
* 输入: [1,2,3,1]
* 输出: true
* 示例 2:
* <p>
* 输入: [1,2,3,4]
* 输出: false
* 示例 3:
* <p>
* 输入: [1,1,1,3,3,4,3,2,4,2]
* 输出: true
* <p>
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/contains-duplicate
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class Week12EContainsDuplicate217 {
public boolean containsDuplicate(int[] nums) {
Set<Integer> map = new HashSet<>();
for (int num : nums) {
if (map.contains(num))return true;
map.add(num);
}
return false;
}
}
1.3. 最长和谐子序列
/**
* 594. 最长和谐子序列
* 和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
* <p>
* 现在,给定一个整数数组,你需要在所有可能的子序列中找到最长的和谐子序列的长度。
* <p>
* 示例 1:
* <p>
* 输入: [1,3,2,2,5,2,3,7]
* 输出: 5
* 原因: 最长的和谐数组是:[3,2,2,2,3].
* 说明: 输入的数组长度最大不超过20,000.
* <p>
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/longest-harmonious-subsequence
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
package com.myserious.code.cdz.week20;
import java.util.*;
public class Week12EFindLHS594 {
/**
* 其实并不需要 重新排序nums数组
* <p>
* 直接将nums[i]+1 或者 -1 就满足题意
*
* @param nums
* @return
*/
public int findLHS(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
Arrays.sort(nums);
int max = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] - nums[i] == 1) {
max = Math.max(map.get(nums[i + 1]) + map.get(nums[i]), max);
}
}
return max;
}
/**
* 其实并不需要 重新排序nums数组
* <p>
* 直接将nums[i]+1 或者 -1 就满足题意
*
* @param nums
* @return
*/
public int findLHS1(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int max = 0;
Set<Integer> keySet = map.keySet();
for (Integer k : keySet) {
if (map.containsKey(k + 1)) {
max = Math.max(max, map.get(k + 1) + map.get(k));
}
}
return max;
}
/**
* 不需要遍历两遍 只需要一遍即可
*
* @param nums
* @return
*/
public int findLHS2(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int max = 0;
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (map.containsKey(num + 1)) {
max = Math.max(max, map.get(num) + map.get(num + 1));
}
if (map.containsKey(num - 1)) {
max = Math.max(max, map.get(num) + map.get(num - 1));
}
}
return max;
}
public static void main(String[] args) {
Week12EFindLHS594 findLHS = new Week12EFindLHS594();
int[] ints = {1, 3, 2, 2, 5, 2, 3, 7};
System.out.println(findLHS.findLHS2(ints));
}
}
1.4. 子域名访问计数
/**
* 811. 子域名访问计数
* 一个网站域名,如"discuss.leetcode.com",包含了多个子域名。作为顶级域名,常用的有"com",下一级则有"leetcode.com",最低的一级为"discuss.leetcode.com"。当我们访问域名"discuss.leetcode.com"时,也同时访问了其父域名"leetcode.com"以及顶级域名 "com"。
* <p>
* 给定一个带访问次数和域名的组合,要求分别计算每个域名被访问的次数。其格式为访问次数+空格+地址,例如:"9001 discuss.leetcode.com"。
* <p>
* 接下来会给出一组访问次数和域名组合的列表cpdomains 。要求解析出所有域名的访问次数,输出格式和输入格式相同,不限定先后顺序。
* <p>
* 示例 1:
* 输入:
* ["9001 discuss.leetcode.com"]
* 输出:
* ["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
* 说明:
* 例子中仅包含一个网站域名:"discuss.leetcode.com"。按照前文假设,子域名"leetcode.com"和"com"都会被访问,所以它们都被访问了9001次。
* 示例 2
* 输入:
* ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
* 输出:
* ["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
* 说明:
* 按照假设,会访问"google.mail.com" 900次,"yahoo.com" 50次,"intel.mail.com" 1次,"wiki.org" 5次。
* 而对于父域名,会访问"mail.com" 900+1 = 901次,"com" 900 + 50 + 1 = 951次,和 "org" 5 次。
* 注意事项:
* <p>
* cpdomains 的长度小于 100。
* 每个域名的长度小于100。
* 每个域名地址包含一个或两个"."符号。
* 输入中任意一个域名的访问次数都小于10000。
* <p>
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/subdomain-visit-count
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
package com.myserious.code.cdz.week20;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class Week12ESubdomainVisits811 {
public List<String> subdomainVisits(String[] cpdomains) {
HashMap<String, Integer> map = new HashMap<>();
for (String cpdomain : cpdomains) {
String[] kv = cpdomain.split(" ");
Integer count = Integer.parseInt(kv[0]);
String main = kv[1];
map.put(main,map.getOrDefault(main,0)+count);
String[] dnses = main.split("\\.");
if (dnses.length==3){
map.put(dnses[1]+"."+dnses[2],map.getOrDefault(dnses[1]+"."+dnses[2],0)+count);
map.put(dnses[2],map.getOrDefault(dnses[2],0)+count);
}else if (dnses.length==2){
map.put(dnses[1],map.getOrDefault(dnses[1],0)+count);
}
}
ArrayList<String> list = new ArrayList<>();
map.forEach((k,v)->list.add(v+" "+k));
return list;
}
public static void main(String[] args) {
Week12ESubdomainVisits811 visits = new Week12ESubdomainVisits811();
List<String> strings = visits.subdomainVisits(new String[]{"9001 discuss.leetcode.com"});
System.out.println(strings.toString());
}
}
1.5. 两数之和
/**
* 1. 两数之和
* 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
* <p>
* 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
* <p>
* 示例:
* <p>
* 给定 nums = [2, 7, 11, 15], target = 9
* <p>
* 因为 nums[0] + nums[1] = 2 + 7 = 9
* 所以返回 [0, 1]
* <p>
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/two-sum
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
package com.myserious.code.cdz.week20;
import java.util.HashMap;
import java.util.Map;
public class Week12ETwoSum1 {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (map.containsKey(diff)){
return new int[]{map.get(diff),i};
}
map.put(nums[i],i);
}
return new int[]{-1,-1};
}
}
1.6. 最长连续序列
/**
* 128. 最长连续序列
* 给定一个未排序的整数数组,找出最长连续序列的长度。
* <p>
* 要求算法的时间复杂度为 O(n)。
* <p>
* 示例:
* <p>
* 输入: [100, 4, 200, 1, 3, 2]
* 输出: 4
* 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
* <p>
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/longest-consecutive-sequence
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
package com.myserious.code.cdz.week20;
import java.util.HashSet;
public class Week12HLongestConsecutive128 {
public int longestConsecutive(int[] nums) {
HashSet<Integer> hashSet = new HashSet<>();
for (int num : nums) {
hashSet.add(num);
}
int maxLens = 0;
for (int num : nums) {
if (!hashSet.contains(num-1)){
//保证从第一个开始
int currNum = num;
int currIndex = 1;
while (hashSet.contains(currNum+1)){
currNum++;
currIndex++;
}
maxLens = Math.max(maxLens, currIndex);
}
}
return maxLens;
}
}
2. review
2.1. 四年Google程序员为什么要离职
Worst of all, I wasn’t proud of my work. Instead of asking myself, “How can I solve this challenging problem?” I was asking, “How can I make this problem look challenging for promotion?” I hated that.
看完之后,让我感受到大公司的官僚体制下的那种无奈。
每一个做技术的人,开始都有一颗抱着极致的追求,想起来我不也是,在开始工作的时候,会去默默的优化,一些写的不规范的地方,或者是出错的地方。
确实,公司到了一定的体量,就必须要上管理,这是必然的。
我在想,其实人们都喜欢自由的环境为梦想而斗。那些创始人们,先成功了(在公司还小时)。当体量大后,知道必须实行管理方式,也许会官僚,但是其实自己并不需要经受这些。
所以他们其实是最幸福的吧。
3. tip
3.1. 算法
3.1.1. GC原理:G1与CMS分别是什么?
垃圾回收:主要针对的是Java对象,Java对象在堆中。
3.2. 多线程
3.2.1. 线程池设计,一般采用的是 生产者-消费者模式
3.2.2. 线程池执行任务流程
注意点:
- 如果缓存队列为无限制队列,那么是否达到最大线程数量限制这一项就没有用了
- 在使用时,最好不要使用无限制队列
3.2.3. 并发编程技巧
并发编程中,看到回调函数时,一定要问一问自己执行回调函数的线程时谁。
适用多线程协同工具类时,注意屏障过后同时进入临界区,重点考虑这个地方的并发问题。
3.3. Java基础
3.3.1. HashMap并发状态下会导致CPU飙升的原因
Java7中HashMap,在put时会有扩容操作,主要是扩容时链表的并发操作会导致,链表成环,从而导致CPU飙升。
3.4. MySQL优化
3.4.1. 覆盖索引概念
覆盖索引: 普通索引查询(范围)时,需要一个一个的回表查询,效率很低。 但是如果在查询结果中,只需要字段id或者在普通索引上的字段,就不需要回表。
3.4.2. 最左前缀原则
B+ 树这种索引结构,可以利用索引的“最左前缀”,来定位记录。
也就是说如果有联合索引时,最左边的索引其实已经自带。 如: 联合索引(a,b)a与b两个字段的联合索引。 (a)a字段索引自动就已经存在,不需要在额外添加。
4. share
4.1. Java基础
4.1.1. Java类加载过程
4.1.1.1. 类加载器
代码:
/**
* 测试classloader类
*/
public class ClassLoaderDemo {
public static void main(String[] args) {
ClassLoader classLoader = Object.class.getClassLoader();
System.out.println("Object的类加载器"+classLoader);//bootstrap加载器,C语言编写 所以Java中展示为null
System.out.println("-----------------------");
ClassLoader classLoader1 = DNSNameService.class.getClassLoader();
System.out.println("DNSNameService的类加载器"+classLoader1);//拓展加载器
System.out.println("-----------------------");
ClassLoader classLoader2 = ClassLoaderDemo.class.getClassLoader();
System.out.println("DemoClassLoader的类加载器"+classLoader2);//应用加载器 程序中类默认都是应用加载器加载
System.out.println("-----------------------");
while (classLoader2!=null){
//查看父加载器,其层次关系
System.out.println(classLoader2);
classLoader2 = classLoader2.getParent();
}
}
}
打印结果:
Object的类加载器null //为null的原因是,根加载器为C写的
-----------------------
DNSNameService的类加载器sun.misc.Launcher$ExtClassLoader@5e2de80c
-----------------------
DemoClassLoader的类加载器sun.misc.Launcher$AppClassLoader@18b4aac2
-----------------------
sun.misc.Launcher$AppClassLoader@18b4aac2
sun.misc.Launcher$ExtClassLoader@5e2de80c
4.1.1.2. 自定义类加载器(深入测试)
当然,JDK提供了一个我们可以使用的类加载器URLClassLoader
,这里我们自定义实现的功能与它差不多。
但是根据双亲委派机制,我们知道ClassLoader::loadClass
中实现了双亲委派机制。
如果我们想要一份字节码在可以多次被加载,并且是不同的对象。在热部署中常使用。
Demo文件:
package com.demo;
public class Demo{
public Demo(){
System.out.println("初始化Demo");
}
}
通过命令编译为.class文件:javac -d . Demo.java
自定义类加载器:
package com.myserious.code.cdz.thread.classloader;
import java.io.*;
/**
* 自定义文件加载器
*
* 只需要重写 findClass 方法即可
*
* ClassLoader::loadClass的方法,中实现了双亲委派模式,
*
* 如果我们想要同一份字节码,加载两次得到不同的对象,可以直接使用重写的findClass方法。
*
*
*/
public class MyFileClassLoader extends ClassLoader{
private String dir;
public MyFileClassLoader(String dir) {
this.dir = dir;
}
public MyFileClassLoader(String dir, ClassLoader parent) {
super(parent);
this.dir = dir;
}
@Override
protected Class<?> findClass(String name) throws ClassNotFoundException {
try {
String file = dir+name.replace(".",File.separator)+".class";
//创建输入流
InputStream in = new FileInputStream(new File(file));
//构建输出流
ByteArrayOutputStream baos = new ByteArrayOutputStream();
int len = -1;
byte[] bytes = new byte[1024];
while ((len=in.read(bytes))!=-1){
baos.write(bytes,0,len);
}
byte[] data = baos.toByteArray();
in.close();
baos.close();
return defineClass(name,data,0,data.length);
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
- 测试初始化对象
public static void main(String[] args) throws Exception {
MyFileClassLoader myFileClassLoader = new MyFileClassLoader("/Users/cdz/Desktop/“);
Class<?> aClass = myFileClassLoader.loadClass("com.demo.Demo”); loadClass 方法使用了双亲委派机制
Object o = aClass.newInstance();
}
打印:
初始化Demo
- 测试双亲委派机制:
public static void main(String[] args) throws Exception {
MyFileClassLoader myFileClassLoader = new MyFileClassLoader("/Users/cdz/Desktop/");
//第二个classloader 指定父加载器
// 当父类加载器发现加载过,直接会返回加载过的class对象
MyFileClassLoader myFileClassLoader1 = new MyFileClassLoader("/Users/cdz/Desktop/", myFileClassLoader);
Class<?> aClass = myFileClassLoader.loadClass("com.demo.Demo");
Class<?> bClass = myFileClassLoader1.loadClass("com.demo.Demo");
System.out.println("aClass="+aClass.hashCode());
System.out.println("bClass="+bClass.hashCode());
}
打印:
aClass=1360875712
bClass=1360875712
- 绕过双亲委派机制:使用自定义的
findClass
public static void main(String[] args) throws Exception {
MyFileClassLoader myFileClassLoader = new MyFileClassLoader("/Users/cdz/Desktop/");
MyFileClassLoader myFileClassLoader1 = new MyFileClassLoader("/Users/cdz/Desktop/", myFileClassLoader);
Class<?> aClass = myFileClassLoader.findClass("com.demo.Demo");
Class<?> bClass = myFileClassLoader1.findClass("com.demo.Demo");
System.out.println("aClass="+aClass.hashCode());
System.out.println("bClass="+bClass.hashCode());
}
打印:
aClass=1580066828
bClass=491044090
4.1.2. Java静态代码块、构造代码块、构造函数
static {}//静态代码块,可以有多个,只初始化一次
{} //构造代码块, 构造对象时使用,在**构造函数之前**执行
public Student() {//构造代码块
System.out.println("Student");
}
有继承关系的代码执行顺序:
- 从父类开始顺序执行静态代码块(只执行一次)
- 父类静态代码块
- 子类静态代码块
- 父类构造代码块
- 父类构造函数
- 子类构造代码块
- 子类构造函数
class Person {
{//构造代码块
System.out.println("这是person的{}代码块");
}
static {//静态代码块
System.out.println("这是person的static代码块");
}
public Person() {//构造函数
System.out.println("person");
}
}
class Student extends Person{
{
System.out.println("这是Student的{}代码块");
}
static {
System.out.println("这是Student的static代码块");
}
public Student() {
System.out.println("Student");
}
}
这是person的static代码块2
这是person的static代码块
这是Student的static代码块
这是person的{}代码块
person
这是Student的{}代码块
Student
4.2. 多线程
4.2.1. synchronize关键字底层原理
通过反编译后,可以看到,synchronize关键字是由,monitorenter与monitorexit两个指令完成。
是当我们使用synchronize时,编译器自动添加的两个命令。
monitorenter与monitorexit可以一对多,原因是进入monitorenter只有一个入口,但是退出程序会有多个(正常结束、异常抛出)
synchronize可重入性:
当一个线程执行获取到monitor锁之后,如果没有释放,这期间可以再次获取这把锁,不需要重新去获取锁。
- 递归方法,可以重入
- 同一个类的方法,可重入
- 不同类方法,可重入。
- 只要是被同一个锁修饰的,并且调用线程持有该锁就可以重入
4.3. 正确的幻想
这周在得到《洞察力》课上看到一个问题。
让我们开个脑洞,如果谷歌邮件邀请你去参观,可以去谷歌的任何部门,参加任何会议,但是只有一个月的时间,你会去哪?
什么叫做贫穷限制了想象力?
连问题都想不到,怎么谈回答?
让我突然发散的想,很多时候我可以正确的幻想很多事情。
我现在时公司的CEO我会如果领导团队?
BAT我已经在里面了,会担任什么职务?
说实话我觉得这些幻想并不是那种让我能觉得脑洞大开的,还是《洞察力》的那个幻想,让我印象深刻。
所以我觉得,得有个专门可以幻想的时间,或者空间。
设身处地的去想,遇到在这个位置上,我会面临什么样的挑战。我该如何办。
4.4. 屏幕时间与非屏幕时间
最近这段时间,因为记录时间的原因。
发现了一个很奇怪,也值得去关注的现象。
屏幕时间与非屏幕时间。
起因是,番茄时间上,每次25分钟的时间任务,5分钟的休息。
而就在五分钟休息时,我开始注意到了两者时间的差别。
比如,有时候我会趁着这五分钟的时间去运动,不看任何屏幕。有时候可能会整理一下刚刚学习到的内容,有时候会随便翻一下手机。
这其中,只有一个,五分钟的运动,会让人感到时间过的真的很慢。
因为在运动的时候,看不到屏幕,只能通过听提示声音的方式知道,是否休息时间到了。很多次我都怀疑自己是否错过了提示声音。
时间管理工具Toggle,也是一样。
基本上每天下午的时间都是瞎过的,没有什么效率。主要记录时间给了一种紧张感。下午时间记录上,也呈现出这样的规律,屏幕时间真的会让人感到过的非常快。快到有种不真实的感觉。
但是会想起来却发现并没有做些什么有意义的事情。
其实人的大脑,一天按24小时,8小时的睡眠,这个是潜意识的活动,基本上不能自主。
睡觉时间占到整个人生1/3时间。
剩下的2/3时间,真正可以集中注意力的时间,白天16小时里面。正常来说可能平均没有5小时。
也就是说,其实很多时间都在做白日梦。
昨天听书《脑与意识》中讲到了,这点,但是我忘了人一天多少时间是在意识游离的状态。但是可以知道的是,不可能完全集中注意力。
那么如果每天人大概有固定的时间意识游离的话,那么这期间是耍手机,逛网站,就会让自己觉得时间过的飞快,并且并没有好好的利用上这个意识游离的时间去关注自身,白日梦也要做的积极一些。
如果这些时间用在另外的一些非屏幕时间上呢?发会儿呆/想一下积极一面。也许能让人过的更充实,至少每天都会觉得一天能够想起来做了什么。
逃离屏幕。
在刚刚我发现一个与时间有关很神奇的事情。
iOS系统的屏幕时间记录做的越来越好。基本我每周都会去关注一下自己在屏幕上的使用时间。
特别是最近自己手机开始限时之后,使用时间就更让我关注了。
限时的效果:非常明显的是,缩短了社交时间。基本上将微信使用时间,每周的使用时间在4小时左右,而没有显示的时候,这个时间往往是8小时,或者10小时左右。
还有就是这最近三周的阅读时间。
仔细回想没有限时之前,其实一周的时间基本都花费在这两大头,阅读与微信。
而刚刚查看,最近三周的阅读时间,竟然惊人的一致,上下相差不到30分钟。
平均在11小时30分钟。
当然这包括了所有的阅读APP,抛去微博与今日头条的两个小时。
平均而言,一周的阅读时间在9小时。
这个时间相差无几,让我有点好奇。
其实也说得通,一周有空看手机的时间也就那么多。多看了这个就会少看那个。阅读类APP时间没有变化,但是内容我仔细看了一下还是有所变化的。
越往前,微博与头条的时间花费的越多。也理所当然,因为要关注疫情的发展。
剩下的就是阅读大头,得到/微信读书。这两个加起来的时间基本上是固定的,也就是说,如果我看得到多了,自然就会读书少一些。如果读书多,那么得到自然就会少一些,因为正常情况下,总时间很难去变化。