精华内容
下载资源
问答
  • 字符串hash用法

    2020-07-22 21:23:37
    我们大量的单词进行对比比较,看哪些单词是重复出现过的,我们首先要将单词转换成ascii码,然后再比较他们的ascii码是否相等,这样会不会太浪费空间和时间,我们不妨先计算出这个单词的hash,然后再保存在内存里,...

    什么是字符串哈希

    其实字符串hash和我们平时在代码中使用的hash都是一样的,原理都是将字符串通过一系列算法,将他映射成一个N进制,并且我们要保证不同的字符串得到的N进制一定是不同的。

    为什么要有字符串hash这个东西?试想一下,我们对大量的单词进行对比比较,看哪些单词是重复出现过的,我们首先要将单词转换成ascii码,然后再比较他们的ascii码是否相等,这样会不会太浪费空间和时间,我们不妨先计算出这个单词的hash,然后再保存在内存里,这样我们比较两个单词,直接比较他们的字符串hash即可。至于如何计算字符串hash,其实就跟我们计算二进制,八进制一样,只是有一点细节上的区别。

    如何计算

    假设我们有abcabb两个字符串,假设1=a,2=b,3=c…,英文字母有26个,我们其实可以设置26进制即可,但这样容易出现hash碰撞,所以我们设置大一点,随便一个数字就好,就36进制吧。

    通过进制计算,我们得出:

    hash(abc) = 1371

    hash(abb) = 1370

    由于在计算较长的字符串时,我们知道int最大可以保存2^31-1,如果字符串过长的话,肯定会出现溢出的情况,这个时候我们就要对结果取模,一般这儿设置一个较大的质数用来取模即可,我这里用的是1e+9 + 7这个数来进行取模,同时这个数刚好在int范围内。

    所以我们可以得出一个计算字符串hash的公式。

    其中 h 为返回值,初始为 0,p为所代表的进制,Si代表当前字符串第i个字符。

    衡量hash的一个指标就是看hash碰撞率,如果某字符串越长越复杂,那计算出来的hash值进行取模后,可能会与其他字符串的hash值发生碰撞。

    这个问题是不可避免的,你可以增大基数p或者增大模来降低hash碰撞,也可以采用其他的hash策略来计算hash。

    总而言之,在平时刷题中,题目是不会出这种数据给你的,如果有,改变一下模的值就行了。

    代码

    我的cpp代码如下:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    unsigned int MOD = 1e+9 + 7;
    
    int getH(string s) {
        unsigned int h = 0;
        int n = s.size();
        int p = 36;         // 36进制
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a' + 1;
            h = (h * p) % MOD + c;
        }
        return h;
    }
    
    
    int main() {
        cout << getH("abb") << endl;
        cout << getH("abc");
        return 0;
    }
    
    展开全文
  • 该算法通过计算每个固定长度的字串,然后通过滚动hash依次每个子串的hash值与匹配串进行比较,如果相同就打印子串所在的位置。由于使用的是hash值,可能产生hash冲突,可以在hash值相同以后在进行逐个字符匹配。 ...

    该算法通过计算每个固定长度的字串,然后通过滚动hash依次对每个子串的hash值与匹配串进行比较,如果相同就打印子串所在的位置。由于使用的是hash值,可能产生hash冲突,可以在hash值相同以后在进行逐个字符匹配。

    public class PabinKarp {
        public static void main(String[] args) {
            String s = "ABABABA";
            String p = "ABA";
            //方法开始
            match(p,s);
        }
    
        private static void match(String p, String s) {
        //计算匹配串的hash值
           long hash_p = hash(p);
           //计算第一个字串的hash值,并存入数组当中
            long [] hashOfS = hash(s,p.length());
            match(hash_p,hashOfS);
        }
    	
        private static void match(long hash_p, long[] hash_s) {
        //逐个对hash值进行比较,如果相同则打印第一个字符的位置
            for (int i = 0; i < hash_s.length; i++) {
            //这里可能会产生hash冲突,会导致匹配串和子串的值不一样,如需改进,可以在这进行再次字串的匹配
                if (hash_s[i] == hash_p) {
                    System.out.println("match:"+i);
                }
            }
        }
    
    	
        static int seed = 31;
        static long hash(String str) {
            long hash = 0;
            for (int i = 0; i != str.length(); i++) {
                hash = seed * hash +  str.charAt(i);
            }
            return hash%Long.MAX_VALUE;
        }
    	//滚动hash的核心方法
        static long[] hash(final String s,final int n) {
            long[] res = new long[s.length() - n +1];
            res[0] = hash(s.substring(0,n));
            for (int i = n; i < s.length() ; i++) {
                char newChar = s.charAt(i);
                char oldChar = s.charAt(i - n);
    			//将字符串转成31进制的hash值,进行滚动hash,可能导致结果很大
    			//所以进行取模,例如如果我们字符串为1234,分成两个字串123和234,逐个进行hash,就会得到123的hash值:
    			//1*31^2+2*31^+3*31^0=1026,如果我们要得到234的hash值,我们不用再次逐个进行hash我们只需要:
    			//(1*31^2+2*31^+3*31^0)*31-1*31^3+4
    			// = (1*31^3+2*31^2+3^31^1)-1*31^3+4
    			// =2*31^2+3^31^1+4*31^0
    			
                long v = (long)(res[i -n] * seed - Math.pow(seed,n) * oldChar + newChar)%Long.MAX_VALUE;
                res[i-n+1] = v;
            }
            return res;
        }
    
    }
    
    展开全文
  • 百度,google了很多关于这个函数的用法。...(别人的分析:它对于长字符串和短字符串都很有效,字符串中每个字符都有同样的作用,它巧妙地对字符的ASCII编码值进行计算,ELFhash函数对于能够比较均匀地...

         百度,google了很多关于这个函数的用法。都大同小异,都只是给出了代码,我觉得对我这个初学者来说有点难理解。所以,在这,我综合一下我搜到的知识,把它再加深下印象吧。

        ELFhash函数关键是要取得字符串对应的hash值。(别人的分析:它对于长字符串和短字符串都很有效,字符串中每个字符都有同样的作用,它巧妙地对字符的ASCII编码值进行计算,ELFhash函数对于能够比较均匀地把字符串分布在散列表中。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。)

        ELFhash():参考http://blog.chinaunix.net/uid-24683784-id-3061386.html

    int ELFhash(char *key){

    unsigned long h=0;
    unsigned long x=0;

    while(*key)
    {
    h=(h<<4)+(*key++); //h左移4位,当前字符ASCII存入h的低四位
    if( (x=h & 0xF0000000L)!=0)
    { //如果最高位不为0,则说明字符多余7个,如果不处理,再加第九个字符时,第一个字符会被移出
    //因此要有如下处理
    h^=(x>>24);
    //清空28~31位
    h&=~x;
    }
    }
    return h % N;
    }

    关键还是要在实际应用中才能更深刻的把这个算法理解。如果 感兴趣,可以看我 ACM 字符串 标签里的poj2503题解,这题可以用ELFhash函数来做。也不算很难吧。

    转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/04/02/2430230.html

    展开全文
  • 字符串HASH函数

    2012-11-16 17:01:30
    百度,google了很多关于这个函数的用法。...(别人的分析:它对于长字符串和短字符串都很有效,字符串中每个字符都有同样的作用,它巧妙地对字符的ASCII编码值进行计算,ELFhash函数对于能够比较均匀地把字符串
    百度,google了很多关于这个函数的用法。都大同小异,都只是给出了代码,我觉得对我这个初学者来说有点难理解。所以,在这,我综合一下我搜到的知识,把它再加深下印象吧。
    

        ELFhash函数关键是要取得字符串对应的hash值。(别人的分析:它对于长字符串和短字符串都很有效,字符串中每个字符都有同样的作用,它巧妙地对字符的ASCII编码值进行计算,ELFhash函数对于能够比较均匀地把字符串分布在散列表中。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。)

        ELFhash():参考http://blog.chinaunix.net/uid-24683784-id-3061386.html

    复制代码
    int ELFhash(char *key){
    
        unsigned long h=0;
        unsigned long x=0;
    
        while(*key)
        {
            h=(h<<4)+(*key++);  //h左移4位,当前字符ASCII存入h的低四位
                    if( (x=h & 0xF0000000L)!=0)
            { //如果最高位不为0,则说明字符多余7个,如果不处理,再加第九个字符时,第一个字符会被移出
              //因此要有如下处理
              h^=(x>>24);
              //清空28~31位
              h&=~x;
            }
        }
        return h % N;
    }
    展开全文
  • 下面的代码示例计算字符串 MD5 哈希值,并将哈希返回为32字符的十六进制格式字符串。 此代码示例创建的哈希字符串与创建32字符的十六进制格式哈希字符串的任何平台上的任何 MD5 哈希函数兼容。 1. 引用Cryptography ...
  • Hash字符串(第一次接触Hash的小伙伴可以去看一下我的Hash初步,仅供参考)是一种很神奇的操作,历史很多计算机专业的学者,也进行了一系列的探讨与开发,所以现在有很多种Hash字符串的处理方式,最为常用的有三...
  • 前言 Rabin-Karp字符串匹配算法和前面介绍的《朴素字符串匹配算法》类似,也是相应每一个字符进行比較。不同的是Rabin-Karp採用了把字符进行预处理... 首先计算待匹配字符串hash值,计算目标字符串前M个字符的ha...
  • 计算机网络世界中一切信息包括用户的身份信息都是用一组特定的数据来表示的,计算机只能识别用户的数字身份,所有用户的授权也是针对用户数字身份的授权。如何保证以数字身份进行操作的操作者就是这个数字身份合法...
  • hash 将整个字符串进行计数区间统计前缀值,在调用的时候将遍历变为直接前缀进行计算,复杂度 o(n) 线性变为 o(1) #include<iostream> #include<cstring> using namespace std; const int Hash=131; ...
  • 来源:牛客网   题目描述 ZZT 得到了一个字符串 S 以及一个整数 K。 WZH 在 1995 年提出了“优雅 K 串”...现在 ZZT 想要对字符串进行 Q 次询问,第 i 次询问给出一个区间 [Li, Ri],他想计算 [Li, Ri] 中有多少...
  • Karp Rabin 算法是利用hash函数的特性进行字符串匹配的。KR算法模式串和循环中每一次要匹配的子串按一定的hash函数求值,如果hash值相同,才进一步比较这两个串是否真正相等也许你会有这样的疑问,在Brute force...
  •  数据查询语言 (Data Query Language, DQL) 是SQL语言中,负责进行数据查询而不会数据本身进行修改的语句,这是最基本的SQL语句。例如:SELECT(查询)  数据控制语言Data Controlling Language(DCL),用来...
  • [SQLServer2005] 哈希索引

    2010-01-03 15:29:00
    这种情况下可以考虑使用对字符串进行hash计算,然后对hash值进行索引。 本示例显示使用sqlserver 2005中, 通过CHECKSUM生成哈希索引。通过将计算校验和列添加到索引的表中,然后对校验和列生成索引来生成哈希索引。...
  • 1、 对字符串进行MD5不可逆算法加密,生成32位MD5密码; 2、对文件生成32位MD5指纹,确保文件在传输使用过程中没有被修改,没有出错,没有被植入木马、病毒等; 3、比对文件的MD5指纹,确定文件是否被修改(如果仅靠...
  • 采用java安全信息类java.security.MessageDigest对字符串、对象、文件进行加密,也可以计算文件hash值(对于文件服务器中实现文件对比很有用),下面列举MessageDigest类的用法①: 1、首先是创建一个类对象 ...
  • Hash算法

    2011-01-09 23:32:00
    ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效,字符串中每个字符都有同样的作用,它巧妙地对字符的ASCII编码值进行计算,ELFhash函数对于能够比较均匀地把字符串分布在散列表中。这些函数使用位...
  • ELFHash 算法

    2015-12-09 15:55:00
    它对于长字符串和短字符串都很有效,字符串中每个字符都有同样的作用,它巧妙地对字符的ASCII编码值进行计算,ELFhash函数对于能够比较均匀地把字符串分布在散列表中。这些函数使用位运算使得每一个字符都对
  • 内容hash,签名 (Windows Crypt API)

    千次阅读 2014-10-11 14:08:06
    Windows 提供了Crypto API, 使用这些API, 我们可以比较轻松的实现Hash,签名等工作。...下面的例子是一个给定的字符串进行hash计算,并且把hash值签名。给定的字符串如下: BYTE *pbBuffer = (BYTE *)"The data
  • 几种hash函数的汇总

    千次阅读 2010-10-08 18:57:00
    ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效,字符串中每个字符都有同样的作用,它巧妙地对字符的ASCII编码值进行计算,ELFhash函数对于能够比较均匀地把字符串分布在散列表中。具体做法...
  • GeoHash算法获取附近店铺和距离

    千次阅读 2020-09-11 10:04:54
    1. 简介 GeoHash算法将二维经纬度坐标直接转换成字符串,每...地球纬度区间是[-90,90],经度区间是[-180,180],通过区间法经度和纬度分别进行计算,假如我们获取到的当前坐标为经度-0.12866, 纬度38.534413,以纬度为
  • 对字符串的每一个字符,迭代的乘以33 原型: hash(i) = hash(i-1)*33 + str[i] ; 在使用时。存在一个问题,对相似的字符串生成的hashcode也类似,有人提出对原始字符串。进行MD5。然后再计算hashcode。 ...
  • sqlite中的hash算法实现

    2012-06-18 21:23:00
    sqlite的分词器模块需要输入的字符串映射为系统中的标示符...由于sqlite的关键字有100多个,如果每个字符串进行比较判断,无疑效率很低 2:使用hash算法: 首先构造一个散列函数,该函数计算字符串得到一个hash...
  • Hash散列算法之 Time33算法

    千次阅读 2014-04-19 00:24:01
    对字符串的每个字符,迭代的乘以33 原型: hash(i) = hash(i-1)*33 + str[i] ; 在使用时,存在一个问题,对相似的字符串生成的hashcode也类似,有人提出对原始字符串,进行MD5,然后再计算hashcode。
  • 文件进行数字签名

    千次阅读 2012-06-11 18:02:53
    文件进行数字签名大致上是这样做的,当用户连接设备的会话结束以后,系统LOG文件后面再上一串固定的字符串(64个字符差不多了,需保密),然后用MD5进行hash,这样将得到一串128位的hash,把它存储到数据库。...
  • Win本地hash概念

    2020-08-03 12:17:33
    这个加密函数一个任意长度的字符串数据进行一次数学加密函数运算,然后返回一个固定长度的字符串。现在已经有了更新的NTLMv2以及Kerberos验证体系。 Windows加密过的密码口令,我们称之为has.
  • GeoHash补充

    2016-05-09 16:03:31
    - 我们可以不用进行base32编码,直接将其转化为unsinged long,可以大大减少计算,数据库使用字符串是因为很多数据库对字符串类型有很好的支持,c上面用字符串效率低得可以 - 之前那个写得仓促,有很多错误没整理,...
  • **内容:**今天在看STL源码剖中的hashtable这一节时,书中讲述hashtable的hash散列函数对大多数int,char,short类型什么都不做,直接返回,对字符串的书中有一个对字符串每个字符的ASCII值乘5叠加的公式计算哈希值...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 156
精华内容 62
关键字:

对字符串进行hash计算