文档章节

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

realsa
 realsa
发布于 2016/05/15 13:28
字数 600
阅读 103
收藏 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
广州
程序员
DOM——拷贝.clone()与替换.replaceWith() 和.replaceAll()及包裹.wrap()

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

拉考的考拉
2017/11/21
0
0
学习zepto.js(原型方法)[1]

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

贾顺名
2015/08/10
0
0
python --- hashlib模块使用详解

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

码农47
2017/10/25
0
0
JDK不同操作系统的FileSystem(unix-like)下篇

前言 我们知道不同的操作系统有各自的文件系统,这些文件系统又存在很多差异,而Java 因为是跨平台的,所以它必须要统一处理这些不同平台文件系统之间的差异,才能往上提供统一的入口。 关于...

超人汪小建
2017/12/10
0
0
读 zepto 源码之工具函数

源码版本 本文阅读的源码为 zepto1.2.0 $.extend 方法可以用来扩展目标对象的属性。目标对象的同名属性会被源对象的属性覆盖。 其实调用的是内部方法 , 所以我们先看看内部方法 的具体实现。...

jjjyyy66
2017/05/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java中的移位运算符

国庆给自己放了个小长期二十几天,回来继续更新专栏 上一篇文章我们说了Java里的二进制,知道了计算机是以0和1来处理数据的,在阅读源码的过程中,经常会看到这些符号<< ,>>,>>>,这些符号...

SuShine
20分钟前
2
0
linux版QQ

下载地址在这 http://yun.tzmm.com.cn/index.php/s/XRbfi6aOIjv5gwj Appimage包不用做什么别的处理,安装啥的都不需要。。找到文件所在目录,终端中修改一下文件的权限 chmod 777 QQ-2017112...

悲催的古灵武士
26分钟前
1
0
咕泡-MyBatis 实用篇作业

1. Mapper在spring管理下其实是单例,为什么可以是一个单例? 首先,mapper 内部不包含 成员字段,无状态单例是安全的 另外,一直存在不用每次调用都new 一个新实例 2. MyBatis在Spring集成下...

职业搬砖20年
29分钟前
2
0
MQTT协议的初浅认识之连接建立

MQTT百科 MQTT(消息队列遥测传输)是ISO 标准(ISO/IEC PRF 20922)下基于发布/订阅范式的消息协议。它工作在 TCP/IP协议族上,是为硬件性能低下的远程设备以及网络状况糟糕的情况下而设计的发布...

亚林瓜子
45分钟前
1
0
OpenStack部署都有哪些方式

对于每一个刚接触到OpenStack的新人而言,安装无疑是最困难的,同时这也客观上提高了大家学习OpenStack云计算的技术门槛。想一想,自己3年前网上偶然接触到OpenStack时,一头茫然,手动搭建一...

tututu_jiang
46分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部