字节跳动后端日常实习面经

目录

• • 1.HashMap 的底层数据结构
  • 2.什么时候变成红黑树？为什么要选择数组 + 链表的结构？
  • 3.HashMap 的扩容机制
  • 4.进程和线程的区别
  • 5.一个进程中有哪些数据段？
  • 6.乐观锁和悲观锁
  • 7.介绍一下版本号机制
  • 8.介绍一下 CAS
  • 9.Redis 过期数据删除策略
  • 10.Redis 内存淘汰机制
  • 11.缓存穿透
  • 12.布隆过滤器的原理

1.HashMap 的底层数据结构

在 JDK 1.7 中，HashMap 使用的是数组 + 链表实现。
在 JDK 1.8 中使用的是数组 + 链表或红黑树实现的。

put实现原理
（1）先判断当前Node[]数组是不是为空，为空就新建，不为空就对hash值与容量-1做与运算得到数组下标
（2）然后会判断当前数组位置有没有元素，没有的话就把值插到当前位置，有的话就说明遇到了哈希碰撞
（3）遇到哈希碰撞后，如果Hash值相同且equals内容也相同，直接覆盖，就会看下当前链表是不是以红黑树的方式存储，是的话，就会遍历红黑树，看有没有相同key的元素，有就覆盖，没有就执行红黑树插入
（4）如果是普通链表，则按普通链表的方式遍历链表的元素，判断p.next = null的情况下，直接存放追加在next后面,然后我们要检查一下如果链表长度大于8且数组容量>=64链表转换成红黑树，否则查找到链表中是否存在该key，如果存在直接修改value值，如果没有继续遍历
（5）如果++size > threshold(阈值)就扩容

HashMap中put的实现原理
HashMap何时会链表转红黑树

2.什么时候变成红黑树？为什么要选择数组 + 链表的结构？

什么时候才会转换为红黑树？
当Map链表长度大于或等于阈值TREEIFY_THRESHOLD（默认为 8）的时候，如果同时还满足容量(数组的长度)大于或等于 MIN_TREEIFY_CAPACITY（默认为 64）的要求，就会把链表转换为红黑树。同样，后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态。

数组 + 链表的结构是 HashMap 的一种经典实现方式，其主要优点包括：

1. 空间利用率高：数组可以预先分配一定的空间，而链表可以动态地添加和删除元素，因此可以充分利用内存空间，避免浪费。

2. 插入和删除元素的效率高：由于链表的特性，插入和删除元素的时间复杂度为 O(1)，因此在插入和删除元素时，数组 + 链表的结构比纯数组结构更加高效。

3. 支持快速查找元素：由于数组的特性，可以通过下标快速访问数组中的元素，因此在查找元素时，数组 + 链表的结构比纯链表结构更加高效。

4. 支持高效的哈希计算：由于数组的特性，可以通过哈希函数将键映射到数组的某个位置，从而快速定位元素所在的桶，因此在哈希计算时，数组 + 链表的结构比纯链表结构更加高效。

需要注意的是，数组 + 链表的结构也存在一些缺点，例如：

1. 当链表过长时，查找元素的效率会降低，因此需要将链表转换为红黑树，以提高查找效率。

2. 当哈希表中的元素数量过多时，需要进行扩容操作，这会导致一定的性能损失。

因此，在实际应用中，我们需要根据具体的场景和需求，选择合适的数据结构和算法，以达到最优的性能和空间效率。

3.HashMap 的扩容机制

• capacity 即容量，默认16。
• loadFactor 加载因子，默认是0.75
• threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。

一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。
HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE（ 2^31 - 1，即永远不会超出阈值了）。

hashmap长度为什么是2的倍数
当我们向 HashMap 中添加一个元素时，HashMap 会根据元素的哈希值计算出该元素在数组中的位置，计算公式为：(n - 1) & hash，其中 n 表示数组的长度，hash 表示元素的哈希值。由于 n 必须是 2 的幂次方，因此 n - 1 的二进制表示中所有位都是 1，这样就可以保证计算出的位置在数组的有效范围内。

