小红书二面

总体流程大概 45min 左右，已收感谢信，总的来说是因为自己这两个礼拜没怎么准备八股，算法没撕出来。面经如下：1.你自己做的项目有锁的释放是怎么实现的？什么比较亮眼的功能，可以拿出来说一下，方案是什么样的？2.锁的释放是怎么实现的？3.你的库存防超卖是通过 Redis 所做的吗？还有什么其他技术吗？java 八股：1.比较常用的 HashMap 是一个什么数据结构？哈希冲突的情况下，除了拉链法，还有什么其他方法？2.红黑树是什么样的结构？为什么需要转成红黑树？3.HashMap 在多线程环境下是不是一个线程安全的容器？为什么说 HashMap 它不是一个线程安全？会产生什么问题？4.ConcurrentHashMap 是怎么解决 HashMap 的线程安全问题的？在 ConcurrentHashMap 里面，用 CAS 去上锁，如果说 CAS 失败的话会怎么办？ConcurrentHashMap 的扩容机制了解吗？5.比较 synchronized 和 reentrylock 的异同点。volatile 的那个变量（state）的作用是什么。什么状态下是表示加锁成功了，在 AQS 里面？这个 tryAcquire 方法的整体流程是什么样子的？介绍一下 volatile 关键字有什么用吗？synchronized 它的底层是怎么去实现的？MySQL：1.MySQL 里面的索引是一个什么样的一个数据结构？为什么会选择 B+ 树的这种数据结构而不用 B 树？相对于 B 树有什么优势？2.索引优化的一些常用方案方法说一下，为什么最左前缀原则不能跳过中间列？为什么百分号放在前面就会产生索引失效？手撕：输入： 给定一个二叉树的根节点。每个节点除了左右子节点外，还有一个额外的 next 指针。目标： 填充所有节点的 next 指针，使其指向同一层级（同一深度）的下一个右侧节点。如果该节点已经是该层最右侧的节点，则 next 指针设置为 null。就给20 分钟，没做出来。复习：1.哈希冲突：拉链法和开放地址法。（如果当前索引已经被使用，那么按顺序检查下一个位置）。或者再哈希法，使用多个不同的哈希函数，第一个冲突的话就使用第二个函数，依此类推。2.红黑树是一种自平衡的二叉树，给每个节点添加红色或黑色的属性，确保插入或删除后能够保持基本平衡。原因： 哈希冲突严重情况下，一个桶内的元素全部形成链表，查找性能退化到 on，红黑树可以保证 logn，提升可靠性。3.hashmap 不是线程安全的是因为并发下对其进行读写操作，多个线程同时调用 put 向同一个桶写入数据，可能会出现写丢失或覆盖的现象。jdk1.7 中，扩容使用头插法迁移元素，可能会导致循环链表，此时再调用get 方***陷入循环，再 jdk1.8 中使用尾插法。其次，没有同步机制下，一个进程遍历 hashmap，另一个线程进行修改，可能会导致遍历失败，抛异常。4.concurrenthashmap在 jdk1.7 用分段锁解决线程问题，segment 数组，整个 map 分成多个 segment，可以独立加锁。jdk1.8 之后使用 cas + synchronized 来操作，Node 数组和链表红黑树，读的时候无锁，写的时候先尝试 cas，如果失败，就对当前桶节点进行 synchronized 加锁。cas 操作失败后，线程会不断 cas 自旋操作频繁失败的话放弃自旋转而阻塞。扩容机制：触发条件： 当数组中元素个数超过负载因子（默认为 0.75）乘以数组容量时触发扩容，新容量通常是旧容量的 2 倍.无锁化迁移： 扩容过程不是由单个线程一次性完成的，而是通过多线程并发地、增量地进行数据迁移.协助扩容（Help）： 线程 A 触发扩容后，其他线程（如线程 B、C...）在进行 put、get 等操作时，如果发现有扩容任务正在进行，它们会主动参与进来，帮助进行部分数据的迁移工作. 这样可以快速分散扩容的压力.原子性保证：线程在迁移某个桶（Bucket）时，会使用 synchronized 锁住当前桶的头结点，确保该桶的数据迁移是安全的.迁移完成后，会在旧数组的该桶位置设置一个特殊的 ForwardingNode，用于指引其他线程到新数组中查找数据.5.synchronized是基于 jvm 实现的，依赖对象头中的 mark word，jdk1.6 以后引入锁升级机制，会进行自动释放锁，可重入，不过功能比较单一，不支持中断，不支持超时获取锁，非公平锁。reentrylock 是 juc 包提供的显示锁，基于 aqs 实现，需要在 finally 块中调用 unlock方法来释放锁，否则可能会造成死锁。功能更加强大，支持公平锁和非公平锁。state总结：对于独占锁（reentrylock）表示锁的重入次数，或者持有状态对于共享锁（semaphore）表示可用的共享资源数量。violate 保证对 state 变量的修改可以被所有线程看到。加锁成功状态：通过 cas 操作，把 state 从 0 设置到 1，如果已经持有锁，那么就 state + 1.try acquire 是 aqs 子类，该方法尝试获取资源。首先读取当前同步状态 state，如果无锁，尝试 cas 修改 state，返回 true。如果有锁，判断是不是自己的线程，是的话继续修改 state，否则返回 false；viloate总结：保证内存可见性，修改的时候会立即刷新到主存当中去。禁止指令重排序，保证变量之前的代码一定会提前完成。但是对于复合操作 i++，不保证原子性。synchronized 底层实现：是java 的隐式锁，主要涉及对象头的锁升级机制。字节码层面，有 monitorenter 和 monitorexit 两个字节码指令实现，enter 尝试获取对象锁的监视器，exit 是释放监视器。锁定的对象，状态记录在对象头，mark word，存储锁状态，哈希码，gc 年龄，以及相关指针或线程 id，通过修改 mark word 实现锁的升级和状态切换。锁升级机制：无锁--偏向锁--轻量级锁--重量级锁偏向锁：第一次获取，线程 id 记在 mark word 中，后续无同步操作。轻量级锁：cas 操作， 尝试将 mark word指向自己的栈中 Lock Record，失败就自旋。重量级锁：竞争激烈，长时间阻塞。涉及到阻塞和内核态装换，重量级锁依赖操作系统 mutex lock 实现，涉及操作系统层面的调度，开销比自旋要大得多。MySQL：1.使用 b+数优势是优化了磁盘 io 效率和范围查询能力。io效率高是因为非叶子节点体积小，单个磁盘页可以存更多的索引键，高度更矮。范围查询是所有叶子节点通过双向链表链接，可完成范围查询。性能也更加稳定。2.索引优化：建立索引，确保 where，orderby 使用合适的索引。遵循最左前缀原则，从最左侧列开始匹配。覆盖索引：尽量只查索引中包含的字段，避免回表。避免索引失效：进行函数运算，类型抓换或者模糊匹配。