精华内容
下载资源
问答
  • 【C++】字符串hash计算

    千次阅读 2019-08-22 16:11:42
      C++ 11 中新加入的容器 unordered_map 和 unordered_set 底层都是哈希表实现的,那么对于内置类型,肯定是可以自动计算hash 值的,但是对于像 pair<int, int> 或者 vector<int> 这样的,或者...

      C++ 11 中新加入的容器 unordered_map 和 unordered_set 底层都是哈希表实现的,那么对于内置类型,肯定是可以自动计算出 hash 值的,但是对于像 pair<int, int> 或者 vector<int> 这样的,或者自定义的类这种复杂类型,就不能自动算出 hash 值了,编译会提示 The C++ Standard doesn’t provide a hash for this type。那么就需要自己去定义 hash function 了,自定义 hash 函数可以参考 https://blog.csdn.net/Bob__yuan/article/details/96737222,这里不讨论这个问题。
      本文学习并记录一下 C++ 中 string 的 hash 计算方式。首先我们定义一个 unordered_map 如 unordered_set<string> hs;,然后跳到 unordered_map 的定义,可以看到模板参数中第二个参数就是 hash 函数,默认使用 hash<_Kty>

      然后再跳到 hash<_Kty> 的定义,如下,有一个模板实现,以及一些模板特化,但是没有针对 string 的特化。

      随着C++发展,这部分代码肯定会变,就像上文链接中我是用vs2015里边写的,hash 的结构定义就和上边这个截图(vs2017中)不一样。不过意思都是差不多的。
      跳到 _Hash_representation 中发现有跳到了别的函数 _Fnv1a_append_value

      再跳过去,这里有提示 "Only trivial types can be directly hashed."

      再跳到 _Fnv1a_append_bytes

      就是这里了!! 这里的返回值就是 hash 值,这个函数也很简单,就是从前到后遍历这个传入的参数,对每一位,先转换为 size_t,然后和 _Val 进行异或(注意 _Val 传入就是 _FNV_offset_basis),然后 _Val *= _FNV_prime;。也就是传入的是 string 的话,对每个字符,转换成 size_t(应该就是 ascii 码),异或,乘一个常量,循环。 重点就是下边这两句

    	_Val ^= static_cast<size_t>(_First[_Idx]);
    	_Val *= _FNV_prime;
    

    下面我们验证一下。

    #include <iostream>
    #include <string>
    using namespace std;
    
    constexpr size_t tmp_FNV_offset_basis = 2166136261U;
    constexpr size_t tmp_FNV_prime = 16777619U;
    
    int main(){
    	// 输出 hash 函数计算出的 hash 值
    	cout << "hash<string>()(\'a\') = " << hash<char>()('a') << endl;		// 3826002220
    	cout << "hash<string>()(\"a\") = "   << hash<string>()("a")   << endl;	// 3826002220
    	cout << "hash<string>()(\"abc\") = " << hash<string>()("abc") << endl;	// 440920331
    
    	// 手动计算 'a' 的 hash 值
    	size_t val1 = tmp_FNV_offset_basis;
    	val1 ^= static_cast<size_t>('a');
    	val1 *= tmp_FNV_prime;
    	cout << "val1 = " << val1 << endl;
    
    	// 手动计算 'abc' 的 hash 值
    	string str = "abc";
    	size_t val2 = tmp_FNV_offset_basis;
    	for(int i = 0; i < str.length(); ++i) {
    		val2 ^= static_cast<size_t>(str[i]);
    		val2 *= tmp_FNV_prime;
    	}
    	cout << "val2 = " << val2 << endl;
    }
    

      结果如下:

    hash()(‘a’) = 3826002220
    hash()(“a”) = 3826002220
    hash()(“abc”) = 440920331
    val1 = 3826002220
    val2 = 440920331

      说明 string 的 hash 值确实是这么计算的,字符也是这么处理,就相当于是长度为 1 的字符串。

      不过《STL源码剖析》里讲,SGI STL 中,string 是按照如下方式计算的:

    // 以下定义于 <stl_hash_fun.h>
    template <class Key> struct hash { };
    inline size_t __stl_hash_string(const char* s)
    {
    	unsigned long h = 0;
    	for ( ; *s; ++s)
    		h = 5 * h + *s;
    	return size_t(h);
    }
    
    展开全文
  • 小弟在用lua写个脚本需要根据字符串的哈希值进行分组,找了半天也没找到相关的库函数,请问使用lua怎么能得出字符串hash值呢?
  • 字符串hash

    千次阅读 2018-10-21 13:08:03
    这个是在学习哈希表的时候偶然带出来的,想着都是hash家的人,一起看看,...【将KMP一起看了,这种问题用KMP也可以解决啊,而且人家KMP的代码短啊,,也是不太清楚字符串hash存在的意义是啥,,】如果是从主串中每次...

      这个是在学习哈希表的时候偶然带出来的,想着都是hash家的人,一起看看,结果比哈希表难好多【或许是哈希表学的不深入】; 

    解决问题:

      字符串hash主要应用在:寻找长度为n的主串S中的匹配串T(长度为m)出现的位置次数的问题属于字符串匹配问题。【将KMP一起看了,这种问题用KMP也可以解决啊,而且人家KMP的代码短啊,,也是不太清楚字符串hash存在的意义是啥,,】如果是从主串中每次选出两个子串判断是否匹配问题,还是要用字符串hash求解

    主要思路:

      1》将字符串中的每一个字母都看做是一个数字(例:从a-z,视为1-26);

      2》选取两个合适的互质常数 b,h ( b < h )【互质,有用;b < h,有用too】;

      3》定义哈希函数,H(C)=[ c1*b^(m-1) + c2*b^(m-2) + . . . + c0*b^0 ] mod h

          【看不懂吧,看不懂就对了,我也看不懂hhhh~

             (1) C代表一个字符串,用C=c1 c2 c3 c4..cm;表示该字符串,其中 ci 表示从前向后数的第 i 个字符;

             (2) 方括号[ ]内的表达式:c1*b^(m-1) + c2*b^(m-2) + . . . + c0*b^0 意为将字符串C当做 b进制数 来处理,b是基数;

             (3) 关于对 h 取模,若b,h有公因子,那么不同的字符串取余之后的结果发生冲突的几率将大大大增加(冲突:数值相同的意

                  思) 

            】;

      4》计算上一步H(C)的过程是递归实现的:H(C,k)为前 k 个字符构成的字符串的哈希值,(若不考虑取模):

            H(C,k+1)= H( C , k ) * b+c( k+1 );

      5》判断 主串上 长度为 n 的任意子串 C '=c(k+1) c(k+2) c(k+3) . . . c(k+n) 与 待匹配串S=s1 s2 s3. . .sn 的哈希值是否相等【现在子串长度为n!!】,则:

             H(C ’)= H( C , k+n ) - H(C, k ) * b^n; 

       【我全部都看明白之后还是有点懵,感觉和用遍历没什么差别,,看看了看分析,因为运算是递归的,所以主串中前 i 字符的哈希值是打表存储好的,取子串时直接调用相减函数就可以,此时需要计算的只有b^n,还是省去很多比对的过程的】

      6》思路在第五步就已经结束了,我看完也在翘首期盼着“考虑取模”的讲解,其实在实际应用中,通常利用32/64位无符号整数来计算哈希值的,这样的话,当哈希值溢出时,系统会自动对h=2^32 / h=2^64取模

    不足之处:

      对于哈希值在 0~n 内均匀分布的哈希函数,出现不同字符串哈希值相等的期望步数是O(sqrt(n)),这在选择哈希函数时可以作为一个效率和正确性的参考。

      即便如此,我们还可以再双哈希降低出现相同哈希值的概率,即取不同的模数,把不同的模数算出来的哈希值都记下来,只有几个哈希值都一样,我们才能判定字符串的匹配,我们通常用双哈希就可以相冲突的概率降到最低,如果分别取 h1=10^9+7和h=10^9+9,就几乎不可能发生冲突,因为他们是一对孪生质数

     

     

     

     

     

     

     

    展开全文
  • 字符串Hash

    2020-02-01 22:08:52
    字符串Hash 简介 字符串Hash就是将一串字符串转换成一个整数。 主要解决找子串或者一串字符串中任意两段是否相等之类的问题,简单来说就是快速判断字符串相不相等。 那如何判断字符串是否相等呢?就是看转换成的整数...

    字符串Hash

    简介

    字符串Hash就是将一串字符串转换成一个整数

    主要解决找子串或者一串字符串中任意两段是否相等之类的问题,简单来说就是快速判断字符串相不相等。
    那如何判断字符串是否相等呢?就是看转换成的整数是否相等。

    采纳博客:https://blog.csdn.net/pengwill97/article/details/80879387
    那我来举个例子:
    p=131,mod=264; 注:mod的取值一般都是264 ,这是unsigned long long int 的最大取值范围,所以一般都可以不用写
    那么字符串:“abc” 的字符串Hash值为多少?
    嗯,我们要先规定a - z 的值为 1 - 24。
    然后就按进制转换的方法算:
    所以 ”abc“ 的Hash值为11312 +21311 +3*1310 =17426

    还有两点要注意:
    1. 一般要计算出该字符串所有前缀的值,比如:”abc",就要算出“a”的hash值,“ab”的hash值和“abc”的hash值;
    2. 还要计算p的1 - n次方的值,n为字符串的长度,并且要保存到数组里面,上面那一点的值也要保存到数组里。

    嗯,接下来就讲个例题吧!

    例题

    链接:https://www.acwing.com/problem/content/description/140/
    大佬视频讲解:https://www.acwing.com/video/44/
    相关博客:https://blog.csdn.net/pengwill97/article/details/80879387
    这道题目的大意就是:一串字符串中任意两段是否相等;

    我想hash值应该没问题了吧;

    主要是如何算出某一段字符串的hash值;

    采纳博客:https://blog.csdn.net/pengwill97/article/details/80879387
    注:视情况mod可以省去;

    那我来举个例子:
    p=131,mod=264;
    char s[4]=“abc”;
    由上面的计算hash值的公式,我们可以的出:hash[1]=1,(hash[1]等价于“a”)hash[2]=133,hash[3]=17426;p[0]=1,(p[0]等价于P0 )p[1]=131,p[2]=17161,p[3]=2248091;
    那么"bc"的值为ans=hash[3]-hash[1]*p[2]=?;这个就自己算啦

    那看看代码吧!

    代码

    #include <stdio.h>
    #include <string.h>
    #define ull unsigned long long int
    #define N 1000010
    
    char s[N];
    ull h[N], p[N]; //h用来保存字符串前缀的值,p用来保存次方的值
    
    ull fun(int a, int b) { //计算hash值
    	return h[b] - h[a - 1] * p[b - a + 1];
    }
    
    int main() {
    	int i, len, base = 131;
    	scanf("%s", s + 1);
    	
    	len = strlen(s + 1);
    	h[0] = 0; p[0] = 1;
    	for (i = 1; i <= len; i++) { //算前缀和次方的值
    		h[i] = h[i - 1] * 131 + s[i] - 'a' + 1;
    		p[i] = p[i - 1] * 131;
    	}
    
    	int a, b, c, d, n;
    	scanf("%d", &n);
    	while (n-- > 0) {
    		scanf("%d%d%d%d", &a, &b, &c, &d);
    		if (fun(a, b) == fun(c, d)) {
    			printf("Yes\n");
    		}
    		else {
    			printf("No\n");
    		}
    	}
    
    	return 0;
    }
    
    展开全文
  • python 计算字符串hash

    千次阅读 2019-10-05 06:01:55
    import hashlib def stringtomd5(originstr): """将string转化为MD5""" signaturemd5 = hashlib.md5() signaturemd5.update(originstr) return signaturemd5.hexdigest() 转载于:https://www.cnblogs.com...
    import hashlib 

    def stringtomd5(originstr):
    """string转化为MD5"""
    signaturemd5 = hashlib.md5()
    signaturemd5.update(originstr)
    return signaturemd5.hexdigest()

    转载于:https://www.cnblogs.com/snowDream-shineDream/p/9157324.html

    展开全文
  • Hash字符串匹配

    2019-05-20 19:23:17
    hash字符串匹配即把固定长度的字符串转化为hash进行匹配,这种匹配方式在大量数据的情况下是有误差的,大约万分之四五左右,这是因为hash值是通过字符和公式计算出来的,不同的字符串有可能根据我们的计算公式算出...
  • 小工具-计算字符串hash值 crc32 md5 sha sha1 sha224 sha256 sha384 sha512
  • mycat1.6.5分片(字符串拆分hash

    千次阅读 2017-10-22 21:33:10
    mycat1.6.5字符串拆分hash
  • 经典字符串hash函数

    2012-09-01 15:21:44
    几个经典字符串hash函数,SDBM/RS/JS/BKDR/DJB/AP HASH
  • 对字符串进行哈希的算法,hash_func

    千次阅读 2014-04-25 15:08:34
    最近做了一个项目,需要对字符串进行大量查找,效率
  • 性能很高的计算字符串或文件hash值的函数,比md5速度快得多,自己一直用着,重复的几率为很底,一般的应用足够, var I64BIT_TABLE = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-'.split...
  • C++ 字符串hash

    千次阅读 2017-02-16 11:00:17
    // BKDR Hash Function BKDR 字符串转哈希值
  • 字符串hash解析分片,其实就是根据配置的hash预算位规则,将截取的字符串进行hash计算后,得到的int数值即为datanode index(分片节点索引,从0开始)。 二、字符串hash分片 实现步骤: 【a】创建数据库和表 ...
  • 求一个字符串hash

    千次阅读 2016-04-28 14:37:52
    求一个字符串hash值: •现在我们希望找到一个hash函数,使得每一个字符串都能够映射到一个整数上 •比如hash[i]=(hash[i-1]*p+idx(s[i]))%mod •字符串:abc,bbc,aba,aadaabac •字符串下标从0开始 •先...
  • 计算字符串hash值小工具源码(使用openssl) crc32 md5 sha sha1 sha224 sha256 sha384 sha512
  • 字符串哈希 Hash 的思想 Hash 的核心思想在于,将输入映射到一个值域较小、可以方便比较的范围。 Warning!Warning!Warning! 这里说的“值域较小”在不同的情况下意义是不一样的: 在哈希表中:值域需要小到能够...
  • 字符串哈希(Hash)

    千次阅读 多人点赞 2019-06-24 21:04:06
    所谓字符串哈希就是构造一个数字使...同理,给你一个字符串,要把它转换为数字,就可以先把每一个字符都先对应一个数字,然后把它们按照顺序乘以进制的幂进行相加。 如abcd,我们取各个字母的ASCII码值减去a的ASCI...
  • 主要介绍了Go语言对字符串进行SHA1哈希运算的方法,实例分析了Go语言针对字符串操作的技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 计算文件或者一段字符串HASH,SHA1,SHA256,CRC32,MD5的值。里面有readMe文件,可在控制台中运行计算。在界面中,readme中有详细的介绍。可显示当前计算的进度和时间信息
  • 【算法学习】字符串哈希(Hash

    千次阅读 2020-01-15 21:11:25
    什么是字符串Hash 构造字符串Hash 1)自然溢出方法 2)单Hash方法 3)双Hash方法 4)三种不同的构造方法的对比 获取子串的Hash O(1) 1)例子 2)公式 具体的题目例子 1)题目链接 2)题意 3)解题分析 ...
  • 字符串的经典hash算法

    万次阅读 2010-09-29 19:30:00
    字符串 hash 算法
  • 计算两个字符hash值工具类,输入项为(string1,string2,hashAlgorithm),根据hash算法计算string1和string2的hash值,再将两个hash值拼接后再计算出一个hash值输出。hashAlgorithm名为配置文件可配。 这是师傅给...
  • KMP替代算法——字符串Hash

    千次阅读 2018-02-01 17:23:40
    KMP替代算法——字符串Hash 今天来谈谈一种用来替代KMP算法的奇葩算法——字符串Hash 例题:给你两个字符串p和s,求出p在s中出现的次数。(字符串长度小于等于1000000) 字符串的Hash 根据字面意思,这种...
  • Java里字符串hash算法

    千次阅读 2016-08-15 20:19:27
    Java的hash算法,简单小巧的的散列方法 public int hashCode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i ; i++
  • /** * 获取Hash值 */ public static String ... //Java利用MessageDigest获取字符串MD5 final MessageDigest mDigestData = MessageDigest.getInstance("MD5"); mDigestData.update(key.getBytes(.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 151,230
精华内容 60,492
关键字:

对字符串进行hash计算