计算机基础面试八股 · 第 62 题

1. 数据结构:哈希表 Map<key, Node> + 带头尾哨兵的双向链表,链表头部是最近使用的,尾部是最久未使用的。
2. get(key):哈希表里没有就返回 -1;有就把节点从原位置摘下,插到头部,再返回值。
3. put(key, value):已存在就更新值并移到头部;不存在就新建节点插到头部并放进哈希表;如果超出容量,删除尾部前一个真实节点,同时从哈希表中删掉它的 key。
4. 为什么用双向链表:删除任意节点需要它的前驱,单链表做不到 O(1)。
5. 节点里要同时存 key,淘汰尾节点时才能从哈希表删除对应项。
6. 并发场景可以加锁或分段;Java 可直接继承 LinkedHashMap(accessOrder=true)并重写 removeEldestEntry。

能写出结构和四个操作即可,能说出节点要存 key 是加分点。