L7_05 哈希表

一、哈希表的概念

1.1 哈希表定义

哈希表（Hash Table）是一种通过哈希函数将键映射到数组位置来存储数据的数据结构。

1.2 哈希表的特点

• 平均 O(1) 时间复杂度：插入、删除、查找操作
• 空间换时间：需要额外的存储空间
• 可能发生哈希冲突：需要处理冲突的策略

1.3 哈希函数

// 简单的整数哈希函数
int hashInt(int key, int tableSize) {
    return key % tableSize;
}

// 字符串哈希函数（BKDRHash）
unsigned int hashString(const string& str) {
    unsigned int seed = 131;
    unsigned int hash = 0;
    for (char c : str) {
        hash = hash * seed + c;
    }
    return hash;
}

二、哈希冲突处理

2.1 开放地址法

template <typename K, typename V>
class HashTableOpenAddressing {
private:
    vector<pair<K, V>> table;
    vector<bool> deleted;
    int size;
    int capacity;
    
    int hash(const K& key) const {
        return hash<K>()(key) % capacity;
    }
    
    int probe(int index, int i) const {
        return (index + i) % capacity; // 线性探测
    }
    
public:
    HashTableOpenAddressing(int cap = 16) : capacity(cap), size(0) {
        table.resize(capacity);
        deleted.resize(capacity, false);
    }
    
    void insert(const K& key, const V& value) {
        if (size >= capacity * 0.7) {
            // 扩容
            capacity *= 2;
            vector<pair<K, V>> oldTable = table;
            vector<bool> oldDeleted = deleted;
            table.resize(capacity);
            deleted.resize(capacity, false);
            size = 0;
            
            for (int i = 0; i < oldTable.size(); i++) {
                if (!oldDeleted[i]) {
                    insert(oldTable[i].first, oldTable[i].second);
                }
            }
        }
        
        int index = hash(key);
        for (int i = 0; i < capacity; i++) {
            int pos = probe(index, i);
            if (deleted[pos] || table[pos].first == key || table[pos].first == K()) {
                table[pos] = {key, value};
                deleted[pos] = false;
                size++;
                return;
            }
        }
    }
    
    bool find(const K& key, V& value) const {
        int index = hash(key);
        for (int i = 0; i < capacity; i++) {
            int pos = probe(index, i);
            if (table[pos].first == key && !deleted[pos]) {
                value = table[pos].second;
                return true;
            }
            if (table[pos].first == K() && !deleted[pos]) {
                return false;
            }
        }
        return false;
    }
    
    bool remove(const K& key) {
        int index = hash(key);
        for (int i = 0; i < capacity; i++) {
            int pos = probe(index, i);
            if (table[pos].first == key && !deleted[pos]) {
                deleted[pos] = true;
                size--;
                return true;
            }
            if (table[pos].first == K() && !deleted[pos]) {
                return false;
            }
        }
        return false;
    }
};

2.2 链地址法

template <typename K, typename V>
class HashTableChaining {
private:
    struct Node {
        K key;
        V value;
        Node* next;
        Node(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
    };
    
    vector<Node*> table;
    int size;
    int capacity;
    
    int hash(const K& key) const {
        return hash<K>()(key) % capacity;
    }
    
    void resize() {
        capacity *= 2;
        vector<Node*> newTable(capacity, nullptr);
        
        for (int i = 0; i < capacity / 2; i++) {
            Node* curr = table[i];
            while (curr) {
                Node* next = curr->next;
                int index = hash(curr->key);
                curr->next = newTable[index];
                newTable[index] = curr;
                curr = next;
            }
            table[i] = nullptr;
        }
        table.swap(newTable);
    }
    
public:
    HashTableChaining(int cap = 16) : capacity(cap), size(0) {
        table.resize(capacity, nullptr);
    }
    
