快手备考题

• 快手备考题
  • 数据结构
  • 多线程
  • 分布式
  • Redis
  • JVM

数据结构

红黑树的具体实现？有哪些应用？

• 实现：红黑树改良自二叉平衡树，具备二叉查找树的特性外，又不像二叉查找树那样需要频繁的左右旋来保证树的平衡性。
• 应用：HashMap、ConcurrentHashMap在Jdk1.8之后，从原来的数组+链表改为数组+红黑树的形式进行存储，保证遍历速度。

为什么红黑树的查找效率高？如何维护的？

• 首先红黑树的最长路径最多是最短路径的二倍长，避免了传统二叉查找树的退化成链表的问题
• 其次，红黑树在插入一个新节点的时候，因为是红色节点，所以只需要平衡一下对应节点的红黑数量即可

HashMap、HashTable、ConcurrentHashMap？

I. HashMap

• HashMap常用于键值对存储，本身是非线程安全的，采用Fast-fail策略，如果集合中元素被其他线程修改会抛出异常；
• HashMap在Jdk1.7~1.8迭代中有明显结构变化，从原来的数组+链表的存储实现方式改为了数组+红黑树，如果链表的长度超过8（可设置），就会转化为红黑树；
• HashMap的寻址，会先用 hashCode(key)取到key的hash值，再对%map.size()，获取对应的位置，如果已有数据，则遍历链表 / 红黑树；
• 由于size的变动会导致key的hash变化，导致所有数据重hash()，所以尽量设置好初始大小；
• 如果真的触发扩容了，size会变为原来的两倍，且上限为2^31-1；
• Jdk1.7和1.8的扩容不同：

HashMap 的Fail-Fast是怎么实现的？

• 遍历HashMap时，维护一个volatile修饰的modCount，修改操作会变更这个值，如果获取next或者hasNext的时候，会检查modCount，如果不一致就会抛出异常 ConcurrentModificationException；
• JU包下大多是Fail-Fast防止并发修改引起的错误，JUC下大多是Fail-Safe保证并发修改的成功；

II. HashTable

• HashTable的初始容量为11（为啥？）；
• 扩容时，HashTable会额外再加一个；
• HashTable因为用的安全失败原则（Fail-Safe），无法判断key不存在还是key为null，所以不允许key、Val为Null；
• HashTable整个Map被synchronized修饰，线程安全但是效率低；

III. ConcurrentHashMap

• 线程安全的HashMap版本，底层同样为（数组+链表） => （数组+红黑树），并且和HashTable直接对整个HashMap上锁不同的是，ConcurrentHashMap采用分段锁，划定不同的segment，不同之间的segment互不影响；
• Jdk1.7中ConcurrentHashMap做的优化：1）Segment用volatile修饰了存储数据用的HashEntry<K,V>[]，保证线程之前是互相可见的；2）put操作时，先尝试获得锁（tryLock()），如果获取失败，就开始自旋，不断尝试获取锁；3）达到设置的自旋上限后，转为阻塞形式获取锁；
• get()操作本身没有过多操作，仅为内存寻址，故没有过多的锁操作；
• Jdk1.8中，将Segment的分段锁改为了CAS+synchronized，原本的HashEntry()改为了，链表/红黑树的自动转换模式；

Jdk1.8中ConcurrentHashMap如何保证线程安全的？

• put()操作时，首先检查阈值和容量，如果可以存入的话就对存取操作进行CAS的自旋获取锁，获取到了就存入，如果没有获取到，就尝试进行synchronized加锁写入；写入后判断当前节点的Node数量是否大于设定的阈值（默认8），决定是否要转化列表为红黑树；

CAS的自选获取锁是什么？

• 1）通过本地方法（native修饰的方法）获取变量A的值为OldValue；2）准备好新的变量值NewValue；3）再通过本地方法获取变量A的值ExceptValue；4）判断OldValue和ExceptValue是否相同，如果相同，就把NewValue赋值给变量A；
• 类似于 update table set a = :newVal where a = :oldVal；

CAS有什么弊端么？

• ValueA -> ValueB -> ValueA的情况无法被掌控到，一般如果需要感知的话，就添加一个版本号 / 操作时间即可；

synchronized本身是重量级锁，导致了HashTable的效率低下，为什么还要引入？

