base：北京

到店事业群-平台技术部

##2021.8.27 美团 二面

1.自我介绍

2.实习项目介绍

3.HashMap

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

3.1 数据结构

jdk1.8以前是数组+链表 jdk1.8以后是数组+链表+红黑树

3.2 扩容

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。 （具体理解还需百度）

3.3 扩容过程中链表如何迁移到新的位置

如果hash值第N+1位为0，则表示不需要调整该链表节点位置；如果为1，表示需要调整到 原索引+原数组长度的位置。

3.4 为什么线程不安全

在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。 在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。

3.5 什么情况下成为一个环状

主要在这扩容的过程，当多个线程同时对这个HashMap进行put操作，而察觉到内存容量不够，需要进行扩容时，多个线程会同时执行resize操作，而这就出现问题了。首先，在HashMap扩容时，会改变链表中的元素的顺序，将元素从链表头部插入，而环形链表就在这一时刻发生。

4.CurrentHashMap

5.LRU是什么？如何实现

LRU是一种缓存淘汰机制策略。

6.平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。

7.堆是什么？如何调整

堆就是用数组实现的二叉树，堆分为两种：最大堆和最小堆，性质如下： （1）堆中某个节点的值总是不大于或不小于其父节点的值。 （2）堆总是一棵完全二叉树。

堆调整（堆的初始化）：排序之前需要将序列调整为堆（不满足时 与 左右孩子中较大的那一个进行交换） 从n/2向下取整个点开始由后向前调整直到满足堆条件为止。

（1）从堆顶取出最大元素 ，堆顶元素与堆的最后一个元素交换位置 （往后就不用考虑当前最后一个元素）。 （2）对剩余的元素进行调整 , 调整选择剩下元素中的最大元素 （根与左右孩子中较大的那个进行交换直到满足条件为止）即 对根进行堆调整。 （3）重复以上过程 直到序列有序为止 （大堆升序）。

8.口述：二叉树最近的祖先节点