    ~HashTableChaining() {
        for (int i = 0; i < capacity; i++) {
            Node* curr = table[i];
            while (curr) {
                Node* next = curr->next;
                delete curr;
                curr = next;
            }
        }
    }
    
    void insert(const K& key, const V& value) {
        if (size >= capacity * 0.7) {
            resize();
        }
        
        int index = hash(key);
        Node* curr = table[index];
        
        // 更新已存在的键
        while (curr) {
            if (curr->key == key) {
                curr->value = value;
                return;
            }
            curr = curr->next;
        }
        
        // 插入新节点
        Node* newNode = new Node(key, value);
        newNode->next = table[index];
        table[index] = newNode;
        size++;
    }
    
    bool find(const K& key, V& value) const {
        int index = hash(key);
        Node* curr = table[index];
        
        while (curr) {
            if (curr->key == key) {
                value = curr->value;
                return true;
            }
            curr = curr->next;
        }
        return false;
    }
    
    bool remove(const K& key) {
        int index = hash(key);
        Node* curr = table[index];
        Node* prev = nullptr;
        
        while (curr) {
            if (curr->key == key) {
                if (prev) {
                    prev->next = curr->next;
                } else {
                    table[index] = curr->next;
                }
                delete curr;
                size--;
                return true;
            }
            prev = curr;
            curr = curr->next;
        }
        return false;
    }
};

三、C++ STL 中的哈希表

3.1 unordered_map

#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> map;
    
    // 插入
    map["apple"] = 10;
    map["banana"] = 5;
    map.insert({"orange", 8});
    
    // 查找
    if (map.find("apple") != map.end()) {
        std::cout << "apple: " << map["apple"] << std::endl;
    }
    
    // 遍历
    for (const auto& pair : map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 删除
    map.erase("banana");
    
    // 大小
    std::cout << "Size: " << map.size() << std::endl;
    
    return 0;
}

3.2 unordered_set

#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> set;
    
    // 插入
    set.insert("apple");
    set.insert("banana");
    set.insert("orange");
    
    // 查找
    if (set.count("apple")) {
        std::cout << "apple exists" << std::endl;
    }
    
    // 删除
    set.erase("banana");
    
    // 遍历
    for (const std::string& item : set) {
        std::cout << item << std::endl;
    }
    
    return 0;
}

3.3 自定义哈希函数

#include <unordered_map>
#include <tuple>

struct PairHash {
    template <typename T1, typename T2>
    size_t operator()(const std::pair<T1, T2>& p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ (h2 << 1);
    }
};

int main() {
    std::unordered_map<std::pair<int, int>, std::string, PairHash> map;
    map[{1, 2}] = "point";
    return 0;
}

四、哈希表的应用

4.1 两数之和

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.count(complement)) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

4.2 字母异位词分组

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> map;
    
    for (string str : strs) {
        string key = str;
        sort(key.begin(), key.end());
        map[key].push_back(str);
    }
    
    vector<vector<string>> result;
    for (auto& pair : map) {
        result.push_back(pair.second);
    }
    return result;
}

4.3 最长连续序列

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> set(nums.begin(), nums.end());
    int longest = 0;
    
    for (int num : nums) {
        if (!set.count(num - 1)) {
            int current = num;
            int length = 1;
            
            while (set.count(current + 1)) {
                current++;
                length++;
            }
            
            longest = max(longest, length);
        }
    }
    return longest;
}

五、哈希表的性能分析

5.1 时间复杂度

操作	平均情况	最坏情况
插入	O(1)	O(n)
删除	O(1)	O(n)
查找	O(1)	O(n)

5.2 空间复杂度

• O(n)，需要存储所有元素

5.3 负载因子

• 负载因子 = 元素数量 / 表容量
• 通常负载因子阈值设为 0.7，超过时需要扩容

5.4 哈希表 vs 有序容器

特性	哈希表	有序容器
查找	O(1)	O(log n)
有序性	无序	有序
内存占用	较高	较低
迭代顺序	不确定	有序