• Jdk1.8以后的synchronized是优化过后的升级锁，本身为偏向锁（同一线程获取锁不需要竞争），如果获取锁失败的话就会升级为CAS自旋锁，最后才升级为重量锁

锁都有什么状态？

• 无锁、偏向锁、轻量级锁和重量级锁；

锁是怎什么实现的？

• Java对象中，存在一个Monitor的绑定对象，可以和对象同时创建或者在对象出现锁现象是创建，当monitor被某个Thread标识的时候，该对象上锁；
• 当多个线程同时访问一段被synchronized修饰的代码时，首先添加进_EntryList集合，当某个线程获取到对象的monitor对象后，进入_Owner区域并把monitor中的owner变量设置为当前线程，同时monitor中的计数器count加1；
• 当某个线程调用wait()方法，将释放当前持有的monitor，owner变量恢复为null，count自减1，同时该线程进入WaitSet集合中等待被唤醒；
• 当某个线程执行完毕，释放monitor对象并复位owner和count；

获取锁和退出锁的详细有了解吗？

• 在编译后的文件看来，主要是有monitorenter和monitorexit两条指令；
• 1）monitorenter：首先尝试获取monitor 的持有权，当monitor的进入计数器为0时，线程可以成功取得monitor，并将计数器值设置为1，取锁成功（如果当前线程已经拥有monitor的持有权，那重入时计数器的值也会加1；若目标锁对象的计数器不为0，那当前线程将被阻塞，直到正在执行线程执行完毕.
• 2）monitorexit：JVM将monitor计数器减1；
• 一条指令monitorenter可以对应到多条monitorexit指令，包括但不限于：提前返回、抛出异常、ifElse分支等；

synchronized本身说一下？

• synchronized初始为偏向锁：如果一个线程获得了锁，JVM给Monitor对象的标记字段添加该线程占有标识（ThreadId）和对象是偏向锁的标识（后三位置为101），当这个线程再次请求锁时，直接可以获取锁；如果一个对象被其他线程尝试获取，那么就给对象的epoch值+1，当达到一定阈值之后，这个偏向锁就无效了，原来的线程获取一样要加锁，再超过一个更大的阈值后，该对象直到JVM重启之前，都直接升级为轻量级锁；
• 升级后的轻量级锁：标记字的后两位为00（01 代表无锁或偏向锁，10 代表重量级锁），自选获取锁，自旋超过10次升级为重量级锁；
• 最后，synchronized修饰的代码块，在编译后Flags标识位上添加了ACC_SYNCHRONIZED标识，进入这部分代码或者退出（正常 || 不正常）都要执行配套的monitorenter和monitorexit方法；在早期，这两个操作，依赖于调用OS的MutexLock实现的，线程之间的切换时需要从用户态转换到核心态，时间成本较高，而这个过程，也叫重量级锁；

线程的状态？

• 线程的状态有新建、就绪、运行、阻塞、死亡；其中挂起、睡眠会导致阻塞的发生；

多线程

线程池的核心参数？调参？为什么？

• corePoolSize：核心线程数，即使这些线程处理空闲状态，他们也不会被销毁，创建了，就创建了；
• maximumPoolSize：一个任务被提交到线程池以后，首先会找有没有空闲存活线程，如果有则直接将任务交给这个空闲线程来执行，如果没有则会缓存到队列中，如果队列满了，才创建一个新线程，从工作队列的头部取出一个任务交由新线程来处理，而将刚提交的任务放入工作队列尾部，最大线程数限制了一共能创建多少线程的数量；
• keepAliveTime：存活时间，空闲线程的存活时间；
• 队列：1）有界阻塞队列：如果核心线程数满了，就会放入队列，先入先出，最大线程数也满了，就执行拒绝策略；2）无界阻塞队列：最大容量为Integer.MAX(2^32-1)的队列，使用该队列等于无视最大线程数，因为都进队列了；3）无队列，有任务就创建线程，最大线程不够了就执行拒绝策略；4）优先级阻塞队列：PriorityBlockingQueue，优先级由存入对象的Comparator函数决定；
• handler：拒绝策略，上文提到的xxx都满了时，任务的处理方案，共四种：1）直接抛弃任务；2）丢弃任务，并抛异常RejectedExecutionException；3）在调用线程中执行被拒绝任务的run方法；4）抛弃先进队列的任务；
• 计算密集的业务，频繁使用CPU的，core就是CPU数，最大CPU+1，过多的线程数会导致每个线程都想去CPU请求资源，导致频繁切换；
• IO密集的业务，网络通信、MySQL、文件流比较多的机器，核心也是CPU数，最大2/(1-阻塞系数<IO耗时/CPU耗时>)；

