头条后端面试记录

面试 , 评论
  • 前言
    • 1. 求二叉树的最远节点的距离
    • [2. Java 的装箱与拆箱](#2-java 的装箱与拆箱)
    • [3. CMS 垃圾收集器的收集过程中，什么时候会暂停用户线程？](#3-cms 垃圾收集器的收集过程中什么时候会暂停用户线程)
    • [4. ConcurrentHashMap 在读取的过程中为什么不需要加锁？](#4-concurrenthashmap 在读取的过程中为什么不需要加锁)
    • [5. Redis 的字典 rehash 和 JDK 中 hashmap 等 rehash 有什么不同？](#5-redis 的字典 rehash 和 jdk 中 hashmap 等 rehash 有什么不同)
  • 参考文章

前言

最近参加了一下头条后端工程师的面试，很惨，一面就挂掉了。

回来之后也对面试过程做了一些总结，就不夹带私货了，这篇文章主要对面试过程中的技术问题做一个复盘。

1. 求二叉树的最远节点的距离

这是一道 LeetCode 原题，原题链接

求二叉树的最远距离节点间的节点。
首先总结几个规律：

  1. 一棵树的直径要么完全在其左子树中，要么完全在其右子树中，要么路过根节点。
  2. 一棵树的直径 = 以该树中每一个节点为根节点，求 路过根节点的最大直径，所有节点的最大值就是这棵树的直径。
  3. 求经过根节点的直径，可以分解为：求左子树的最深叶子 + 右子树的最深叶子。

所以我们要做：

  1. 递归的求 每一个节点的 路过根节点的直径（求当前节点的左子树最深叶子和右子树的最深叶子）, 取其最大值。
  2. 求某一个节点的最深叶子，就等于 他的 左子树最深叶子 + 1 和 右子树最深叶子 + 1 的较大值。
  3. 在求最深叶子的时候，其实是求出了当前节点直径的（左边最深叶子 + 右边最深叶子 + 2), 为了避免重复计算，我们在递归求最深叶子的时候，把直径也记录下来。)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int diameterOfBinaryTree(TreeNode root) {
    AtomicReference<Integer> ret = new AtomicReference<>(0);
     find(root, ret);
    return ret.get();
}

private int find(TreeNode node, AtomicReference<Integer> result) {
    if (node == null) return 0;
    int left = 0, right = 0;
    if (node.left != null) left = find(node.left,result) + 1;
    if (node.right != null) right = find(node.right,result) + 1;
    int tmp = Math.max(result.get(), left + right);
    result.set(tmp);
    return Math.max(left, right);
}

代码很简单，就是递归的求节点的左子树最远叶子和右子树最远叶子。然后在 计算过程中，将 当前节点的直径 作为一个备选项存储，最后求最大直径即可。

2. Java 的装箱与拆箱

Java 在 1.5 添加了自动装箱和拆箱机制。总的来说基本就是基本类型和对应的包装类型之间的自动转换。

如下面的代码中：

1
2
3
4
5
6
public class BoxTest {
    public static void main(String [] args){
        Integer a = 10; // 装箱
        int b = a; // 拆箱
    }
}

我们将代码编译之后进行反编译，可以看到

2019-10-24-14-32-50

很明显在 代码中的 #2 ,#3 处进行了装箱和拆箱。

分别调用了 Integer 的 valueOf 方法和intValue 方法。

3. CMS 垃圾收集器的收集过程中，什么时候会暂停用户线程？

这里不对所有的垃圾收集器展开讲解，有兴趣的朋友们可以移步 JVM 的数据区域与垃圾收集.

众所周知，CMS 的垃圾收集过程如下：

2019-08-10-21-19-28

所以在初始标记和重新标记两个阶段还是需要暂停用户线程的。

4. ConcurrentHashMap 在读取的过程中为什么不需要加锁？

查看ConcurrentHashMap 的源码可以发现，Node 节点的定义是：

1
2
3
4
5
6
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
}

可以看到，里面定义了几个属性，分别如下：

  1. final 修饰的 hash 值，初始化后不能再次改变。
  2. final 修饰的 key, 初始化后不能再次改变。
  3. volatile 修饰的值
  4. volatile 修饰的下一节点指针

在get(Ojbect)方法的调用过程中。

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 V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //获取 hash 值
    int h = spread(key.hashCode());
    //通过 tabat 获取 hash 桶，tabAt 是一个线程安全的操作，有 UnSafe 来保证的。
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //如果该 hash 桶的第一个节点就是查找结果，则返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //第一个节点是树的根节点，按照树的方式进行遍历查找
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        //第一个节点是链表的根节点，按照链表的方式遍历查找
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

在这个过程中，

  1. 获取 hash 桶的根节点，通过 tabAt 来操作，线程安全。
  2. 遍历的时候用到了 node 的 next 属性，由于其与 volatile 修饰的，所以线程间可见，出现并发问题。
  3. 返回时读取 node 的 volatile 属性 val.

所以 get 过程中不用加锁也可以正确的获取对象。

5. Redis 的字典 rehash 和 JDK 中 hashmap 等 rehash 有什么不同？

这个问题比较宽泛，我个人的理解有以下两点。

  1. hashmap rehash 的时候的 另外一张 table 是临时创建的。而 redis 是时刻保持两张表的引用的。只是在需要 rehash 的时候才分配足够的空间。
  2. hashmap rehash 是一次性的，集中的完成 rehash 过程，而 redis 是渐进式 hash.

hashmap 的 rehash 过程想必大家都是了解的，那么这么稍微说一下 redis 的渐进式 hash.

首先，rehash 是要将原来表中的所有数据重新 hash 一遍，存放到新的表格中，以进行扩容。

而 redis 是一个单线程的高性能的服务，如果一个 hash 表中有几亿条数据，rehash 花费的时间将比较长，而在此期间，redis 是无法对外提供服务的，这是不可接受的。

因此，redis 实现了渐进式 hash. 过程如下：

  1. 假如当前数据在 ht[0] 中，那么首先为 ht[1] 分配足够的空间。
  2. 在字典中维护一个变量，rehashindex = 0. 用来指示当前 rehash 的进度。
  3. 在 rehash 期间，每次对 字典进行 增删改查操作，在完成实际操作之后，都会进行 一次 rehash 操作，将 ht[0] 在rehashindex 位置上的值 rehash 到 ht[1] 上。将 rehashindex 递增一位。
  4. 随着不断的执行，原来的 ht[0] 上的数值总会全部 rehash 完成，此时结束 rehash 过程。

在上面的过程中有两个问题没有提到：

  1. 假如这个服务器很空余呢？中间几小时都没有请求进来，那么同时保持两个 table, 岂不是很浪费内存？

解决办法是：在 redis 的定时函数里，也加入帮助 rehash 的操作，这样子如果服务器空闲，就会比较快的完成 rehash.

  1. 在保持两个 table 期间，该哈希表怎么对外提供服务呢？

解决办法：对于添加操作，直接添加到 ht[1] 上，因此这样才能保证 ht[0] 的数量只会减少不会增加，才能保证 rehash 过程可以完结。而删除，修改，查询等操作会在 ht[0] 上进行，如果得不到结果，会去 ht[1] 再执行一遍。

渐进式 hash 带来的好处是显而易见的，他采用了分而治之的思想，将 rehash 操作分散到每一个对该哈希表的操作上，避免了集中式 rehash 带来的性能压力。

与此同时，渐进式 hash 也带来了一个问题，那就是 在 rehash 的时间内，需要保存两个 hash 表，对内存的占用稍大，而且如果在 redis 服务器本来内存满了的时候，突然进行 rehash 会造成大量的 key 被抛弃。

参考文章

《Redis 设计与实现（第二版》

完。

ChangeLog

2019-05-19 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客或关注微信公众号 < 呼延十 > ——>呼延十

呼延十Developer

个人简介。