两个高频设计类面试题：如何设计 HashMap 和线程池

你好，我是 yes。

最近在汇总面试题，但是我写的这个版本不是背诵版，不是那种死记硬背刻板的答案。

我的本意是抛砖引玉，针对每个题目给出我自己的理解和解释型的答案，然后背诵版本需要你们自行去总结和记忆。

因为八股文在面试中是一定要的，也就是该知道的题还是得知道的，而在理解的基础上记忆会比较深刻，并且可以应对一些变种问题。

但是不清楚这样的形式是不是受欢迎，所以我暂时拿两个题目先发出来看看反响。

所以如果觉得这样的形式哪里不好，需要改进的话，请留言。

1.如果让你设计一个 HashMap 如何设计？

这个问题我觉得可以从 HashMap 的一些关键点入手，例如 hash 函数、如何处理冲突、如何扩容。

可以先说下你对 HashMap 的理解。

比如：HashMap 无非就是一个存储 <key,value> 格式的集合，使得通过 key 在 O(1) 的时间复杂下就能查找到 value。

基本原理就是将 key 经过 hash 函数进行散列得到散列值，然后通过散列值对数组取模得到对应的 index 。

所以 hash 函数很关键，不仅运算要快，还需要分布均匀，减少 hash 碰撞。

而因为输入值是无限的，而数组的大小是有限的所以肯定会有碰撞，因此可以采用拉链法来处理冲突。

为了避免恶意的 hash 攻击，当拉链超过一定长度之后可以转为红黑树结构。

当然超过一定的结点还是需要扩容的，不然碰撞就太严重了。

而普通的扩容会导致某次 put 延时较大，特别是 HashMap 存储的数据比较多的时候，所以可以考虑和 redis 那样搞两个 table 延迟移动，一次可以只移动一部分。

不过这样内存比较吃紧，所以也是看场景来 trade off 了。

还有，最好使用之前预估准数据大小，避免频繁的扩容。

基本上这样答下来差不多了，HashMap 几个关键要素都包含了，接下来就看面试官怎么问了。

可能会延伸到线程安全之类的问题，反正就照着 currentHashMap 的设计答。

其实有些题目看起来是问如何设计，实际上你就答你对这个东西是怎么理解的，把它原理和一些要点讲一讲这个题目就过了。

比如我上面说的预估准数据的大小，这种看起来和设计没关系，但是可以让面试官知道你对这种方面是敏感的就够了。

所以有时候的“答非所问”是 OK 的，如果面试官觉得你答的方向不对，自然而然会提醒你，到时候你再接招就好了。

简单地说，很多提问不是真的要死板的对着面试题而回答，因为面试官也只是笼统地问。

2.如果让你设计一个线程池如何设计？

这种设计类问题还是一样，先说下理解，表明你是知道这个东西的用处和原理的，然后开始 BB。基本上就是按照现有的设计来说，再添加一些个人见解。

线程池讲白了就是存储线程的一个容器，池内保存之前建立过的线程来重复执行任务，减少创建和销毁线程的开销，提高任务的响应速度，并便于线程的管理。

我个人觉得如果要设计一个线程池的话得考虑池内工作线程的管理、任务编排执行、线程池超负荷处理方案、监控等方面。

要将初始化线程数、核心线程数、最大线程池都暴露出来可配置，包括超过核心线程数的线程空闲消亡相关配置。

然后任务的存储结构也得可配置，可以是无界队列也可以是有界队列，也可以根据配置，分多个队列来分配不同优先级的任务，也可以采用 stealing 的机制来提高线程的利用率。

再提供配置来表明此线程池是 IO 密集型还是 CPU 密集型来改变任务的执行策略。

超负荷的方案可以有多种，包括丢弃任务、拒绝任务并抛出异常、丢弃最旧的任务或自定义等等。

至于监控的话，线程池设计要埋好点，暴露出用于监控的接口，如已处理任务数、待处理任务数、正在运行的线程数、拒绝的任务数等等信息。

我觉得基本上这样答就差不多了，等着面试官的追问就好。

注意不需要跟面试官解释什么叫核心线程数之类的，都懂的没必要。

当然这种开放型问题还是仁者见仁智者见智，我这个不是标准答案，仅供参考。

建议把线程池相关的关键字都要说出来，表面你对线程池的内部原理的理解是透彻的。

最后

近期应该有很多人在准备面试了，跳槽 time is up。

我也在加紧写面试题解，今天暂时就拿出这两个设计类题目来看看反响。

如果有什么建议留言哈。

也欢迎关注我的个人公众号，之后继续产出面试题：

更多文章可看我的文章汇总：https://github.com/yessimida/yes 欢迎 star !

我是 yes，从一点点到亿点点，欢迎在看、转发、留言，我们下篇见。