哈希算法基础：原理、函数与哈希表实现

输出：

Hash value of 'hash': 9

代码解释：

• simpleHash 是一个简单的哈希函数，它将字符串中的每个字符的 ASCII 值累加起来。
• 然后通过取模操作，将累加结果映射到一个固定范围（哈希表的大小）。
• 尽管简单，但这种方法容易引发哈希冲突，因为不同的输入可能映射到相同的哈希值。

哈希表实现

哈希表是一种数据结构，通过哈希函数快速定位存储值。以下是一个简单的哈希表插入和查找实现：

#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;

// 哈希表的定义
class HashTable {
private:
    vector<list<string>> table; // 使用链地址法解决冲突
    int tableSize;

    // 哈希函数
    int hashFunction(string key) {
        int hashValue = 0;
        for (char c : key) {
            hashValue += c;
        }
        return hashValue % tableSize;
    }

public:
    // 构造函数
    HashTable(int size) : tableSize(size) {
        table.resize(tableSize);
    }

    // 插入操作
    void insert(string key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }

    // 查找操作
    bool search(string key) {
        int index = hashFunction(key);
        for (string item : table[index]) {
            if (item == key) return true;
        }
        return false;
    }

    // 打印哈希表
    void display() {
        for (int i = 0; i < tableSize; i++) {
            cout << "Bucket " << i << ": ";
            for (string key : table[i]) {
                cout << key << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    HashTable hashTable(5);
    hashTable.insert("hello");
    hashTable.insert("world");
    hashTable.insert("hash");
    hashTable.insert("table");
    hashTable.display();
    cout << "Search for 'world': " << (hashTable.search("world") ? "Found" : "Not Found") << endl;
    cout << "Search for 'data': " << (hashTable.search("data") ? "Found" : "Not Found") << endl;
    return 0;
}

输出：

Bucket 0: Bucket 1: table Bucket 2: Bucket 3: hello world hash Bucket 4: Search for 'world': Found Search for 'data': Not Found

代码解释：

• 哈希函数：hashFunction 根据字符求和并取模，将键映射到一个固定范围。
• 链地址法：当两个键映射到同一个索引时，将它们存储在该桶（Bucket）中的链表中，解决哈希冲突。
• 插入操作：通过哈希函数计算键的索引，将键插入到对应桶中。
• 查找操作：定位到桶后，遍历桶内的链表查找目标键。

实际应用：LRU 缓存

哈希表结合链表可以高效实现最近最少使用（LRU）缓存。以下是一个简单实现：

#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;

// LRU 缓存类
class LRUCache {
private:
    int capacity; // 缓存容量
    list<int> keys; // 存储键的顺序
    unordered_map<int, pair<int, list<int>::iterator>> cache; // 哈希表存储键值对及其迭代器

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

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1; // 缓存未命中
        // 缓存命中：将键移到列表前
        keys.erase(cache[key].second);
        keys.push_front(key);
        cache[key].second = keys.begin();
        return cache[key].first;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) { // 键已存在，更新值并移动到前
            keys.erase(cache[key].second);
        } else if (keys.size() == capacity) { // 缓存已满，移除最近最少使用的键
            int oldKey = keys.back();
            keys.pop_back();
            cache.erase(oldKey);
        }
        keys.push_front(key);
        cache[key] = {value, keys.begin()};
    }

    void display() {
        for (int key : keys) {
            cout << key << " ";
        }
        cout << endl;
    }
};

int main() {
    LRUCache cache(3);
    cache.put(1, 10);
    cache.put(2, 20);
    cache.put(3, 30);
    cache.display(); // 输出：3 2 1
    cache.get(1);
    cache.display(); // 输出：1 3 2
    cache.put(4, 40);
    cache.display(); // 输出：4 1 3 （2 被移除）
    return 0;
}

输出：

3 2 1 1 3 2 4 1 3

代码解释：

• 哈希表与链表结合：哈希表提供 O(1) 的查找，链表维护键的使用顺序。
• 缓存命中：如果键存在，将其移动到链表头部。
• 缓存未命中：如果缓存满了，移除链表尾部的键。

改进策略：

• 使用动态扩展的哈希表（如 Python 的 dict）。
• 在分布式场景下采用一致性哈希，平衡节点数据。