拓展题
1.准备用HashMap存1W条数据，构造时传10000还会触发扩容吗？存1000呢？

• 如果我们从外部传递进来 10000 初始化 initialCapacity ，实际上经过 tableSizeFor 方法处理之后，最终 threshold 就会变成 2 的 14 次幂 16384，再在 resize 方法中乘上负载因子 0.75，实际在不触发扩容的前提下，可存储的数据容量是 12288(16384 * 0.75)，用来存放 10000 条数据，绰绰有余，所以并不会触发扩容。
• 如果我们从外部传递进来 1000 初始化 initialCapacity ，实际上经过 tableSizeFor 方法处理之后，最终 threshold 就会变成 2 的 10 次幂 1024，再在 resize 方法中乘上负载因子 0.75，实际在不触发扩容的前提下，可存储的数据容量是 768 (1024* 0.75)，它是不足以承载 1000 条数据的，最终在存够 1k 条数据之前，还会触发一次动态扩容。

2.如何选择初始化容量
阿里巴巴java手册解释到

  想要使用 HashMap 存放 10000 条数据，应该设置 initialCapacity = 10000 / 0.75 + 1 = 13334，然后哈希表容量会被 tableSizeFor 方法调整到 16384(2^14)，threshold = 16384 * 0.75 = 12288 足够存储 10000 条数据而不会触发扩容。
  想要使用 HashMap 存放 1000 条数据，应该设置 initialCapacity = 1000 / 0.75 + 1 = 1334，然后哈希表容量会被 tableSizeFor 方法调整到 2048(2^11)，threshold = 2048* 0.75 = 1536 足够存储 1000条数据而不会触发扩容。

4.进程和线程的区别

进程
是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行『资源分配和调度』的一个独立单位。
线程
进行运算调度的最小单位，其实是进程中的一个执行任务（控制单元），负责当前进程中程序的执行
两者之间的区别
「本质区别」：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位
「在开销方面」：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小
「所处环境」：在操作系统中能同时运行多个进程（程序）；而在同一个进程（程序）中有多个线程同时执行（通过CPU调度，在每个时间片中只有一个线程执行）
「内存分配方面」：系统在运行的时候会为每个进程分配不同的内存空间；而对线程而言，除了CPU外，系统不会为线程分配内存（线程所使用的资源来自其所属进程的资源），线程组之间只能共享资源
「包含关系」：没有线程的进程可以看做是单线程的，如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的；线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程

5.一个进程中有哪些数据段？

在一个进程中，通常会包含以下几个数据段：

1. 代码段（text segment）：也称为只读代码段，存储程序的机器指令，通常是只读的，不允许修改。

2. 数据段（data segment）：存储程序中已经初始化的全局变量和静态变量，包括全局变量、静态变量、常量等。

3. BSS 段（bss segment）：存储程序中未初始化的全局变量和静态变量，通常会被初始化为 0。

4. 堆（heap）：存储动态分配的内存，由程序员手动申请和释放。

5. 栈（stack）：存储函数调用时的局部变量、函数参数、返回地址等信息，由系统自动分配和释放。

需要注意的是，不同的操作系统和编译器可能会对数据段的划分方式有所不同，上述数据段只是一般情况下的划分方式。此外，还有一些特殊的数据段，如共享内存段、内存映射文件等，它们通常用于进程间通信和共享数据。

6.乐观锁和悲观锁

从对待锁的态度划分:乐观锁、悲观锁

• 乐观锁
  总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和 CAS 算法实现。 乐观锁适用于多读的应用类型，这样可以提高吞吐量，像数据库提供的类似于 write_condition 机制，其实都是提供的乐观锁。在 Java 中 java.util.concurrent.atomic 包下面的原子变量类就是使用了乐观锁的一种实现方式 CAS 实现的。

• 悲观锁
  总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁（共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程）。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。 Java 中 synchronized 和 ReentrantLock 等独占锁就是悲观锁思想的实现。

乐观锁 适合 读操作多 的场景，相对来说写的操作比较少。它的优点在于 程序实现 ， 不存在死锁
问题，不过适用场景也会相对乐观，因为它阻止不了除了程序以外的数据库操作。
悲观锁 适合 写操作多 的场景，因为写的操作具有 排它性 。采用悲观锁的方式，可以在数据库层
面阻止其他事务对该数据的操作权限，防止 读 - 写 和 写 - 写 的冲突。

