一文吃透哈希

opencode

发布于 2022-12-26 15:45:02

3000

发布于 2022-12-26 15:45:02

文章被收录于专栏：知识同步

字符哈希算法，IP哈希算法，bloom过滤器原理

哈希结构

哈希算法的两个关键：哈希函数、冲突解决

哈希函数

哈希函数的设计有很多很多，例如常见的

取余，关键字除以某个不大于散列表表长m的数p，p<=m，p一般取小于m的第一个素数
平方取中，取关键字平方后中间几位数
直接寻址，使用某个线性函数，例如a*k+b
MD4, MD5, SHA等算法，包括后面提到的某些字符哈希的算法
…

冲突解决

经过哈希函数后，可能会有冲突，解决冲突的常见方法有

链表法，每个对应的桶拉一个链表
再哈希法，使用第二个哈希函数一直哈希到不冲突为止，或者就直接线性探测，位置不停加1，直到不冲突，或者平方探测

拉链法结构的哈希表

采用拉链法结构的哈希表如下：

字符哈希算法

有很多场景需要对字符串做哈希的，一般常见的做法：

加法hash

int additiveHash(string key, int prime) //prime是个质数
{
int hash, i;
for (hash = key.size(), i = 0; i < key.size(); i++)
hash += key[i];
return (hash % prime);
}

位运算hash，这是IP哈希用到的算法，但是和一般的有些区别，下面详细说

int rotatingHash(string key, int prime)
{
int hash, i;
for (hash = key.size(), i = 0; i < key.size(); i++)
  hash = (hash<<4)^(hash>>28)^key[i];
return (hash % prime);
}

乘法hash

int bernstein(string key)
{
int hash = 0;
int i;
for (i=0; i<key.size(); ++i) hash = 33*hash + key[i];
return hash;
}

以及其他很多改进算法FVN，MD5和SHA算法，MD5可以产生出一个128位（16字节）的散列值，SHA256对于任意长度的消息都会产生一个256bit长的哈希值

IP哈希算法

参考https://leetcode-cn.com/circle/discuss/l8fl8B/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

unsigned ipToInt(string ip) {
    int l = ip.size();
    vector<int> ipList;
    //split
    for (int i = 0; i < l; i++) {
        int j = i;
        while (j < l && ip[j] != '.') j++;
        ipList.push_back(stoi(ip.substr(i, j - i)));
        i = j;
    }
    int n = ipList.size();
    unsigned res = 0;
    for (int i = 0; i < n; i++) {
        res = res << 8 | ipList[i];
    }
    return res;
}

string intToIp(unsigned num) {
    vector<string> ipList;
    string res = "";
    for(int i = 0; i < 4; i ++) {
        string seg = to_string(num & 255);
        ipList.push_back(seg);
        num = num >> 8;
    }
    reverse(ipList.begin(), ipList.end());
    for(int i = 0; i < 4; i ++) {
        if(i == 3) res += ipList[i];
        else res += ipList[i] + '.';
    }
    return res;
}
int main()
{
    string ip;
    unsigned num;
    cin >> ip;
    cin >> num;
    cout << ipToInt(ip) << endl;
    cout << intToIp(num) << endl;
}

bloom过滤器

布隆过滤器其实底层也是哈希，底层是一个bitset，每个字符串会通过哈希函数生成k个数字，对应bitset上的k个位，如果这些位都为1，说明字符可能出现，注意，只是可能，不是一定，所以关键就在于要怎么减少冲突的可能性。

在这里有一个共识，假如k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率即错误率，他们有如下关系

应用场景

在实际工作中，布隆过滤器常见的应用场景如下：

网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
Google Chrome 使用布隆过滤器识别恶意 URL；
Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。
除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。

利用布隆过滤器我们可以预先把数据查询的主键，比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候，我们先判断该 ID 是否存在，若存在的话，则进行下一步处理。若不存在的话，直接返回，这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。