阿里面试官用HashMap把我问倒了

2024-03-09 15:09:11

本人是一名大三学生，最近在找暑期实习，其中也面试过两次阿里，一次菜鸟网络部门、一次网商银行部门，当然我都失败了，同时也让我印象很深刻，因此记录了其中一些面试心得，我觉得这个问题很值得分享，因此分享给大家，同时我在B站也录制了相应的视频，地址：https://www.bilibili.com/video/BV1ZA411G7uc

你能说一下HashMap的实现原理吗？

对于这个问题，我当时觉得这个问题太小菜一碟了，于是照着自己之前准备的开始巴拉巴拉介绍HashMap，当我说到哈希冲突时，面试官打断了我，问我，你知道HashMap如何解决哈希冲突的吗？这个我想都没想直接说链地址法，于是面试官又继续问，那你还知道有哪些解决Hash冲突的方法，我当时整好记得一个开放寻址法，于是面试官又继续问

你能说一下开放寻址法的原理吗？

到这里我已经有点懵了，我就照着字面意思解释了一番，标准解答如下：当哈希碰撞发生时，从发生碰撞的那个单元起，按照一定的次序，从哈希表中寻找一个空闲的单元，然后把发生冲突的元素存入到该单元。

于是面试官又问，如果用开放寻址法实现HashMap，能删除节点吗？此时我已语塞，因为我知道不管是回答能还是不能，他下一句肯定是为什么能或者为什么不能

面试关看我这里不会，于是换了个方向，接着问

你知道开放寻址法有哪些地方用到，或者说有哪些应用？

整好，我学过ThreadLocal，并当时了解过ThreadLocal的底层是使用ThreadLocalMap实现的，而ThreadLocalMap 的底层解决哈希冲突的方式正是开放寻址法，于是我将这些说了出来，于是面试官接着问

说说你对ThreadLocal的理解

于是我照着自己的理解介绍了一下ThreadLocal，面试官接着问，ThreadLocal有哪些应用，我答在与数据库进行交互的时候，需要保证数据库连接的一致性，此时就用到了ThreadLocal保证同一个事物中对数据库的操作是用的同一个数据库连接（其实当时我只想的到这个了），于是面试官接着问

ThreadLocal存在哪些问题

学过ThreadLocal 的人应该都知道，ThreadLocal其实是存在内存泄漏的问题，一个是key的内存泄漏，一个是value的内存泄漏，面试官接着问，那你说说ThreadLocal是如何解决这些问题的，我答：

对于key 的内存泄漏：ThreadLocalMap 的key实际上是一个弱引用，当ThreaLocal对象为null时，这个key就会被回收，就不会造成内存泄漏
对于value的内存泄漏：每次使用完ThreadLocal中存的变量都要记得remove，这样就不会造成value 的内存泄漏

于是面试关接着问，既然key采用了弱引用的方式解决内存泄漏，那为什么value不也用弱引用的方式解决内存泄漏，我当时其实都不知道该怎么答了，我照着自己的理解说：对于value的内存泄漏，之所以没有采用弱引用的方式，是因为不清楚这个Value除了map的引用还是否还存在其他引用，如果不存在其他引用，当GC的时候就会直接将这个value干掉了，而此时我们的ThreadLocal还处于使用期间，就会造成Value为null的错误

但是面试官仍然没有打算放过我，然后接着问，为什么弱引用就能解决内存泄漏问题，其实我觉得当时他的意思是

把Java 的引用数据类型给介绍一下？

我答：Java有强引用、软引用、弱引用、虚引用。我分别按照自己的理解将这些引用介绍了一下，于是面试官逮这虚引用跟我聊起来了，他说

虚引用有什么用

其实我在Java引用数据类型还有一些了解，所以就介绍了下虚引用，于是面试官说那平常有哪些场景会用到，我说常见的就是NIO通信的时候，因为我之前做过一个项目与硬件数据上传有关，当时我的服务端就用的NIO，我接着说，比如网卡传来数据，会先将该数据拷贝到操作系统内存中，如果JVM要用这部分数据，则会再从操作系统的内存中将这部分数据拷贝到JVM内存中，这样的过程就进行了多次拷贝，且耗时间，因此allocateDirect这样少一次拷贝的效率会很高，这样的操作也被称为零拷贝，NIO底层就用到了零拷贝的原理。在这种零拷贝的情况下，虚引用就诞生了，虚引用通常指向操作系统内存空间的数据，当虚引用要被回收时，就会把该虚引用放到事件队列里，GC也会时不时检查队列，会检查队列里的虚引用所指向的内存需不需要被回收，如果需要就直接将其回收，同时将改虚引用出队，这样就实现了虚引用监控的作用，实现了通过虚引用清除OS空间里的内存

面试官看我说到了NIO，于是就着NIO开始问我

为什么当时项目用NIO不用IO

其实这个地方我还是能答的，因为我当时项目最开始的确是使用的IO方式接收数据，之后才改成的NIO，于是我回答因为IO底层采用的多路复用机制，效率会比IO高很多，于是面试官接着问

说一说IO多路复用机制是怎样的

其实到这里我已经感觉到呼吸困难了，我照着自己的理解介绍了IO多路复用机制（当时感觉介绍的很通俗，不够专业）

于是面试官接着问

那你介绍下select、poll、epoll

select

select（阻塞函数）其实就是将对FD（标志位）数据的集合判断从原来的用户态到交给内核态管理（将Rset从用户态拷贝到了内核态），内核态会快很多，如果判断有数据

将FD置位，表示此时有数据来了
将select返回，不再阻塞

之后判断那一个FD被置位了，于是就行取数据处理

select使用的1024的bitmap存数据

缺点：

fd_size有限制1024bitmap
FDset不可重用
用户态到内核态的拷贝开销
O（n）再次遍历

poll

poll（阻塞函数），工作原理与select很相似，但是poll没有采用bitmap，采用的pollfd存储（基于结构体存储fd）

struct pollfd {
    int fd;
    short events;
    short revents;
}

有数据：

pollfd.revents置位
poll返回，不再阻塞

执行之后的操作，执行之后再将pollfd.revents设置为0

缺点：

用户态到内核态的拷贝开销
O（n）再次遍历

epoll

epoll，最新的一种IO多路复用的函数，用户态和内核态共享epfd数组，内核用于判断哪个fd有数据到来，不需要用户态到内核态的拷贝，不需要轮询，时间负责度O（1）