- 正确答案： 1. LRU缓存（Least Recently Used）是一种常用的缓存淘汰策略，其核心思想是当缓存容量满时，优先淘汰最久未使用的数据。实现上通常结合哈希表和双向链表，以实现O(1)的插入、查找和删除操作。 2. 跳表（Skip List）是一种基于概率的数据结构，用于实现有序集合的快速查找、插入和删除，平均时间复杂度为O(log n)，最坏情况下为O(n)。它是平衡树的一种替代方案，实现更简单，常用于Redis的zset等场景。 - 解答思路：面试中遇到LRU和跳表问题，应从基本原理出发，理解其设计动机、数据结构选择、关键操作流程，并能手写核心代码。对于LRU，重点在于如何用哈希表+双向链表维护访问顺序；对于跳表，重点在于多层链表的随机提升机制和查找路径的构造。 --- ### 第一题：LRU缓存实现 - 正确答案：使用哈希表（unordered_map）存储键到节点的映射，配合一个双向链表维护访问顺序。每次访问或插入时，将对应节点移动到链表头部（表示最近使用），当缓存满时，删除链表尾部节点（最久未使用）。 - 解答思路： 1. 定义双向链表节点结构，包含key、value、prev、next指针。 2. 维护头尾哨兵节点（dummy head 和 dummy tail），简化边界处理。 3. 哈希表用于O(1)定位节点位置。 4. get操作：查哈希表，存在则从链表中移除并插入头部，返回value；否则返回-1。 5. put操作：若已存在，更新值并移到头部；若不存在且容量满，则删除尾部节点，插入新节点到头部。 - 深度知识讲解： - 为什么用双向链表？因为需要O(1)删除任意节点，单向链表无法在不知道前驱的情况下删除节点。 - 为什么不用单向链表+前驱数组？空间开销大且不通用。 - 为什么不用栈？栈只能在顶端操作，无法随机删除中间元素。 - 为什么不用优先队列？无法O(1)更新某个元素的访问时间。 - 哈希表+双向链表是经典组合，体现了“用空间换时间”的思想。 - STL中list是双向链表，但不支持O(1)查找，所以仍需哈希表辅助。 - 代码示例（C++）： ``` class LRUCache { private: struct Node { int key, value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; int capacity; unordered_map cache; Node* head; // dummy head Node* tail; // dummy tail void removeNode(Node* node) { node->prev->next = node->next; node->next->prev = node->prev; } void addToHead(Node* node) { node->next = head->next; node->prev = head; head->next->prev = node; head->next = node; } void moveToHead(Node* node) { removeNode(node); addToHead(node); } Node* removeTail() { Node* last = tail->prev; removeNode(last); return last; } public: LRUCache(int cap) { capacity = cap; head = new Node(0, 0); tail = new Node(0, 0); head->next = tail; tail->prev = head; } int get(int key) { if (cache.find(key) == cache.end()) { return -1; } Node* node = cache[key]; moveToHead(node); return node->value; } void put(int key, int value) { if (cache.find(key) != cache.end()) { Node* node = cache[key]; node->value = value; moveToHead(node); } else { Node* newNode = new Node(key, value); cache[key] = newNode; addToHead(newNode); if (cache.size() > capacity) { Node* removed = removeTail(); cache.erase(removed->key); delete removed; } } } }; ``` --- ### 第二题：跳表（Skip List）实现 - 正确答案：跳表是一种基于多层有序链表的概率型数据结构。每一层都是下一层的“快速通道”，高层跳过更多元素。插入时通过随机函数决定节点层数，查找从最高层开始逐层下降，最终在底层找到目标。 - 解答思路： 1. 定义跳表节点结构，包含value、一个指针数组forward，用于指向每一层的下一个节点。 2. 维护最大层数（maxLevel）和当前层数（curLevel）。 3. 查找：从最高层开始，向右走直到下一个节点大于目标，则下移一层，重复直到找到或失败。 4. 插入：先查找路径，记录每层最后一个小于目标的节点（update数组），然后生成随机层数，创建新节点并插入各层。 5. 删除：查找节点，若存在则从所有层中移除。 - 深度知识讲解： - 跳表的本质是空间换时间，通过多层索引加速查找，类似于二分查找的思想，但在链表上实现。 - 随机层数生成：通常使用抛硬币方式（rand() % 2 == 0）决定是否提升，直到失败或达到最大层数。期望层数为log n。 - 时间复杂度分析： - 查找：平均每层跳过一定数量元素，期望比较次数为O(log n)。 - 插入/删除：同样O(log n)，因为需要更新路径上的指针。 - 空间复杂度：O(n)，因为每个节点平均有2个指针（几何级数期望为2）。 - 与平衡树对比：跳表实现更简单，支持范围查询高效，且易于并发（如Redis使用跳表而非红黑树）。 - 为什么Redis用跳表？因为跳表支持O(log n)的按分数查找、范围查询、插入删除，且代码简洁，适合zset场景。 - 伪代码示例（跳表核心操作）： ``` const int MAX_LEVEL = 16; const double P = 0.5; struct Node { int value; Node** forward; // 指针数组，forward[i]表示第i层的下一个节点 Node(int v, int level) { value = v; forward = new Node*[level]; for (int i = 0; i < level; i++) { forward[i] = nullptr; } } }; class SkipList { private: Node* head; int curLevel; int randomLevel() { int level = 1; while (rand() % 100 < P * 100 && level < MAX_LEVEL) { level++; } return level; } public: SkipList() { curLevel = 1; head = new Node(-1, MAX_LEVEL); // 哨兵节点 } bool search(int target) { Node* curr = head; for (int i = curLevel - 1; i >= 0; i--) { while (curr->forward[i] != nullptr && curr->forward[i]->value < target) { curr = curr->forward[i]; } } curr = curr->forward[0]; return curr != nullptr && curr->value == target; } void add(int num) { Node* update[MAX_LEVEL]; // 记录每层最后一个小于num的节点 Node* curr = head; for (int i = curLevel - 1; i >= 0; i--) { while (curr->forward[i] != nullptr && curr->forward[i]->value < num) { curr = curr->forward[i]; } update[i] = curr; } curr = curr->forward[0]; if (curr == nullptr || curr->value != num) { int newLevel = randomLevel(); if (newLevel > curLevel) { for (int i = curLevel; i < newLevel; i++) { update[i] = head; } curLevel = newLevel; } Node* newNode = new Node(num, newLevel); for (int i = 0; i < newLevel; i++) { newNode->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newNode; } } } bool erase(int num) { Node* update[MAX_LEVEL]; Node* curr = head; for (int i = curLevel - 1; i >= 0; i--) { while (curr->forward[i] != nullptr && curr->forward[i]->value < num) { curr = curr->forward[i]; } update[i] = curr; } curr = curr->forward[0]; if (curr == nullptr || curr->value != num) { return false; } for (int i = 0; i < curLevel; i++) { if (update[i]->forward[i] != curr) break; update[i]->forward[i] = curr->forward[i]; } delete curr; while (curLevel > 1 && head->forward[curLevel - 1] == nullptr) { curLevel--; } return true; } }; ``` - 扩展知识： - LRU在操作系统页面置换、数据库缓冲池、浏览器缓存中广泛应用。 - 跳表可用于实现有序集合、区间查询、排名系统等。 - 实际工程中，C++ STL没有提供跳表，但可以自己实现或使用第三方库。 - LRU也可以用std::list + std::unordered_map实现，利用list的splice操作移动节点。 - 进阶变种：LFU（Least Frequently Used）使用频率作为淘汰依据，需维护频次桶。 - 面试建议：在白板上写代码时，先说明整体结构，再分模块实现。注意边界条件（如空链表、重复插入、删除不存在元素），并主动测试几个用例。

字节一面（抖音电商 8.26）

全站热榜

创作者周榜