Skip to content

Latest commit

 

History

History
356 lines (265 loc) · 8.42 KB

11.hash_table.md

File metadata and controls

356 lines (265 loc) · 8.42 KB

哈希表(主要是哈希思想)与布隆过滤器

数组 key(int) <- value(any type)

这样根据下标取数的时间复杂度是$O(n)$

就是利用了数组快速存取数据的特性了

哈希表 -- 高纬(any type)到低纬(int)的映射

哈希表是设计感非常强的数据结构，冲突处理，哈希函数都没有定式！

将复杂的信息映射成简单的整形数组下标

哈希函数无论怎么设计也无法完全避免冲突

由于是高->低的映射，所以一定会存在冲突

冲突处理的方法:

  1. 开放定址(核心思想：如果发现冲突了就再往后找不冲突的)

可以用线性散列和二次散列法(当然散列法都随便取)

  1. 再哈希(设计不同的哈希函数，发现冲突了就用别的哈希函数)

一般会配合其他的方法，作为一个兜底方案

  1. 建立公共溢出区

把存在冲突的全丢进公共溢出区，可以用红黑树维护

  1. 链地址(拉链法，推荐)

$装填因子 = \frac{存储的数据}{哈希表总数} \in [0, 1)$

一般 == 0.75就要扩容了

c++实现一个二次散列法的哈希表

使用BKDR hash 和开放定址法

class HashTable {
public : 
    HashTable(int n = 100) : data(n), cnt(0) {}
    void insert(std::string s) {
        // hash对数组大小取余才是位置 
        int ind = hash(s) % data.size();
        recalc(ind, s);
        // 处理完成的ind就不会冲突了
        data[ind] = s;
        flag[ind] = 1;
        return ;
    }
    bool find(std::string s) {
        int ind = hash(s) % data.size();
        // recalc 就是找当前s在的ind
        // 找到了我们不存不就行了
        // 如果data[ind] == s
        // flag[ind] 里面就是1
        // 就是当前ind 存的是s
        recalc(ind, s);
        return flag[ind];
    }
private :
    int cnt;
    std::vector<std::string> data;
    std::bitset<100> flag;

    // BKDR hash 
    // 经典的string -> int 哈希
    int hash(std::string s) {
        const int seed = 123;
        int h = 0;
        for (auto x : s) {
            h = h * seed + x;
        }
        return h & 0x7fffffff;
    }
    void recalc(int &ind, std::string &s) {
        // flag记录ind处有没有存元素
        // 当ind处有元素 
        // 并且要存入的元素s不等于当前ind的元素
        // 才处理冲突
        // 用平方探测法
        int t = 1;
        while (flag[ind] && data[ind] != s) {
            ind += t * t;
            t += 1;
            ind %= data.size();
        }
        return ;
    }
};

int main(int argc, char **argv) {
        int op;
        std::string s;
    HashTable h;
    while (std::cin >> op >> s) {
        switch (op) {
            case 1: h.insert(s); break;
            case 2: std::cout << "find : " << s <<  " = " << h.find(s) << std::endl; break;
        }
    }
    return 0;
}
BKDR Hash
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;

    while (*str)
    {
        hash = hash * seed + (*str++);
    }

    return hash;
}

其中，seed是一个常数，可以取31、131、1313等任意正整数，hash是哈希值的初始值，初始值可以为任意值。

该算法的思路是将字符串中的每个字符视为一个权值，从左到右依次计算哈希值。在计算哈希值的过程中，不断更新哈希值，每次更新时使用一个常数seed乘以当前哈希值并加上当前字符的权值。最后得到的哈希值即为该字符串的哈希值。

扩容操作
    // 扩容操作
    void expand() {
        int n = data.size() >> 1;
        HashTable h(n);
        for (int i = 0; i < data.size(); i++) {
            if (!flag[i]) continue;
            h.insert(data[i]);
        }
        *this = h;
        return ;
    }

既然扩容操作是对每个元素处理，就相当于深拷贝了

