更新1：按照此思路实现的简单版本

又是面试总结时间

这次面试的是一个初创公司的职位，其中一道题是不可能现场能够给出正确答案的，这里我的思考用时为六个小时。

原命题是：

如何设计一个LRUCache的System。能在接近O(1)时间内完成操作

那么以前两次提到的如何问问题，我们先确定使用场景，这是一个K-V键值系统，其中K-V值很小，但是延时要求高。

我们要求是在普通的服务器环境中构建一个尽可能低延时的LRUCache系统。

第一点是：确定数据结构

因为要以O(1)时间做查询，那么Map结构是跑不掉的，那么我们知道Map从语义上来说不一定是有序的。为了达到有序一定会有个辅助数据结构，这个结构一定是有序的。这是在我脑子里面第一个是小堆。小堆的维持堆结构操作最坏是nlogn，那么在频繁的写时候，并不能满足O(1)的需求，放弃掉；

第二个出现在我脑海中的数据结构是树，同样维持树结构仍不能满足需求；

第三个是我已经离开了面试地点想到的，跳表

这不是一般意义上的跳表，我们按照时间先后使得跳表的查询能够想hash操作一样是计算出来的，此时的hash函数一定是个递增阶梯函数

自然而然的引出了我认为最正确的答案，则是对数据集进行划分。

第二点是：具体怎么做

首先我们按照内存大小进行划分，按照面试官的提示，内存为8GB左右，我们估算一个k-v键值对大约占用100bytes，那么最差会有8.6kw个键值对，我们知道CPU的一二三级缓存速度非常快，即使是遍历也会极快，我们假设CPU的三级缓存有16MB，则我们对数据块的划分为16MB一个那么我们就拥有了512个块，我们可以近似认为在其中遍历只需要O(1)的时间，假设我们拥有一个足够均匀的hash函数能够使得key平均的分布在者512个块，那么我们查询的时间为O(1)+O(k)；k为块的大小远小于整体数据量，此时删除和查询一个或者插入一个元素，近似时间都在O(1)完成。

第三点是：一些其他问题

第一点是，我们的hash有可能不能使得key均匀分布

第二点是，假设服务器还部署了其他应用，那么还要能对空闲的块进行回收合并

总结是：

大部分这种面试题如果当场做不出，也很难当场做出的，要多和面试官探讨