7.5 散列表 (哈希表)

7.5.1 散列表的基本概念

散列表建立了关键字和存储地址之间一种直接映射关系。

7.5.2 散列表的构造方法

1.直接定址法

适合连续分布。

2.除留余数法

除以小于等于散列表表长 m 的最大质数 p。

3.数字分析法

4.平方取中法

取关键字平方的中间几位作为散列地址。

7.5.3 处理冲突的方法

1.开放定址法

冲突就后移，可以放在表的任一地方。

  1. 线性探测法:0，1，2，3。
  2. 平方探测法：0，1，-1，4，-4，$k^2$,$-k^2$，表长必须可以表示为 4k+3 的素数。

2.拉链法

冲突就用一个链表串起来。

装填因子$\alpha =\frac{\text{表中记录数} n}{\text{散列表长度} m}$。

LeetCode001 两数之和

vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_map<int, int> q;
        for (int i = 0; i < nums.size(); i++)
        {
            auto it = q.find(target - nums[i]);
            if (it != q.end())
            {
                return {it->second, i};
            }
            q[nums[i]] = i;
        }
        return {};
    }

时间复杂度 O(1)

实现 unordered_map（哈希表）

#include <iostream>
#include <list>//双向链表

using namespace std;

template<typename K, typename V, int MAX_SIZE>
class UnorderedMap {
private:
    list<pair<K, V>> mapList[MAX_SIZE];//键 - 值对双向链表数组
    int hash(K key) {
        return key % MAX_SIZE;//类似除留余数
    }

public:
    // 添加元素
    void insert(K key, V value) {
        int index = hash(key);
        for (auto it = mapList[index].begin(); it != mapList[index].end(); it++) {
            if (it->first == key) {
                it->second = value;
                return;
            }
        }
        mapList[index].push_back({key, value});//拉链法：如果冲突，将新元素插入到双向链表尾部
    }

    // 删除元素
    void erase(K key) {
        int index = hash(key);
        for (auto it = mapList[index].begin(); it != mapList[index].end(); it++) {
            if (it->first == key) {
                mapList[index].erase(it);
                return;
            }
        }
    }

    // 查找元素
    V find(K key) {
        int index = hash(key);
        for (auto it = mapList[index].begin(); it != mapList[index].end(); it++) {
            if (it->first == key) {
                return it->second;
            }
        }
        return NULL;
    }

    // 获取元素数量
    int size() {
        int count = 0;
        for (int i = 0; i < MAX_SIZE; i++) {
            count += mapList[i].size();
        }
        return count;
    }
};

int main() {
    // 测试
    UnorderedMap<int, string, 10> map;

    map.insert(1, "one");
    map.insert(2, "two");
    map.insert(3, "three");
    map.insert(11, "eleven");
    map.insert(12, "twelve");
    map.insert(13, "thirteen");

    cout << map.find(2) << endl;
    cout << map.find(4) << endl;

    map.erase(3);

    cout << map.find(3) << endl;

}