那么它的时间复杂度会不会很高？

我们知道扩容操作是每次扩大2倍

也就是原来的元素数量最多是$\frac{n}{2}$

一直往前推 $\frac{n}{2^{n - 1}} +...+ \frac{n}{2} = n $

最多是n 对于每个元素的均摊复杂度 也就是$O(1)$

公共溢出区法

class HashTable {
public : 
    HashTable(int n = 100) : data(n), cnt(0) {}
    void insert(std::string s) {
        // hash对数组大小取余才是位置 
        int ind = hash(s) % data.size();
        recalc(ind, s);
        // 冲突的话插入缓冲区了
        if (flag[ind]) {
            buff.insert(s);
        } else {
            data[ind] = s;
            flag[ind] = 1;
            cnt += 1;
            if (cnt <= (float)data.size() * 0.75) expand();
        }
        return ;
    }
    bool find(std::string s) {
        int ind = hash(s) % data.size();
        recalc(ind, s);
        if (!flag[ind]) return false;
        if (data[ind] == s) return true;
        // 没在buff中找到
        return buff.find(s) != buff.end();
    }
private :
    int cnt;
    std::vector<std::string> data;
    std::bitset<100> flag;
    std::set<std::string> buff;

    // 扩容操作
    void expand() {
        int n = data.size() >> 1;
        HashTable h(n);
        for (int i = 0; i < data.size(); i++) {
            if (!flag[i]) continue;
            h.insert(data[i]);
        }
        // 插入buff中的元素
        for (auto x : buff) h.insert(x);
        *this = h;
        return ;
    }

    // BKDR hash 
    // 经典的string -> int 哈希
    int hash(std::string s) {
        const int seed = 123;
        int h = 0;
        for (auto x : s) {
            h = h * seed + x;
        }
        return h & 0x7fffffff;
    }
    void recalc(int &ind, std::string &s) {
        return ;
    }
};
class Node  {
public :
    Node(std::string data = "", Node *next = nullptr) : data(), next(nullptr) {}
    std::string data;
    Node *next;
    void insert(Node *node) {
        node->next = this->next;
        this->next = nullptr;
        return ;
    }


};

class HashTable {
public : 
    HashTable(int n = 100) : data(n), cnt(0) {}
    void insert(std::string s) {
        int ind = hash(s) % data.size();
        recalc(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 <= (float)data.size() * 3) expand();
        return ;
    }
    bool find(std::string s) {
        int ind = hash(s) % data.size();
        recalc(ind, s);
        Node *p = data[ind].next;
        while (p && p->data != s) p = p->next;
        return p != nullptr;
    }
private :
    int cnt;
    std::vector<Node> data;

    // 扩容操作
    void expand() {
        int n = data.size() >> 1;
        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 ;
    }

    // BKDR hash 
    // 经典的string -> int 哈希
    int hash(std::string s) {
        const int seed = 123;
        int h = 0;
        for (auto x : s) {
            h = h * seed + x;
        }
        return h & 0x7fffffff;
    }
    void recalc(int &ind, std::string &s) {
        return ;
    }
};

布隆过滤器

布隆过滤器的存储空间和元素数量无关

比如爬虫，在碰到新的url的时候怎么判断这个url爬过没爬过呢？

一个naive的方法是用哈希表做映射，每次看url是否存在哈希表中

image-20230506230727157

布隆过滤器的数据区存的是不同的哈希索引是否存储了

比如一个URL过来，经过三个哈希之后分别得到了2 7 1的值

那么就把data的127标记成1

如果url不存在呢，那么经过三个哈希之后不可能全都是1

如果再过来一个url，经过三个哈希之后对应了127的下标

只能说明它大概率存在

也就是布隆过滤器能判断哪个数据不存在，不能判断哪个数据一定存在

应用于：大数据(爬虫)

信息安全：因为布隆过滤器没存储原始的数据，不像我们之前实现的哈希表的data域都是存的原始数据

存在误判 校验为全1不一定存在 有一个不为1就肯定不存在