Hash表这种数据结构在java中是原生的一个集合对象,在实际中用途极广,主要有这么几个特点:
- 访问速度快
- 大小不受限制
- 按键进行索引,没有重复对象
- 用字符串(id:string)检索对象(object)
今天整理以前在学校写的一些算法,翻出来一个hash表的实现,就贴出来,自己也温习温习。
先看看头文件,也就是数据结构的定义,相当于java中的接口的概念:
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->#include <stdio.h>
#define HASHSIZE 256
//定义hash表中的节点的类型
struct nlist{
struct nlist *next;
char *name;
char *defn;
};
//定义接口中的函数,也就是对外来说,这个程序可以做什么
unsigned hash(char *s);//计算一个串的hash值
struct nlist *lookup(char *s);//查找一个value,根据key
struct nlist *install(char *name,char *defn);//插入一个key=value的对象
然后是具体实现:
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->#include <string.h>
#include "list.h"
static struct nlist *hashtab[HASHSIZE];
unsigned hash(char *s)
{
unsigned hashval;
for(hashval = 0; *s != '\0';s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
struct nlist *lookup(char *s)
{
struct nlist *np;
for(np = hashtab[hash(s)];
np != NULL;
np = np->next)
if(strcmp(s,np->name) == 0)
return np;
return NULL;
}
struct nlist *install(char *name,char *defn)
{
struct nlist *np;
unsigned hashval;
if((np = lookup(name)) == NULL){
np = (struct nlist *)malloc(sizeof(struct nlist));
if(np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next= hashtab[hashval];
hashtab[hashval] = np;
}else
free((void *)np->defn);
if((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}
很简单,只有两个外部接口,
- install(key, value),用来插入一个新的节点
- lookup(key),根据一个键来进行搜索,并返回节点
代码很简单,主要用到的hash算法跟java中的String的hashcode()方法中用到的算法一样,使用:
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->unsigned hash(char *s)
{
unsigned hashval;
for(hashval = 0; *s != '\0';s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
这里的31并非随意,乃是一个经验值,选取它的目的在于减少冲突,当然,hash冲突这个问题是不能根本避免的。这里只是一个人们在测试中发现的可以相对减少hash冲突的一个数字,可能以后会发现更好的数值来。
分享到:
相关推荐
用C实现的哈希表 int hash_insert(Hash* * hp,int data)//返回0表示成功 { if((*hp) == NULL)return 1; if(((*hp)->num)==14) { printf("hash full\n"); return 1;//哈希表满了 } if((*hp)->pNode[KEY(data...
C语言实现hash算法源码,实现了sha256,sha384,sha512三种哈希算法,项目中用到的,提取出来测试使用的。
该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论是自定义的struct还是基本数据类型,需要注意的是不同类型的key其操作接口方式略有不通。...
hash算法C代码实现 标准接口函数 方便修改hash函数
从linux内核提取出来的,双向链表和hash表实现。在普通的用户态C程序中,均可使用
扫描一个C源程序,用Hash表存储该程序中出现的关键字,并统计该程序中的关键字出现的度。用线性探测法解决Hash冲突。设Hash函数为:Hash(Key)=[(Key的首字母序号)*100+(Key的尾字母序号)] Mod 41。关键字39个,参考...
uthash开源的hash函数实现,里面的uthash.h可用
压缩包里包括了MD5算法的源代码,完全用C语言实现,同时还附带了7个验证Hash的小工具,供大家使用希望对大家有所帮助!谢谢使用
1)利用C\C++语言实现DSA算法。 2)DSA中的Hash函数采用SHA算法。 (1)消息填充:因为我们存储的时候是以字节为单位存储的,所以消息的长度(单位:位)一定是 8 的倍数。而我们填充的时候也一定是 8 位、8 位...
通过建立邻接表,然后建立两个Hash表,同时实现按照姓名查找,电话号码查找相关功能。
This is a simple hash table implementation in ANSI C. It supports the rudimentary functions generally expected of a hash table: Inserting and retrieving key-value associations Querying the existence ...
根据算法导论上的HashTable, C语言实现
MurmurHash3通用hash bashed查找函数实现 关于 是一种非加密哈希函数,适用于一般的基于哈希的查找。 此实现实现了 MurmurHash 的第 3 版。 安装 : $ clib install jwerle/murmurhash.c 来源: $ git clone git@...
C++实现的hash冲突解决算法,有好几种解决方法
c语言实现哈希表,,,已经在vc++6.0上调试通过,2.txt中的内容为 12 19 14 23 1 68 20 84 27 55 11 10 79
这个小程序实现了哈希表的主要内容。有哈希函数、冲突避免,实现了插入和查找。主要是作为一个教学的例子存在。 本程序用Visual Studio 2005实现。
该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论是自定义的struct还是基本数据类型,需要注意的是不同类型的key其操作接口方式略有不通。...
一个开源的hash表的实现。The source code of structure hashtable.