7.介绍一下版本号机制

一般是在数据表中加上一个数据版本号 version 字段，表示数据被修改的次数，当数据被修改时， version 值会加一。当线程 A 要更新数据值时，在读取数据的同时也会读取 version 值，在提交更新时，若刚才读取到的 version 值为当前数据库中的 version 值相等时才更新，否则重试更新操作，直到更新成功。

8.介绍一下 CAS

CAS（Compare and Swap）比较并交换，是一种乐观锁的实现，是用非阻塞算法来代替锁定，其中 java.util.concurrent 包下的 AtomicInteger 就是借助 CAS 来实现的。
原理
CAS （CompareAndSwap）
CAS有3个操作数，位置内存值V，旧的预期值A，要修改的更新值B。
当且仅当旧的预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做或重来

CAS会导致“ABA问题”。
CAS算法实现一个重要前提需要取出内存中某时刻的数据并在当下时刻比较并替换，那么在这个时间差类会导致数据的变化。
如说一个线程one从内存位置V中取出A，这时候另一个线程two也从内存中取出A，并且线程two进行了一些操作将值变成了B，然后线程two又将V位置的数据变成A，这时候线程one进行CAS操作发现内存中仍然是A，然后线程one操作成功。
尽管线程one的CAS操作成功，但是不代表这个过程就是没有问题的。
解决方案
Java 提供了一个 AtomicStampedReference 原子引用变量

9.Redis 过期数据删除策略

如果不熟悉可以看这篇
Redis过期删除策略和内存淘汰策略

立即删除

Redis不可能时时刻刻遍历所有被设置了生存时间的key，来检测数据是否已经到达过期时间，然后对它进行删除。

立即删除能保证内存中数据的最大新鲜度，因为它保证过期键值会在过期后马上被删除，其所占用的内存也会随之释放。但是立即删除对cpu是最不友好的。因为删除操作会占用cpu的时间，如果刚好碰上了cpu很忙的时候，比如正在做交集或排序等计算的时候，就会给cpu造成额外的压力，让CPU心累，时时需要删除，忙死。。。。。。。
这会产生大量的性能消耗，同时也会影响数据的读取操作。

总结：对CPU不友好，用处理器性能换取存储空间
惰性删除

数据到达过期时间，不做处理。等下次访问该数据时，
如果未过期，返回数据 ；
发现已过期，删除，返回不存在。

惰性删除策略的缺点是，它对内存是最不友好的。

如果一个键已经过期，而这个键又仍然保留在redis中，那么只要这个过期键不被删除，它所占用的内存就不会释放。
在使用惰性删除策略时，如果数据库中有非常多的过期键，而这些过期键又恰好没有被访问到的话，那么它们也许永远也不会被删除(除非用户手动执行FLUSHDB)，我们甚至可以将这种情况看作是一种内存泄漏–无用的垃圾数据占用了大量的内存，而服务器却不会自己去释放它们，这对于运行状态非常依赖于内存的Redis服务器来说,肯定不是一个好消息

定期删除
定期删除策略是前两种策略的折中：
定期删除策略每隔一段时间执行一次删除过期键操作，并通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响。

周期性轮询redis库中的时效性数据，采用随机抽取的策略，利用过期数据占比的方式控制删除频度
特点1：CPU性能占用设置有峰值，检测频度可自定义设置
特点2：内存压力不是很大，长期占用内存的冷数据会被持续清理
总结：周期性抽查存储空间 （随机抽查，重点抽查）

总结
Redis服务器实际使用的是惰性删除和定期删除两种策略：通过配合使用这两种删除策略，服务器可以很好地在合理使用CPU时间和避免浪费内存空间之间取得平衡。

10.Redis 内存淘汰机制

如果不熟悉可以看这篇
Redis过期删除策略和内存淘汰策略

1.内存淘汰策略
有哪些

