文档章节

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

realsa
 realsa
发布于 2016/05/15 13:28
字数 600
阅读 90
收藏 1
点赞 3
评论 0

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
博文 82
码字总数 107087
作品 0
广州
程序员
DOM——拷贝.clone()与替换.replaceWith() 和.replaceAll()及包裹.wrap()

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

拉考的考拉 ⋅ 2017/11/21 ⋅ 0

比特币源码解读十九

我们终于看到初始化客户端的最后一步:Step 12: finished(初始化完成) 从解读三一直写到了解读十九,这些内容基本上也包括了比特币很核心的内容:包括区块,交易,P2P网络,挖矿。虽然理解十分...

ttblack ⋅ 2017/12/24 ⋅ 0

JDK不同操作系统的FileSystem(unix-like)下篇

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

超人汪小建 ⋅ 2017/12/10 ⋅ 0

读 zepto 源码之工具函数

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

jjjyyy66 ⋅ 2017/05/15 ⋅ 0

[LeetCode] Sentence Similarity II 句子相似度之二

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, words1......

机器的心脏 ⋅ 2017/12/05 ⋅ 0

计算机基础导论 学习总结 中

第四单元 响应查询 本单元将建立一个可行的搜索引擎,可以抓取并建立一系列网页的索引,可以响应关键词查询。首先是建立网络语料库的索引,其结构将会是:列表的每一项是一个关键词,及该关键...

Nautilus1 ⋅ 2017/11/28 ⋅ 0

Puppet数据类型中[数值类型,数组的使用] (十四)

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

青衫解衣 ⋅ 2017/09/25 ⋅ 0

redis笔记-数据结构篇

2018-1-3 by Atlas 1. SDS + 描述 > redis底层是C语言编写,而redis没有直接使用C语言的字符串表示,是自己构建了一种名为简单动态字符串的抽象类型,即SDS(simple dynamic string)。> red...

水天云黑白 ⋅ 01/04 ⋅ 0

C++ Primer Plus(十二)——类和动态内存分配

静态数据成员在类声明中声明,在包含类方法的文件中初始化。初始化时使用作用域运算符来指出静态成员所属的类。但如果静态成员是整型或枚举型const,则可以在类声明中初始化。 strlen返回字符...

吃一堑消化不良 ⋅ 2016/02/29 ⋅ 0

《Redis设计与实现》简读

一、数据结构与对象 简单动态字符串(SDS) 相比C字符串增加记录字符串长度的,获取字符串长度复杂度为O(1) 相比C字符串增加记录已分配内存空间,可以避免缓冲区溢出 空间预分配和空间惰性释...

ZoaChou ⋅ 2016/08/07 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

开启远程SSH

SSH默认没有开启账号密码登陆,需要再配置表中修改: vim /etc/ssh/sshd_configPermitRootLogin yes #是否可以使用root账户登陆PasswordAuthentication yes #是都开启密码登陆ser...

Kefy ⋅ 15分钟前 ⋅ 0

Zookeeper3.4.11+Hadoop2.7.6+Hbase2.0.0搭建分布式集群

有段时间没更新博客了,趁着最近有点时间,来完成之前关于集群部署方面的知识。今天主要讲一讲Zookeeper+Hadoop+Hbase分布式集群的搭建,在我前几篇的集群搭建的博客中已经分别讲过了Zookeep...

海岸线的曙光 ⋅ 22分钟前 ⋅ 0

js保留两位小数方法总结

本文是小编针对js保留两位小数这个大家经常遇到的经典问题整理了在各种情况下的函数写法以及遇到问题的分析,以下是全部内容: 一、我们首先从经典的“四舍五入”算法讲起 1、四舍五入的情况...

孟飞阳 ⋅ 40分钟前 ⋅ 0

python log

python log 处理方式 log_demo.py: 日志代码。 #! /usr/bin/env python# -*- coding: utf-8 -*-# __author__ = "Q1mi""""logging配置"""import osimport logging.config# 定义三种......

inidcard ⋅ 55分钟前 ⋅ 0

mysql 中的信息数据库以及 shell 查询 sql

Information_schema 是 MySQL 自带的信息数据库,里面的“表”保存着服务器当前的实时信息。它提供了访问数据库元数据的方式。 什么是元数据呢?元数据是关于数据的数据,如数据库名或表名,...

blackfoxya ⋅ 57分钟前 ⋅ 0

maven配置阿里云镜像享受飞的感觉

1.在maven目录下的conf/setting.xml中找到mirrors添加如下内容,对所有使用改maven打包的项目生效。 <mirror> <id>alimaven</id> <name>aliyun maven</name> <url>http://maven.al......

kalnkaya ⋅ 57分钟前 ⋅ 0

centos7下创建新用户并授权

1、创建新用户 创建一个用户名为:test adduser test 创建初始密码: passwd test 2、授予root权限 个人用户的权限只可以在/home/test下有完整权限,其他目录要看别人授权。而经常需要roo...

xixingzhe ⋅ 今天 ⋅ 0

求助:TiledMap如何旋转对象呢?

比如我要旋转一个梯子的角度,单纯在TiledMap旋转角度好像没有效果。那是要用代码来控制角度,还是说只能通过导入相对应的斜的图片才可以呢?

花谢自相惜 ⋅ 今天 ⋅ 0

Micronaut 之HelloWorld!

小试一下Micronaut,按照官方文档跑了一下helloworld 第一步克隆,按照官方文档是: git clone git@github.com:micronaut-projects/micronaut-core.git 结果怎么是这样?? 换个方法吧 git ...

桂哥 ⋅ 今天 ⋅ 0

pom文件

Aeroever ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部