CAS

• 内存的原子性操作，意为CompareAndSwap，保证操作数据在修改过程中没有其他数据参与修改；

线程锁都有什么？

• 按照维度不同分为：1）偏向、轻量、重量锁；2）乐观、悲观锁；3）互斥、自选锁；4）可重入、不可重入锁；5）读写锁；

互斥锁？

• 本质上和数据结构由数组、链表构成一样，线程锁主要是由互斥锁和自旋锁构成的；其中互斥锁如果竞争失败，会把线程挂起，资源释放回CPU；自旋锁竞争失败，线程会忙等待，不断的询问是否可以竞争锁；
• 互斥锁：只要线程A持有锁，线程B请求锁就会失败，并被操作系统挂起，从用户态转为内核态，用户不可操作，直到线程A释放锁，操作系统会将线程B设置为就绪状态，等到CPU可以分配资源了，就把线程B重新置为运行；
• 自旋锁：通过CPU提供的CompareAndSwap函数进行实现，不进行用户态和内核态的切换；步骤是：1）查看锁对象状态是否空闲；2）如果空闲设置为持有；在CPU的帮助下，这两条指令是一定一起执行的，不会有其他干预；
• 上下文切换的时间消耗在微秒级，如果被锁部分的代码执行很快，就应该用自旋锁减少上下文切换；

读写锁？

• 读写锁用于可以区分读场景和写场景的情况；读锁可以被多个线程所持有，是共享锁，而写锁只能被一个线程所拥有，且写锁被持有之后，在释放之前会阻塞该对象的所有读锁；
• 读写锁又分为读优先和写优先和公平锁：1）读优先锁：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 仍然可以成功获取读锁，最后直到读线程 A 和 C 释放读锁后，写线程 B 才可以成功获取写锁；2）写优先锁：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取读锁；3）读写公平锁：用队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁；

悲观乐观锁？

• 访问共享资源先上锁，叫悲观锁；访问共享资源并操作，操作完了看看这段时间有没有人该过这段数据，如果没有就操作成功，叫乐观锁；
• 只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

分布式

分布式的CAP有什么了解的吗？

• 分别代表一致性、可用性、容错性，一般的服务是要求最终一致性，保证服务的可用性和容错性，毕竟在用户角度来讲如果服务没有在运行，一致性也就没有意义了，而因为一个服务导致的整体宕机，没有容错也是不行的；

可用性的处理经验?
性能优化
缓存的回源, 数据库和缓存的一致性要求和保证方案?

Redis

Redis的五种数据结构？

• 字符串、list、hash、set、zset；

Redis怎么保障速度很快可用性很高的?

• 内存操作；专有的数据结构；单线程 + 多路IO复用，避免过多的线程切换开销；自定义协议；

Redis的IO操作的实现方式是什么?

• 多路复用IO，在允许范围内，有多少请求就开多少个socket处理任务，同时开启一个轮询线程检查所有的socket是不是已经执行完成，如果执行完成通知客户端获取数据；
• 每个socket都被绑定了一个文件处理器，当socket链接时，文件处理器开始处理任务，监听到任务完成就给socket返回数据；

内存的使用优化Redis是怎么做的? 除了过期时间和LRU以外的部分?

SDS的实现, 优劣势?

• 传统字符串使用空字符结尾的字符数组，而Redis用键值对的方式，值中保存着SDS对象；SDS由：字符串空闲地址 + 字符串长度 + 字符串数组组成；SDS遵循 C 字符串以空字符结尾的惯例，保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面，并且为空字符分配额外的 1 字节空间；
• SDS可以直接获取字符串长度而无需遍历，而且不存在内存溢出情况，如果内存空间不足会去申请；
• 因为C字符串的长度是固定的，每次修改字符串都要进行内存分配，增长申请、减少释放；
• SDS给字符串分配空间的时候，除了应有的空间，还会预分配一部分free，小于1M的，直接翻倍，大于1M的，给1M，这样针对同一个Key的Val修改，大部分时间是不需要重新申请内存的；
• 惰性释放：当字符串减少长度之后，没有直接回收内存，后续可以通过API回收；