• noeviction: 不会驱逐任何key
• allkeys-lru: 对所有key使用LRU算法进行删除
• volatile-lru: 对所有设置了过期时间的key使用LRU算法进行删除
• allkeys-random: 对所有key随机删除
• volatile-random: 对所有设置了过期时间的key随机删除
• volatile-ttl: 删除马上要过期的key
• allkeys-lfu: 对所有key使用LFU算法进行删除
• volatile-lfu: 对所有设置了过期时间的key使用LFU算法进行删除

总结一下怎么记住这8个
2 * 4 得8
2个维度

过期键中筛选所有键中筛选

4个方面

LRULFUrandomttl

你平时用哪一种
平常使用allkeys-lru
系统默认的是noeviction

11.缓存穿透

1.是什么
请求去查询一条记录，先redis后mysql发现都查询不到该条记录，
但是请求每次都会打到数据库上面去，导致后台数据库压力暴增，这种现象我们称为缓存穿透，这个redis变成了一个摆设。。。。。。
简单说就是本来无一物，既不在Redis缓存中，也不在数据库中
2.解决方案
1.空对象缓存或者缺省值
一般OK

but
黑客或者恶意攻击
黑客会对你的系统进行攻击，拿一个不存在的id 去查询数据，会产生大量的请求到数据库去查询。
可能会导致你的数据库由于压力过大而宕掉

• id相同打你系统
  第一次打到mysql，空对象缓存后第二次就返回null了，
  避免mysql被攻击，不用再到数据库中去走一圈了

• id不同打你系统
  由于存在空对象缓存和缓存回写(看自己业务不限死)，
  redis中的无关紧要的key也会越写越多(记得设置redis过期时间)

2.布隆过滤器

如果不熟悉可以看这篇
布隆过滤器BloomFilter

布隆过滤器优缺点

• 优点
  高效地插入和查询，占用空间少
• 缺点
  不能删除元素。因为删掉元素会导致误判率增加，因为hash冲突同一个位置可能存的东西是多个共有的，你删除一个元素的同时可能也把其它的删除了。
  存在误判，不同的数据可能出来相同的hash值

结论：
有，是可能有
无，是肯定无

12.布隆过滤器的原理

布隆过滤器实现原理和数据结构
布隆过滤器(Bloom Filter) 是一种专门用来解决去重问题的高级数据结构。
实质就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成，用来快速判断某个数据是否存在。但是跟 HyperLogLog 一样，它也一样有那么一点点不精确，也存在一定的误判概率

添加key时
使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，
每个hash函数都会得到一个不同的位置，将这几个位置都置1就完成了add操作。
查询key时
只要有其中一位是零就表示这个key不存在，但如果都是1，则不一定存在对应的key。
结论：
有，是可能有
无，是肯定无
进一步
当有变量被加入集合时，通过N个映射函数将这个变量映射成位图中的N个点，
把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1， 就可以大概率知道集合中有没有它了
如果这些点，有任何一个为零则被查询变量一定不在，
如果都是 1，则被查询变量很可能存在，
为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

步骤
初始化
布隆过滤器 本质上 是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0

添加
当我们向布隆过滤器中添加数据时，为了尽量地址不冲突，会使用多个 hash 函数对 key 进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。
例如，我们添加一个字符串wmyskxz

判断是否存在
向布隆过滤器查询某个key是否存在时，先把这个 key 通过相同的多个 hash 函数进行运算，查看对应的位置是否都为 1，
只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在；
如果这几个位置全都是 1，那么说明极有可能存在；
因为这些位置的 1 可能是因为其他的 key 存在导致的，也就是前面说过的hash冲突。。。。。
就比如我们在 add 了字符串wmyskxz数据之后，很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的；
此时我们查询一个没添加过的不存在的字符串inexistent-key，它有可能计算后坑位也是1/3/5 ，这就是误判了…


布隆过滤器误判率，为什么不要删除
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，
因此误判的根源在于相同的 bit 位被多次映射且置 1。
这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。
如果我们直接删除这一位的话，会影响其他的元素
特性
一个元素判断结果为没有时则一定没有，
如果判断结果为存在的时候元素不一定存在。
布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。
小总结