Nicksxs's Blog

这篇博客的灵感又是来自于我从绍兴来杭州的路上，在我们进站以后上电梯快到的时候，突然前面不动了，右边我能看到的是有个人的行李箱一时拎不起来，另一边后面看到其实是个小孩子在那哭闹，一位妈妈就在那停着安抚或者可能有点手足无措，其实这一点应该是在几年前慢慢意识到是个非常危险的场景，特别是像绍兴北站这样上去站台是非常长的电梯，因为最近扩建改造，车次减少了很多，所以每一班都有很多人，检票上站台的电梯都是满员运转，试想这种情况，如果刚才那位妈妈再多停留一点时间，很可能就会出现后面的人上不来被挤下去，再严重点就是踩踏事件，但是这类情况很少人真的意识到，非常明显的例子就是很多人拿着比较大比较重的行李箱，不走垂梯，并且在快到的时候没有提前准备好，有可能在玩手机啥的，如果提不动，后面又是挤满人了，就很可能出现前面说的这种情况，并且其实这种是非紧急情况，大多数人都没有心理准备，一旦发生后果可能就会很严重，例如火灾地震疏散大部分人或者说负责引导的都是指示要有序撤离，防止踩踏，但是普通坐个扶梯，一般都不会有这个意识，但是如果这个时间比较长，出现了人员站不住往后倒了，真的会很严重。所以如果自己是带娃的或者带了很重的行李箱的，请提前做好准备，看到前面有人带的，最好也保持一定距离。
还有比如日常走路，旁边有车子停着的情况，比较基本的看车灯有没有亮着，亮着的是否是倒车灯，这种应该特别注意远离，至少保持距离，不能挨着走，很多人特别是一些老年人，在一些人比较多的路上，往往完全无视旁边这些车的状态，我走我的路，谁敢阻拦我，管他车在那动不动，其实真的非常危险，车子本身有视线死角，再加上司机的驾驶习惯和状态，想去送死跟碰瓷的除外，还有就是有一些车会比较特殊，车子发动着，但是没灯，可能是车子灯坏了或者司机通过什么方式关了灯，这种比较难避开，不过如果车子打着了，一般会有比较大的热量散发，车子刚灭了也会有，反正能远离点尽量远离，从轿车的车前面走过挨着走要比从屁股后面挨着走稍微安全一些，但也最好不要挨着车走。
最后一点其实是我觉得是我自己比较怕死，一般对来向的车或者从侧面出来的车会做更长的预判距离，特别是电瓶车，一般是不让人的，像送外卖的小哥，的确他们不太容易，但是真的很危险啊，基本就生死看刹车，能刹住就赚了，刹不住就看身子骨扛不扛撞了，只是这里要多说点又要谈到资本的趋利性了，总是想法设法的压榨以获取更多的利益，也不扯远了，能远离就远离吧。

说来也惭愧，这个 ThreadLocal 其实一直都是一知半解，而且看了一下之后还发现记错了，所以还是记录下
原先记忆里的都是反过来，一个 ThreadLocal 是里面按照 thread 作为 key，存储线程内容的，真的是半解都米有，完全是错的，这样就得用 concurrentHashMap 这种去存储并且要锁定线程了，然后内容也只能存一个了，想想简直智障

究竟是啥结构

比如我们在代码中 new 一个 ThreadLocal，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static void main(String[] args) {
        ThreadLocal<Man> tl = new ThreadLocal<>();

        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println(tl.get());
        }).start();
        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            tl.set(new Man());
        }).start();
    }

    static class Man {
        String name = "nick";
    }

这里构造了两个线程，一个先往里设值，一个后从里取，运行看下结果，

知道这个用法的话肯定知道是取不到值的，只是具体的原理原来搞错了，我们来看下设值 set 方法

1
2
3
4
5
6
7
8

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

写博客这会我才明白我原来咋会错得这么离谱，看到第一行代码 t 就是当前线程，然后第二行就是用这个线程去getMap，然后我是把这个当成从 map 里取值了，其实这里是

1
2
3

ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

获取 t 的 threadLocals 成员变量，那这个 threadLocals 又是啥呢

它其实是线程 Thread 中的一个类型是java.lang.ThreadLocal.ThreadLocalMap的成员变量
这是 ThreadLocal 的一个静态成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