Redis的垃圾收集处理? 对于没有引用的key是怎么处理的?

• 一般有三种：1）惰性回收：内存不友好，每次获取再检查是否过期；2）定时删除：给定定时器，但是会大量损耗CPU；3）定期扫描过期的数据；
• 都满了的时候用淘汰策略处理；

缓存击穿、缓存雪崩

• 缓存雪崩：某一时间，大量缓存失效，导致大量压力走到数据库，数据库宕机引起的问题；一般可以：1）获取数据的地方上锁，没有缓存要先被锁住然后等待缓存种上了再放开访问；2）定期发消息设置更新缓存；3）不同的失效时间；4）开启中间件的二级缓存；
• 缓存击穿：大量不存在的key越过缓存直接访问数据库；一般可以：1）BitMap维护一个布隆过滤器，去掉绝对不存在的值；2）缓存为空的值；3）封IP；

一致性Hash了解多少

• 传统Hash是hashCode%size来获取数据位置，size的变动会导致整体都进行reHash，通常这个时候都是降低访问效率甚至是不可访问的；为了防止这一情况，一致性hash就把hashCode%2^32，然后把服务器再和2^32做%运算，这样就把数据均匀的散落开，离哪个数据近就去哪个值，如果服务器节点过少，就加几个虚拟节点，都代指同一个服务器；

JVM

日常用到的垃圾回收器是什么?

• G1，优化版CMS，用标记-整理法，给整个堆划分为大小相同的Region，可以设置预期回收时间减少对用户的影响（G1会记录每个Region的回收时间，如果太久了就下次再回收，优先回收那些快的；
• 一般的收集器：【最老】Serial~Serial Old；【并发可和CMS同用】ParNew~CMS；【并发高吞吐】Parallel Scanage~Parallel Old；【并发灵活自定义】G1；

了解过CMS吗?

• 号称无停留用户影响最低，给老年代用的垃圾收集器；分为：并行的初次标记GcRoots、标记关联对象，阻塞但是时间很短的重标记，并行清理，并行重置；如果正在处理的时候发生FullGC，就转为用SerialOld；

垃圾回收算法了解过哪些吗?

• 标记-清除，一般不用，只有CMS在用；标记-复制，一般新生代在用，Survior用于给Eden复制，适用于幸存少的情况；标记-整理，一般老年代在用，需要移动的少；
• 每种算法对不同的年代的标记和处理方式?
• 算法：
  • 字符串转数字？简易计算器？
  • 快排
  • 左边界右边界
  • 给你一个数组元素大于0的整数数组nums；以及一个整数 sum 。
    • 数组中，每个元素可以使用无限次
      • 求由数组元素相加等于sum所需的最少数组元素个数。
    • 如果没有任何一种数组元素组合相加等于sum，返回-1

Java对象的组成？

• 1）对象头：标记字段 + 类型指针，其中标记字段根据对象需求不同可以存储不同类型的数据；2）实例数据：存储属性数据信息，包括父类的属性信息；3）补齐数据：因为HotSpot要求对象的大小必须是8字节的整数倍，所以不足的部分需要补齐，提升计算机寻址效率；

标记字段具体都有什么能简单说说吗？

• 1）锁标志位：区分锁状态，只有最后2位数据有效，一般 11 时表示待GC回收状态，01代表有锁；
• 2）是否偏向锁：用于区分偏向锁和其他锁；
• 3）分代年龄：表示对象被GC的次数，当该次数到达阈值的时候，对象就会转移到老年代；
• 4）对象的hashcode：System.identityHashCode()的计算结果，初始化后会延迟计算，并把结果赋值，长度不够用的时候转移到Monitor；
• 5）偏向锁线程Id：当某个线程持有对象的时候，被置为该线程的ID，在后面的操作中，就无需再进行尝试获取锁；
• 6）偏向锁标识：偏向锁在CAS锁操作过程中，表示对象更偏向哪个锁。
• 7）ptr_to_lock_record & ptr_to_heavyweight_monitor：轻量重量锁的区分