最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

哈希表与布隆过滤器

来源：博客园


(资料图)

一、哈希的整体思想

最简单的哈希表其实就是数组，从数组中取出一个数的时间复杂度是O(1)的。但是数组下标类型是整型的，万一我的下标类型不是整型了该怎么办呢？比如说字符串型，典型的就是我想查找某个单词存不存在。还有些更复杂的数据类型，比如自定义的类型。那么问题就来了，如何满足任意数据类型的索引需求呢？最简单直接的想法，其实就是先对任意数据类型与整型的数组下标做一个映射，往后就又回到数组取数的环节了。这种映射是一种高维空间到低维空间的映射。低维空间是有限的，而高维空间的变化情况要复杂得多。如果采用一个萝卜一个坑的思想，必然会产生重复占位，这就是哈希冲突。当我们在设计哈希表的时候一定要考虑到哈希冲突。为什么说哈希表的设计感极强，其实就在于，解决哈希冲突的方法是多种多样的。还有一个问题，哈希表装满了怎么办？有一个概念叫做装填因子（=存储元素数/哈希表size大小）一般来说，装填因子达到0.75的情况下，意味着哈希表可能要进行扩容了。

布隆过滤器

好了，说回布隆过滤器，传统哈希表有一个缺点，就是存储空间与元素数量有关，在大数据的场景下，经常需要判重操作。如果用一张哈希表存，数据量可能过于庞大。而布隆过滤器，可以实现存储空间与元素数量无关。它是通过几组不同的哈希函数，映射到不同的数组下标，然后在对应位置的数组上标记为1，默认是0，如果这些位置上的数组值一旦只要出现一个0，那么都可以直接判断出，该元素不存在，但是如果全为1，也不能说明它就一定存在哈希表中，只能说明它大概率存在。布隆过滤器经常应用于大数据和信息安全相关的场景中。

二、哈希冲突解决办法

1、开放地址法

思想：如果7的位置发生冲突了，那就试一试8，8也不行，那就试一试9，依次往后“探测”，直到找到空位。（线性探测法）注意：往后探测位置的计算规则是很灵活的，这里只是举了最简单的线性探测法。

平方探测法也有两种，可以简要看看找找区别，做题的时候格外注意，到底是哪一种：第一种：7->8->12->21->37 (a[i+1] = a[i] + i^2)第二种：7->8->11->16->23 (a[i+1] = a[0] + i^2)值得注意的是，第二种只需要判断 i 从0-Msize-1 即可，因为(key+Msize*Msize)%Msize代表搜索回到了原地，这时可以认为无法搜索到这个数字

2、再哈希法

思想：比方说可以设计三种不同的哈希函数，如果第一种冲突了，就试试第二种，第二种也冲突了就试试第三种，依次类推。注意：这种方法治标不治本，一般配合其他的哈希冲突解决方法使用。

3、建立公共溢出区

思想：另外建立一个公共溢出区，我想找的元素哈希表中找不到，就去公共溢出区再找找，其实就是用另外一种数据结构来维护，比方说红黑树。

4、链式地址法(拉链法)

思想：把哈希表的每一个坑看成链表的头节点。如果两个元素都想占用这个坑，直接在该坑上往后形成一个链表即可。

三、哈希表代码实现：