static class ThreadLocalMap {

        /**
         * The entries in this hash map extend WeakReference, using
         * its main ref field as the key (which is always a
         * ThreadLocal object).  Note that null keys (i.e. entry.get()
         * == null) mean that the key is no longer referenced, so the
         * entry can be expunged from table.  Such entries are referred to
         * as "stale entries" in the code that follows.
         */
        static class Entry extends WeakReference<ThreadLocal<?>> {
            /** The value associated with this ThreadLocal. */
            Object value;

            Entry(ThreadLocal<?> k, Object v) {
                super(k);
                value = v;
            }
        }
    }

全部代码有点长，只截取了一小部分，然后我们再回头来分析前面说的 set 过程，再 copy 下代码

1
2
3
4
5
6
7
8

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

获取到 map 以后呢，如果 map 不为空，就往 map 里 set，这里注意 key 是啥，其实是当前这个 ThreadLocal，这里就比较明白了究竟是啥结构，每个线程都会维护自身的 ThreadLocalMap，它是线程的一个成员变量，当创建 ThreadLocal 的时候，进行设值的时候其实是往这个 map 里以 ThreadLocal 作为 key，往里设 value。

内存泄漏是什么鬼

这里又要看下前面的 ThreadLocalMap 结构了，类似 HashMap，它有个 Entry 结构，在设置的时候会先包装成一个 Entry

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

private void set(ThreadLocal<?> key, Object value) {

        // We don't use a fast path as with get() because it is at
        // least as common to use set() to create new entries as
        // it is to replace existing ones, in which case, a fast
        // path would fail more often than not.

        Entry[] tab = table;
        int len = tab.length;
        int i = key.threadLocalHashCode & (len-1);

        for (Entry e = tab[i];
             e != null;
             e = tab[i = nextIndex(i, len)]) {
            ThreadLocal<?> k = e.get();

            if (k == key) {
                e.value = value;
                return;
            }

            if (k == null) {
                replaceStaleEntry(key, value, i);
                return;
            }
        }

        tab[i] = new Entry(key, value);
        int sz = ++size;
        if (!cleanSomeSlots(i, sz) && sz >= threshold)
            rehash();
}

这里其实比较重要的就是前面的 Entry 的构造方法，Entry 是个 WeakReference 的子类，然后在构造方法里可以看到 key 会被包装成一个弱引用，这里为什么使用弱引用，其实是方便这个 key 被回收，如果前面的 ThreadLocal tl实例被设置成 null 了，如果这里是直接的强引用的话，就只能等到线程整个回收了，但是其实是弱引用也会有问题，主要是因为这个 value，如果在 ThreadLocal tl 被设置成 null 了，那么其实这个 value 就会没法被访问到，所以最好的操作还是在使用完了就 remove 掉

题目介绍

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果当前节点就是 p 或者是 q 的时候，就直接返回了
        // 当没找到，即 root == null 的时候也会返回 null，这是个重要的点
        if (root == null || root == p || root == q) return root;
        // 在左子树中找 p 和 q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 在右子树中找 p 和 q
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 当左边是 null 就直接返回右子树，但是这里不表示右边不是 null，所以这个顺序是不影响的
        // 考虑一种情况，如果一个节点的左右子树都是 null，那么其实对于这个节点来说首先两个子树分别调用
        // lowestCommonAncestor会在开头就返回 null，那么就是上面 left 跟 right 都是 null，然后走下面的判断的时候
        // 其实第一个 if 就返回了 null，如此递归返回就能达到当子树中没有找到 p 或者 q 的时候只返回 null
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
//        if (right == null) {
//            return left;
//        } else if (left == null) {
//            return right;
//        } else {
//            return root;
//        }
//        return left == null ? right : right == null ? left : root;
    }

除了引用，Rust 还有另外一种不持有所有权的数据类型：切片(slice)。切片允许我们引用集合中某一段连续的元素序列，而不是整个集合。
例如代码

1
2
3
4
5
6
7
8
9

fn main() {
    let mut s = String::from("hello world");

    let word = first_word(&s);

    s.clear();

    // 这时候虽然 word 还是 5，但是 s 已经被清除了，所以就没存在的意义
}

这里其实我们就需要关注 s 的存在性，代码的逻辑合理性就需要额外去维护，此时我们就可以用切片

