【重难点算法题】设计哈希集合、哈希映射

文章目录

- Tag
- 题目来源
- 解题思路
- - 方法一：链地址法
- 类似题目
- - 代码1
  - 代码2
- 写在最后

Tag

【哈希集合】【哈希映射】【链地址法】【数据结构设计】

题目来源

705. 设计哈希集合

解题思路

在解题之前需要先明确两组概念：

哈希表与散列表
哈希函数与散列函数

上面的每组概念都是等同的，比如，有些资料中会将哈希表称作散列表，这两个概念是完全相同的，都是任意元素到另一个固定数值的映射。哈希表中的哈希函数对应的就是散列表中的散列函数。

为了实现哈希集合这一数据结构，有以下几个关键问题需要解决：

哈希函数：能够将集合中任意元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的的地址上。
处理冲突：由于不同的元素可能映射到相同的整数值，因此需要再整数值出现冲突时处理冲突。通常有以下几种处理方法：
- 连地址法：为每一个哈希值维护一个链表，将具有相同哈希值的元素都放入这一链表中；
- 开放地址法：当发现哈希值 h 处发生冲突时，根据某种策略，从 h 出发找到下一个不冲突的位置。例如，一种简单的策略是，不断检查 h+1，h+2，…，这些整数对应的位置，如果某一个地址没有发生冲突，则可以将元素映射到第一个没有发生冲突的地址。
- 再哈希法：当发生哈希冲突后，使用另一个哈希函数产生一个新的哈希地址。
扩容：当哈希元素过多时，冲突的概率就越来越大，有一个衡量的指标叫做填充因子， $\frac{哈希表包含的元素数}{位置总数}$ 。一个不错的经验是：当填充因子大于 0.7，就需要调整哈希表的长度，以减少冲突。

方法一：链地址法

我们设置哈希表的大小为 base，接着设计一个简单的哈希函数：hash(x) = x mod base，x 为当前需要映射的元素，hash(x) 表示对应的需要加入到哈希集合中的映射值。

我们开辟一个大小为 base 的数组，将每个 x 的映射值放入数组中，并利用「链地址法」解决哈希冲突，于是在实现中数组中的每一个位置实际放的一条链表。

由于我们使用整数除法作为哈希函数，为了尽可能避免冲突，应当将 base 取为一个质数。在这里，我们取 base=769。

代码

class MyHashSet {
private:
    vector<list<int>> data;
    static const int base = 769;
    int hash(int key) {
        return key % base;
    }
public:
    MyHashSet(): data(base) {}  // 列表初始化，初始化 data 大小为 base
    
    void add(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it) == key) {
                return;
            }
        }
        data[h].push_back(key);
    }
    
    void remove(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it) == key) {
                data[h].erase(it);
                return;
            }
        }
    }
    
    bool contains(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it) == key) {
                return true;
            }
        }
        return false;
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

复杂度分析

时间复杂度： $O(\frac{n}{b})$ 。其中 $n$ 为哈希表中的元素数量， $b$ 为链表的数量。假设哈希值是均匀分布的，则每个链表大概长度为 $\frac{n}{b}$ 。

空间复杂度： $O (n + b)$ 。

类似题目

706. 设计哈希映射

本题是设计一种哈希映射。设计思路和 设计哈希集合 思路基本一致。以下给出两个代码，代码1 是固定哈希表的大小，代码2 是根据哈希表的负载（填充）情况可以动态扩展哈希表的大小，更具一般性，建议仔细阅读并掌握。

关于哈希表的更多知识，可参考【算法与数据结构】哈希表。

代码1

class MyHashMap {
private:
    vector<list<pair<int, int>>> data;
    static const int base = 769;
    static int hash(int key) {
        return key % base;
    }
public:
    MyHashMap():data(base) {}
    
    void put(int key, int value) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it).first == key) {
                (*it).second = value;
                return;
            }
        }
        data[h].push_back(make_pair(key, value));
    }
    
    int get(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it).first == key) {
                return (*it).second;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it).first == key) {
                data[h].erase(it);
                return;
            }
        }
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

代码2

class MyHashMap {
private:
    int size;           // 键值对数量
    int capacity;       // 哈希表容量
    double loadThres;   // 负载因子阈值
    int extendRatio;    // 扩容倍数
    vector<list<pair<int, int>>> data;

    // hash 函数
    int hash(int key) {
        return key % capacity;
    }

    // 计算负载因子
    double loadFactor() {
        return double(size) / double(capacity);
    }

public:
    // 构造函数
    MyHashMap(): size(0), capacity(8), loadThres(0.7), extendRatio(2), data(capacity) {}

    // 析构函数
    ~MyHashMap() {}

    // 添加键值对
    void put(int key, int val) {
        ++size;
        if (loadFactor() > loadThres) {
            extend();
        }
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it).first == key) {
                (*it).second = val;
                return;
            }
        }
        data[h].push_back(make_pair(key, val));
    }

    // 查找
    int get(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it).first == key) {
                return (*it).second;
            }
        }
        return -1;
    }

    // 删除
    void remove(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it) {
            if ((*it).first == key) {
                data[h].erase(it);
                --size;
                return;
            }
        }
    }

    // 扩容
    void extend() {
        vector<list<pair<int, int>>> dataTmp = data;
        capacity *= extendRatio;
        data.clear();
        data.resize(capacity);
        size = 0;
        for (auto& ele : dataTmp) {
            for (auto it = ele.begin(); it != ele.end(); ++it) {
                put((*it).first, (*it).second);
            }
        }
    }
};