#include#includeusing namespace std;// 开放寻址法class HashTable {public:    HashTable(int n = 100) : data(n), flag(n), cnt(0) {}     void insert(string s) {        int ind = hash_func(s) % data.size(); // 计算哈希值        recalc_ind(ind, s); // 冲突处理        if (!flag[ind]) {            data[ind] = s;            flag[ind] = true;            cnt++;            if (cnt * 100 > data.size() * 75) {                expand();            }        }    }    bool find(string s) {        int ind = hash_func(s) % data.size(); // 计算哈希值        recalc_ind(ind, s); // 冲突处理        return flag[ind];    }private:    int cnt; // 记录有多少元素    vector data;    vector flag; // 记录相应位置是否存数据    void expand() {        int n = data.size() * 2;        HashTable h(n);        for (int i = 0; i < data.size(); i++) { // 看似很高的时间复杂度，其实分摊到每一个元素，扩容所造成的时间复杂度是O(1)的。            if (flag[i] == false) continue;            h.insert(data[i]);        }        *this = h;        return ;    }    int hash_func(string &s) {        int seed = 131, hash = 0;        for (int i = 0; s[i]; i++) {            hash = hash * seed + s[i];        }        return hash & 0x7fffffff; // 最高位是0，最后肯定是一个正数    }    void recalc_ind(int &ind, string s) {        int t = 1;        while (flag[ind] && data[ind] != s) {            ind += t * t;            t += 1;            ind %= data.size();        }        return ;    }};// 公共溢出区法：class HashTable {public:    HashTable(int n = 100) : flag(n), data(n), cnt(0) {}    void insert(string s) {        int ind = hash_func(s) % data.size(); // 计算哈希值        recalc_ind(ind, s); // 冲突处理        if (flag[ind] == false) {            data[ind] = s;            flag[ind] = true;            cnt += 1;            if (cnt * 100 > data.size() * 75) {                expand();            }        } else if (data[ind] != s) {            buff.insert(s);        }        return ;    }    bool find(string s) {        int ind = hash_func(s) % data.size(); // 计算哈希值        recalc_ind(ind, s); // 冲突处理        if (flag[ind] == false) return false;        if (data[ind] == s) return true;        return buff.find(s) != buff.end();    }private:    int cnt;    vector data;    vector flag;    set buff;        void expand() {        int n = data.size() * 2;        HashTable h(n);        for (int i = 0; i < data.size(); i++) {            if (flag[i] == false) continue;            h.insert(data[i]);        }        for (auto x : buff) {            h.insert(x);        }        *this = h;        return ;    }    int hash_func(string &s) {        int seed = 131, hash = 0;        for (int i = 0; s[i]; i++) {            hash = hash * seed + s[i];        }        return hash & 0x7fffffff;    }    void recalc_ind(int &ind, string &s) {        return ;    }};// 拉链法class Node {public :    Node(string data = "", Node *next = nullptr) : data(), next(nullptr) {}    string data;    Node *next;    void insert(Node *node) {        node->next = this->next;        this->next = node;        return ;    }};class HashTable {public:    HashTable(int n = 100) : data(n), cnt(0) {}    void insert(string s) {        int ind = hash_func(s) % data.size(); // 计算哈希值        recalc_ind(ind, s); // 冲突处理        Node *p = &data[ind];        while (p->next && p->next->data != s) p = p->next;        if (p->next == nullptr) {            p->insert(new Node(s));            cnt += 1;            if (cnt > data.size() * 3) expand();        }        return ;    }    bool find(string s) {        int ind = hash_func(s) % data.size(); // 计算哈希值        recalc_ind(ind, s); // 冲突处理        Node *p = data[ind].next;        while (p && p->data != s) p = p->next;        return p != nullptr;    }private:    int cnt;    vector data;        void expand() {        int n = data.size() * 2;        HashTable h(n);        for (int i = 0; i < data.size(); i++) {            Node *p = data[i].next;            while (p) {                h.insert(p->data);                p = p->next;            }        }        *this = h;        return ;    }    int hash_func(string &s) {        int seed = 131, hash = 0;        for (int i = 0; s[i]; i++) {            hash = hash * seed + s[i];        }        return hash & 0x7fffffff;    }    void recalc_ind(int &ind, string &s) {        return ;    }};int main() {    int op;    string s;    HashTable h;    while (cin >> op >> s) {        switch (op) {            case 1: h.insert(s); break;            case 2: cout << "find " << s << " : " << h.find(s) << endl; break;        }    }    return 0;}

看到这里，不妨来一道PAT的题目练练手吧，PAT题目链接：https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805343236767744题解代码：

#include#include#includeusing namespace std;#define MAX_N 20000int Msize, n, m;int a[MAX_N + 5], flag[MAX_N + 5];int cnt;bool insert(int s) {    if (cnt == Msize) return false;    for (int t = 0; t < Msize; t++) {        int ind = (s + t * t) % Msize;        if (!flag[ind]) {            a[ind] = s;            flag[ind] = 1;            cnt++;            return true;        }    }    return false;}bool is_prime(int x) {    if (x < 2) return false;    for (int i = 2, I = sqrt(x); i <= I; i++) {        if (x % i == 0) return false;    }    return true;}int main() {    // 初始化    int x;    scanf("%d%d%d",&Msize, &n, &m);    while (!is_prime(Msize)) Msize++;    // 插入部分    for (int i = 0 ; i < n; i++) {        scanf("%d", &x);        bool insert_status = insert(x);        if (!insert_status) printf("%d cannot be inserted.\n", x);    }    // 查找部分    int ans = 0;    for (int i = 0; i < m; i++) {        scanf("%d", &x);        int t;        for (t = 0; t <= Msize; t++) {            ans += 1;            int ind = (x + t * t) % Msize;            if (a[ind] == x || flag[ind] == 0) break;        }    }    printf("%.1f\n", ans * 1.0 / m);    return 0;}

关键词：