文档章节

【C语言】哈希函数写法、字符串深度复制

realsa
 realsa
发布于 2016/05/15 13:28
字数 600
阅读 122
收藏 1

Little trick.

1 哈希函数

理想的哈希函数保证每个字符串对应唯一的哈希值。下面这个哈希函数是同学在项目中遇到的。

unsigned int hash(char* s)
{
    unsigned int h=0;
    for(;*s;s++)
        h = *s + h*31;
    return h%HASHSIZE; //predefined hash size
}

可以看出,这个hash函数遍历字符串中每个字符,通过将其ASCII码计算得到最终的哈希值h。 这样来确保前面提到的结果唯一性。 我们在gdb中验证一下,有char*类型的字符串s为nnmm。s的第i个字符用s[i]或者*(s+i)表示。

(gdb) p s
$8 = 0x40071c "nnmm"
(gdb) p s[0]
$11 = 110 'n'
(gdb) p s[1]
$12 = 110 'n'
(gdb) p s[2]
$13 = 109 'm'

(gdb) p *s
$9 = 110 'n'
(gdb) p *s+1
$10 = 111
(gdb) p *(s+1)
$14 = 110 'n'
(gdb) p *(s+2)
$15 = 109 'm'

可以看到,直接打印第i个字符的同时也会输出该字符的ASCII码。 第i个字符在公式中转成ASCII码,然后算出unsigned int型的h。

ASCII码对照表
输入图片说明

1.1 哈希函数的对比

[1]中提到编程珠玑中的一个hash函数也是用的类似方法,代码如下:

//用跟元素个数最接近的质数作为散列表的大小
#define NHASH 29989
#define MULT 31

unsigned in hash(char *p)
{
    unsigned int h = 0;
    for (; *p; p++)
        h = MULT *h + *p;
    return h % NHASH;
}

除此之外,[1]还对常用字符串哈希函数 BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash进行了量化比较。

1.2 哈希函数分类

[2]中把哈希函数分为如下几类:

  1. 加法Hash;
  2. 位运算Hash;
  3. 乘法Hash;
  4. 除法Hash;
  5. 查表Hash;
  6. 混合Hash;

其中我们上文的函数属于乘法Hash,这种类型的Hash函数利用了乘法的不相关性(乘法的这种性质,最有名的莫过于平方取头尾的随机数生成算法,虽然这种算法效果并不好)。

jdk5.0里面的String类的hashCode()方法也使用乘法Hash。不过,它使用的乘数是31。推荐的乘数还有:131, 1313, 13131, 131313等等。

Reference

2 字符串深度复制

char* str_dump(char* s)
{
    int l=strlen(s)+1;
    char* ns=(char*)malloc(l*sizeof(char));
    strcpy(ns,s);//char *strcpy(char* dest, const char *src)
    return ns;// possible be NULL
}

© 著作权归作者所有

共有 人打赏支持
realsa

realsa

粉丝 30
博文 84
码字总数 107087
作品 0
广州
程序员
私信 提问
python --- hashlib模块使用详解

  这个模块实现了一个通用的接口来实现多个不同的安全哈希和消息摘要算法。包括FIPS安全散列算法SHA1,SHA224,SHA256,SHA384和SHA512(在FIPS 180-2中定义)以及RSA的MD5算法(在因特网 ...

码农47
2017/10/25
0
0
DOM——拷贝.clone()与替换.replaceWith() 和.replaceAll()及包裹.wrap()

拷贝.clone()与替换.replaceWith() 和.replaceAll()及包裹.wrap() 1 .clone()深度复制所有匹配的元素集合,包括所有匹配元素、匹配元素的下级元素和文字节点 2 如果节点有事件或者数据之类的...

拉考的考拉
2017/11/21
0
0
深入谈谈String.intern()在JVM的实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/wangyangzhizhou/article/details/79860622 前言 String 类的方法可能大家比较少用也比较陌生,虽然实际项目中...

超人汪小建(seaboat)
04/09
0
0
Puppet数据类型中[数值类型,数组的使用] (十四)

本文主要写puppet的数据类型中的数值类型和数组的使用,博主puppet为3.8版本,puppet数组的追加功能测试没有成功,官网也没有给出示例,确定是否已经优化或者取消.官网数据类型连接地址 https:...

青衫解衣
06/29
0
0
学习zepto.js(原型方法)[1]

新的一周,新的开始,今天来学习一下zepto里边的原型方法,就是通过$.进行调用的方法,也是可以通过$.fn进行扩展的方法: $.camelCase(): 方法接收一个字符串,将连字符格式的字符串转为驼峰格式的...

贾顺名
2015/08/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机系统要素 C5

本章值得一提的是组织计算机的结构。Hack 的指令和数据是分开存储的,因此它的 CPU 有两个 input: IN inM[16], // M value input (M = contents of RAM[A]) instruction[16],...

lionets
13分钟前
0
0
SpringSecurity404需要注意的地方

在使用@RequestMapping的时候路径的值如果写为("auth"),虽然用的时候前面加不加"/"没有区别,但是在配置了SpringSecurity的http.authorizeRequests().antMatchers()时就必须要注意了! 🌰1...

百萬馬力
16分钟前
0
0
10分钟读懂阿里巴巴高级专家在Flutter Live2018的分享

作者:闲鱼技术-宗心 12月4日,google flutter团队宣布第一个flutter正式版本发布。次日,Flutter Live Beijing 会议上,google flutter团队邀请了在这一技术方案中重要的合作伙伴闲鱼团队分...

阿里云官方博客
17分钟前
1
0
RxJava window操作符

原文:https://github.com/Froussios/Intro-To-RxJava/blob/master/Part%204%20-%20Concurrency/3.%20Sequences%20of%20coincidence.md Sequences of coincidence Rx试图避免管道(pipeline)外......

woshixin
24分钟前
1
0
05.Beetl标签函数以及定界符、占位符介绍---《Beetl视频课程》

本期视频实现了博客的详情页面; 内容简介:使用了标签函数layout完成详情功能 一起学beetl目录:https://my.oschina.net/u/1590490?tab=newest&catalogId=6214598 作者:GK #标签函数 layo...

Gavin-King
25分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部