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...
`hash.c`通常包含了哈希表的函数实现,而`hash.h`则包含对外的头文件,定义了哈希表的数据结构和相关的接口函数。 在`hash.h`中,可能会定义如下的数据结构: ```c typedef struct HashNode { void* key; void* ...
本项目是用C语言实现的哈希算法,包括SHA256、SHA384和SHA512三种不同的哈希函数,这些函数是SHA-2(Secure Hash Algorithm 2)家族的一部分。 SHA-2是由美国国家安全局(NSA)设计的,包含了多种不同长度的哈希...
哈希(Hash)算法在计算机科学中扮演着重要的角色,特别...同时,为了处理碰撞,可以结合链地址法、开放寻址法或者双重哈希等方法实现哈希表。在压缩包中的`hash`文件可能包含了更多不同哈希函数的实现,供学习和参考。
在压缩包文件"C-hash"中,很可能包含了实现上述功能的C语言源代码,包括哈希表结构定义、哈希函数、冲突解决机制以及插入、查找和删除操作的函数。通过阅读和理解这些代码,你可以深入学习到C语言实现哈希表的具体...
UTHASH 是一个开源的 C 语言库,提供了一种简单且高效的哈希表实现,用于在 C 代码中快速查找和管理数据结构。这个库的主要功能是提供一个宏定义的集合,可以方便地将结构体转化为哈希表,进而进行添加、删除、查找...
该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论是自定义的struct还是基本数据类型,需要注意的是不同类型的key其操作接口方式略有不通。...
根据提供的文件信息,我们可以深入分析C语言中哈希表(Hash Table)的实现方式与具体细节。本篇文章将从以下几个方面展开讨论: 1. **哈希表的基本概念** 2. **哈希函数的设计** 3. **哈希表的创建与管理** 4. **...
本话题主要探讨两种常用的数据结构:双向链表和哈希表,它们在Linux内核以及普通用户态C程序中有广泛的应用。 **双向链表** 双向链表是一种线性数据结构,每个节点包含数据和两个指针,分别指向前一个节点和后一个...
扫描一个C源程序,用Hash表存储该程序中出现的关键字,并统计该程序中的关键字出现的度。用线性探测法解决Hash冲突。设Hash函数为:Hash(Key)=[(Key的首字母序号)*100+(Key的尾字母序号)] Mod 41。关键字39个,参考...
哈希表(Hash Table)是一种数据结构,它通过哈希函数将关键字映射到数组的索引位置,以此实现快速的查找、插入和删除操作。在C语言中实现哈希表,我们需要理解哈希函数的设计、冲突解决策略以及动态扩容等核心概念...
此外,附带的7个Hash验证工具可能是为了方便用户检验MD5值的正确性,它们可能有命令行接口,接受输入的MD5摘要和文件路径,然后比较计算出的MD5值是否一致。 在使用MD5算法时,需要注意其安全性问题。由于MD5碰撞...
1)利用C\C++语言实现DSA算法。 2)DSA中的Hash函数采用SHA算法。 (1)消息填充:因为我们存储的时候是以字节为单位存储的,所以消息的长度(单位:位)一定是 8 的倍数。而我们填充的时候也一定是 8 位、8 位...
通过上述分析,我们可以看到Blizzard的Hash表实现不仅体现了对散列技术的深刻理解,而且还展示了如何利用多个散列值来进一步提高Hash表的性能和准确性。这种技术尤其适用于处理大量数据的情况,能够显著减少冲突的...
总的来说,哈希表是计算机科学中的重要工具,尤其在数据库、缓存、编程语言实现等领域广泛应用。深入理解哈希表的设计和实现,有助于提升我们的算法能力和系统设计水平。通过研究“哈希表设计源码HashList”,我们...
在这个框架中,`createHashTable`用于初始化哈希表,`hashFunction`用于计算哈希码,`insert`、`search`和`deleteEntry`分别对应插入、查找和删除操作。为了实现高效且无冲突的哈希索引,你需要仔细设计哈希函数以...
`hash算法.clw`、`hash算法.cpp`、`hash算法Dlg.cpp`等可能是源代码文件,涉及计算HASH值的实现。`hash算法Dlg.h`和`hash算法.h`可能包含了类定义和函数声明,而`StdAfx.*`文件通常用于Visual Studio项目,处理预...
综上所述,这个C程序实现了一个简单的哈希查找系统,包括了数据结构(链表和哈希表)、哈希函数(基于字符串长度的简单哈希)、插入操作、查找操作以及显示所有记录的功能。虽然这个哈希函数较为简单,但足以展示...
- 在这个C语言实现中,哈希函数可能是一个简单的模运算,例如`hash(key) = key % size`,其中`size`是哈希表的大小。 3. **冲突解决:链地址法**: - 链地址法是为每个数组元素创建一个链表,当新键映射到已有的...