算法学习第十七天：LRU缓存与布隆过滤器

LRU缓存与布隆过滤器

目录

1. LRU缓存
   • 基本概念
   • 实现原理
   • C++代码实现
2. 布隆过滤器
   • 基本概念
   • 实现原理
   • C++代码实现

LRU缓存

基本概念

• LRU（Least Recently Used）：最近最少使用策略，当缓存空间不足时，淘汰最久未被访问的数据。
• 缓存特点：快速访问、容量有限、易失性。
• 应用场景：CPU缓存、数据库查询缓存、内存管理。

实现原理

• 双向链表：维护数据的访问顺序，最近访问的节点靠近头部，最久未访问的靠近尾部。
• 哈希表：存储键到链表节点的映射，实现O(1)时间复杂度的查找。
• 操作逻辑：
  • Get：若键存在，将对应节点移到链表头部并返回值。
  • Put：若键存在，更新值并移到头部；若不存在，插入新节点。若缓存满，删除尾部节点。

C++代码实现

#include <unordered_map>
#include <list>

class LRUCache {
private:
    int capacity;
    std::list<std::pair<int, int>> cacheList;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = cacheMap.find(key);
        if (it == cacheMap.end()) return -1;
        // 将节点移到链表头部
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cacheMap.find(key);
        if (it != cacheMap.end()) {
            // 更新值并移到头部
            it->second->second = value;
            cacheList.splice(cacheList.begin(), cacheList, it->second);
            return;
        }
        // 插入新节点，若满则删除尾部
        if (cacheMap.size() == capacity) {
            int lastKey = cacheList.back().first;
            cacheMap.erase(lastKey);
            cacheList.pop_back();
        }
        cacheList.emplace_front(key, value);
        cacheMap[key] = cacheList.begin();
    }
};

布隆过滤器

基本概念

• 作用：高效判断元素是否存在于集合中，适用于允许误判的场景。
• 特点：
  • 空间效率高：使用位数组存储。
  • 查询快：O(k)时间复杂度（k为哈希函数数量）。
  • 误判率：可能存在假阳性（判断存在但实际不存在），但无假阴性。

实现原理

1. 位数组：初始化为全0，插入元素时通过多个哈希函数映射到多个位置并置1。
2. 哈希函数：选择k个独立哈希函数，减少冲突概率。
3. 查询流程：计算元素对应的k个位，若所有位均为1则判定存在，否则不存在。

C++代码实现

#include <bitset>
#include <functional>
#include <vector>

class BloomFilter {
private:
    std::bitset<1000> bits; // 位数组大小可根据需求调整
    std::vector<std::function<size_t(const std::string&)>> hashFunctions;

public:
    BloomFilter() {
        // 添加3个哈希函数示例
        hashFunctions.push_back(std::hash<std::string>());
        hashFunctions.push_back([](const std::string& s) {
            size_t hash = 0;
            for (char c : s) hash = (hash * 131) + c;
            return hash;
        });
        hashFunctions.push_back([](const std::string& s) {
            size_t hash = 0;
            for (char c : s) hash = (hash * 31) + c;
            return hash;
        });
    }

    void add(const std::string& element) {
        for (auto& hashFunc : hashFunctions) {
            size_t pos = hashFunc(element) % bits.size();
            bits.set(pos, true);
        }
    }

    bool contains(const std::string& element) {
        for (auto& hashFunc : hashFunctions) {
            size_t pos = hashFunc(element) % bits.size();
            if (!bits.test(pos)) return false;
        }
        return true;
    }
};

总结

• LRU缓存：通过双向链表维护访问顺序，哈希表加速查询，适用于需要快速访问且数据量有限的场景。
• 布隆过滤器：利用位数组和多个哈希函数高效判断元素存在性，适用于允许误判的过滤场景。
• 注意事项：LRU需处理并发安全问题；布隆过滤器需根据数据规模调整位数组大小和哈希函数数量以控制误判率。