1
2
3
4

let s = String::from("hello world")

let hello = &s[0..5];
let world = &s[6..11];

其实跟 Python 的list 之类的语法有点类似，当然里面还有些语法糖，比如可以直接用省略后面的数字表示直接引用到结尾

1

let hello = &s[0..];

甚至再进一步

1

let hello = &s[..];

使用了切片之后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

fn first_word(s: &String) -> &str {
    let bytes = s.as_bytes();

    for (i, &item) in bytes.iter().enumerate() {
        if item == b' ' {
            return &s[0..i];
        }
    }

    &s[..]
}
fn main() {
    let mut s = String::from("hello world");

    let word = first_word(&s);

    s.clear(); // error!

    println!("the first word is: {}", word);
}

那再执行 main 函数的时候就会抛错，因为 word 还是个切片，需要保证 s 的有效性，并且其实我们可以将函数申明成

1

fn first_word(s: &str) -> &str {

这样就既能处理&String 的情况，就是当成完整字符串的切片，也能处理普通的切片。
其他类型的切片

1
2

let a = [1, 2, 3, 4, 5];
let slice = &a[1..3];

简单记录下，具体可以去看看这本书

前面这个五一回去之前，LD 姐姐跟我说电脑很卡了，想让我重装系统，问了下 LD 可能是那个 09 年买的笔记本，想想有点害怕[捂脸]，前年有一次好像让我帮忙装了她同事的一个三星的笔记本，本着一些系统洁癖，所以就从开始找纯净版的 win7 家庭版，因为之前那些本基本都自带 win7 的家庭版，而且把激活码就贴在机器下面，然后从三星官网去找官方驱动，还好这个机型的驱动还在，先做了系统镜像，其实感觉这种情况需要两个 U 盘，一个 U 盘装系统作为安装启动盘，一个放驱动，毕竟不是专业装系统的，然后因为官方驱动需要一个个下载一个个安装，然后驱动文件下载的地方还没标明是 32 位还是 64 位的，结果还被 LD 姐姐催着，一直问好没好，略尴尬，索性还是找个一键安装的

这次甚至更夸张，上次还让带回去，我准备好了系统镜像啥的，第二天装，这次直接带了两个老旧笔记本过来说让当天就装好，感觉有点像被当修电脑的使，又说这些电脑其实都不用了的，都是为了她们当医生的要每年看会课，然后只能用电脑浏览器看，结果都在用 360 浏览器，真的是万恶的 360，其实以前对 360 没啥坏印象，毕竟以前也经常用，只是对于这些老电脑，360 全家桶真的就是装了就废了，2G 的内存，开机就开着 360 安全卫士，360 杀毒，有一个还装了腾讯电脑管家，然后腾讯视频跟爱奇艺也开机启动了，然后还打开 360 浏览器看课，就算再好的系统也吃不消这么用，重装了系统，还是这么装这些东西，也是分分钟变卡，可惜他们都没啥这类概念。

对于他们要看的课，更搞笑的是，明明在页面上注明了说要使用 IE 浏览器，结果他们都在用 360 浏览器看，但是这个也不能完全怪他们，因为实在是现在的 IE 啥的也有开始不兼容 flash 的配置，需要开启兼容配置，但是只要开启了之后就可以直接用 IE 看，比 360 靠谱很多， 资源占用也比较少，360 估计是基于 chromium 加了很多内置的插件，本身 chromium 也是内存大户，但是说这些其实他们也不懂，总觉得找我免费装下系统能撑一段时间，反正对我来说也应该很简单（他们觉得），实际上开始工作以后，我自己想装个双系统都是上淘宝买别人的服务装的，台式机更是几年没动过系统了，因为要重装一大堆软件，数据备份啥的，还有驱动什么的，分区格式，那些驱动精灵啥的也都是越来越坑，一装就给你带一堆垃圾软件。

感悟是，总觉得学计算机的就应该会装系统，会修电脑，之前亲戚还拿着一个完全开不起来的笔记本让我来修，这真的是，我说可以找官方维修的，结果我说我搞不定，她直接觉得是修不好了，直接电脑都懒得拿回去了，后面又一次反复解释了才明白，另外就是 360 全家桶，别说老电脑了，新机器都不太吃得消。