哈希算法详解

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了哈希算法详解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2084字，纯文字阅读大概需要3分钟。

内容图文

一维字符串哈希

功能：在O(1)时间内查询某个区间的子串是什么(该串的哈希值)等等

实现方法：类似于前缀合，对字符串从前到后进行哈希

void init()
{
    p[0] = 1;
    for(int i = 1; i <= len; i ++) {
        p[i] = p[i-1]*base;
    }
}

void Hash()
{
    has[0] = 0;
    for(int i = 1; i <= len; i ++) {
        has[i] = has[i-1]*base + str[i];
    }
}

查询：查询区间[l, r]内字串的哈希值，has[r] - has[l-1]*p[r-l+1]

uLL get_has(int l, int r)
{
    return has[r] - has[l-1]*p[r-l+1];
}

实现代码：（查询字符串str中s出现的次数）= kmp

const uLL base = 131;
uLL has[100010], p[100010]; //unsigned long long 自动溢出(取模)
char str[100010], s[100010];
int len;

void init()
{
    p[0] = 1;
    for(int i = 1; i <= len+5; i ++) {
        p[i] = p[i-1]*base;
    }
}

void Hash()
{
    has[0] = 0;
    for(int i = 1; i <= len; i ++) {
        has[i] = has[i-1]*base + str[i];
    }
}

uLL get_has(int l, int r)
{
    return has[r] - has[l-1]*p[r-l+1];
}

int main()
{
    init();
    scanf("%s%s", s+1, str+1);
    int len1 = strlen(s+1);
    int len2 = strlen(str+1);
    len = len2;
    Hash();
    uLL hs = 0;
    for(int i = 1; i <= len1; i ++) {
        hs = hs*base + s[i];
    }
    int cnt = 0;
    for(int i = 1; i <= len2-len1+1; i ++) {
        if(hs == get_has(i, i+len1-1)) cnt ++;
    }
    printf("%d\n", cnt);
}

二维矩阵哈希

功能：O(1)时间内查询某个子矩阵的是什么(该矩阵的哈希值)

实现方法：类似于二维前缀合，先对每一列进行哈希，然后再对每一行进行哈希

const uLL base1 = 131;
const uLL base2 = 233;

int n, m;
char mp[510][510];
uLL has[510][510];
uLL p1[510], p2[510];

void init()
{
    p1[0] = p2[0] = 1;
    for(int i = 1; i <= 505; i ++) {
        p1[i] = p1[i-1]*base1;
        p2[i] = p2[i-1]*base2;
    }
}

void Hash()
{
    has[0][0] = 0;
    has[0][1] = 0;
    has[1][0] = 0;
    for(int i = 1; i <= n; i ++) { //对列进行哈希
        for(int j = 1; j <= m; j ++) {
            has[i][j] = has[i][j-1]*base1 + mp[i][j] - 'a';
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j ++) { //对行进行哈希
            has[i][j] = has[i-1][j]*base2 + has[i][j];
        }
    }
}

查询：查询某个nn*mm的子矩阵(相同方法先处理出hs[nn][mm]的值)在原矩阵中出现了多少次

int check(int nn , int mm)
{
    int cnt = 0;
    for(int i = nn; i <= n; i ++) {
        for(int j = mm; j <= m; j ++) {
            uLL k = has[i][j] - has[i-x][j]*p2[x] - has[i][j-x]*p1[x] + has[i-x][j-x]*p1[x]*p2[x];
            if(k == hs[nn][mm]) cnt ++;
        }
    }
    return cnt;
}

 

内容总结

以上是互联网集市为您收集整理的哈希算法详解全部内容，希望文章能够帮你解决哈希算法详解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---