一道数据结构相关的题，请教一下站里的大神们

[fxybk]

小弟本人是前端，最近被问到一道数据结构的题

实现一个 new Cache(length)来存储数据，要求实现 get(key)和 set(key,data)这两个方法，重点，要考虑性能（优先考虑 get 的性能）

小弟不才，实现的时候不知道要从哪方面去体现性能优化，请教一下各位大神

[zxCoder]

哈希表？

[oooolongtea]

可以参考 lru 或者 lfu

[fxybk]

@oooolongtea 学习了~

[Claar]

感觉就是简单的哈希表啊，本身哈希表的速度不是很快了吗？ lru 我没有写过，感觉 lru 的前提是储存空间不足被迫使用的方案，而且 lru 可能还会用到哈希表来储存(如果想要速度快的话)，题目很可能是想要你实现一个简单的好的树实现，也可能是好的哈希表实现(我没写过这个，感觉可能会难点)

[zoyua]

lru 双向哈希链表

[fxybk]

@Claar 懂了，查找跟数据储存分开考虑，查找用哈希表，储存空间问题用 lru 或者 lfu 。。感谢~

[fxybk]

@zoyua 是的。有思路了。感谢感谢

[Claar]

当然，感觉 func Cache(length)这个命名有很强的 LRU 的暗示，可能他表达的就是 LRU

[Claar]

另外我始终认为出题的人描述不正确，你可以通过指出问题的问题来表现你懂的知识哈哈哈
1.实际上如果想要无特殊的限制 /规律下以尽量快的平均速度去实现储存访问，应该是哈希表或者树的实现
2.LRU 一类的缓存置换算法，其核心应该在于 1 ）空间利用的最大化，2 ）依据思想：如果一个数据被使用，那么接下来这个数据被再次使用的几率比其他数据高。个人认为是更偏向 1 的，(主要是我没有看过 OS 上 LRU 的官方实现)。我认为如果不是为了缓存空间的利用率尽可能高，使用哈希表这类 O(log N)的算法平均应该更快一些。
所以我觉得如果他想要的答案是 LRU 的话，应该增加一些规律要求。

[fxybk]

@Claar 感谢。。。非常详细的考虑，看完真是觉得这题难为这么一个前端小弟了

[xiaoqiao24]

key 使用 hash 来生成，不管数据多少，查找效率都是 1

[Claar]

@fxybk #10
哈哈哈其实简单的判断并不难，只需要知道
1.哈希表是多数情况下 key-value 储存算法的选择，他的算法复杂度不高，效率相对来说应该是能经过考验的。另外“hash”也是指具体的“实现方式”
2.树形是常见普通人手写 key-value 算法选择，和哈希表对比可能他的速度稍稍差一点点(但是树形实现多数情况下速度也很优秀了，如果选用具体的如红黑树这种经典树形实现(红黑树算是树里面相当优秀的)，基本是很够用了)，且树形相对哈希来说可能好写一些(这只是个人认为)
3.像哈希这种优秀的算法比较大的缺点是空间占用不小，一般来说你要储存 100 个 key-value 可能需要 300 个左右的空间
4.相对来说树的具体实现，红黑树是很优秀的，但难写一些，AVL 没红黑树强，但依然优秀，且比较好写
5.树形实现速度也很快，复杂度是 O(log N)，大概就是总量为 2 ^ 20 次方的数据，每次查找差不多只需要查 20 个数据即可，而和一般的如队列从头找到尾的查找方案对比是快的没边了
6.LRU 是缓存置换算法，并不是具体的“实现”，只是一种思想形成的结构，也就是说只要满足一定的特征就能称为 LRU，但是具体实现方案的不同，效率可能差很远

在没有特殊技巧的前提下，如果侧重速度，选用哈希表 /树来储存 key-value 应该平均下来最快的了。
如果有特殊技巧，比如：最近用过的数据接下来被使用的几率更高这种规律下，如果频繁的进行查找最近用过的几个数据，那么队列的实现会快一丢丢(因为虽然有 2 ^ 20 个数据，但你查来查去只查前面几个，那当然容易啊)
而且“最近用过的数据接下来被使用的几率更高”这种规律其实只是像算力“摩尔定律”一样只是人为粗略的概括起来的一种规律，实际效果比较玄学，如果不是空间很有限的话，我认为根本没必要使用严格的 LRU 实现，直接使用自带的哈希表存下来就可以了；而使用如(链表+哈希表)来实现的 LRU 其实就是用链表来占据“最近用过的数据接下来被使用的几率更高”的优势，除了用哈希表来查找之外，链表可以加速排在前面的项的查找，并且方便把久远没用的数据丢掉来减小空间占用


综上：如果想要实现简单，直接用语言自带的哈希表走起，不过这太简单了，估计不是人家想考的，如果要实现 LRU 的话，最好是用链表+哈希表，用哈希表来找具体位置，关于规律的部分就是把最新用的数据排到最前面，每次查找完就把这个数据放到最前排就可以了