`
abruzzi
  • 浏览: 452982 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

C实现的Hash表

阅读更多

Hash表这种数据结构在java中是原生的一个集合对象,在实际中用途极广,主要有这么几个特点:

  1. 访问速度快
  2. 大小不受限制
  3. 按键进行索引,没有重复对象
  4. 用字符串(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*!= '\0';s++)
            hashval 
= *+ 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;
}

很简单,只有两个外部接口,

  1. install(key, value),用来插入一个新的节点
  2. 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*!= '\0';s++)
            hashval 
= *+ 31 * hashval;
    
return hashval % HASHSIZE;
}

 

这里的31并非随意,乃是一个经验值,选取它的目的在于减少冲突,当然,hash冲突这个问题是不能根本避免的。这里只是一个人们在测试中发现的可以相对减少hash冲突的一个数字,可能以后会发现更好的数值来。

分享到:
评论

相关推荐

    linux下C实现的哈希表

    用C实现的哈希表 int hash_insert(Hash* * hp,int data)//返回0表示成功 { if((*hp) == NULL)return 1; if(((*hp)-&gt;num)==14) { printf("hash full\n"); return 1;//哈希表满了 } if((*hp)-&gt;pNode[KEY(data...

    c语言hash表源码

    `hash.c`通常包含了哈希表的函数实现,而`hash.h`则包含对外的头文件,定义了哈希表的数据结构和相关的接口函数。 在`hash.h`中,可能会定义如下的数据结构: ```c typedef struct HashNode { void* key; void* ...

    C语言实现hash算法

    本项目是用C语言实现的哈希算法,包括SHA256、SHA384和SHA512三种不同的哈希函数,这些函数是SHA-2(Secure Hash Algorithm 2)家族的一部分。 SHA-2是由美国国家安全局(NSA)设计的,包含了多种不同长度的哈希...

    hash算法C代码实现

    哈希(Hash)算法在计算机科学中扮演着重要的角色,特别...同时,为了处理碰撞,可以结合链地址法、开放寻址法或者双重哈希等方法实现哈希表。在压缩包中的`hash`文件可能包含了更多不同哈希函数的实现,供学习和参考。

    hash表C语言实现

    在压缩包文件"C-hash"中,很可能包含了实现上述功能的C语言源代码,包括哈希表结构定义、哈希函数、冲突解决机制以及插入、查找和删除操作的函数。通过阅读和理解这些代码,你可以深入学习到C语言实现哈希表的具体...

    uthash开源的hash函数实现

    UTHASH 是一个开源的 C 语言库,提供了一种简单且高效的哈希表实现,用于在 C 代码中快速查找和管理数据结构。这个库的主要功能是提供一个宏定义的集合,可以方便地将结构体转化为哈希表,进而进行添加、删除、查找...

    C开源hash代码uthash

    该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论是自定义的struct还是基本数据类型,需要注意的是不同类型的key其操作接口方式略有不通。...

    c语言hash table的实现

    根据提供的文件信息,我们可以深入分析C语言中哈希表(Hash Table)的实现方式与具体细节。本篇文章将从以下几个方面展开讨论: 1. **哈希表的基本概念** 2. **哈希函数的设计** 3. **哈希表的创建与管理** 4. **...

    双向链表与hash表

    本话题主要探讨两种常用的数据结构:双向链表和哈希表,它们在Linux内核以及普通用户态C程序中有广泛的应用。 **双向链表** 双向链表是一种线性数据结构,每个节点包含数据和两个指针,分别指向前一个节点和后一个...

    利用Hash技术统计C源程序中关键字的频度

    扫描一个C源程序,用Hash表存储该程序中出现的关键字,并统计该程序中的关键字出现的度。用线性探测法解决Hash冲突。设Hash函数为:Hash(Key)=[(Key的首字母序号)*100+(Key的尾字母序号)] Mod 41。关键字39个,参考...

    C语言实现的Hash哈希表

    哈希表(Hash Table)是一种数据结构,它通过哈希函数将关键字映射到数组的索引位置,以此实现快速的查找、插入和删除操作。在C语言中实现哈希表,我们需要理解哈希函数的设计、冲突解决策略以及动态扩容等核心概念...

    Hash-MD5算法(C语言实现,附带Hash验证工具)

    此外,附带的7个Hash验证工具可能是为了方便用户检验MD5值的正确性,它们可能有命令行接口,接受输入的MD5摘要和文件路径,然后比较计算出的MD5值是否一致。 在使用MD5算法时,需要注意其安全性问题。由于MD5碰撞...

    实现数字签名算法(DSA),Hash算法的实现C语言

    1)利用C\C++语言实现DSA算法。 2)DSA中的Hash函数采用SHA算法。 (1)消息填充:因为我们存储的时候是以字节为单位存储的,所以消息的长度(单位:位)一定是 8 的倍数。而我们填充的时候也一定是 8 位、8 位...

    打造最快的Hash表(和Blizzard的对话)

    通过上述分析,我们可以看到Blizzard的Hash表实现不仅体现了对散列技术的深刻理解,而且还展示了如何利用多个散列值来进一步提高Hash表的性能和准确性。这种技术尤其适用于处理大量数据的情况,能够显著减少冲突的...

    哈希表设计源码HashList

    总的来说,哈希表是计算机科学中的重要工具,尤其在数据库、缓存、编程语言实现等领域广泛应用。深入理解哈希表的设计和实现,有助于提升我们的算法能力和系统设计水平。通过研究“哈希表设计源码HashList”,我们...

    HASH 索引——用C语言实现

    在这个框架中,`createHashTable`用于初始化哈希表,`hashFunction`用于计算哈希码,`insert`、`search`和`deleteEntry`分别对应插入、查找和删除操作。为了实现高效且无冲突的哈希索引,你需要仔细设计哈希函数以...

    PE导入表-函数列表-HASH值

    `hash算法.clw`、`hash算法.cpp`、`hash算法Dlg.cpp`等可能是源代码文件,涉及计算HASH值的实现。`hash算法Dlg.h`和`hash算法.h`可能包含了类定义和函数声明,而`StdAfx.*`文件通常用于Visual Studio项目,处理预...

    Hash查找程序代码的C实现

    综上所述,这个C程序实现了一个简单的哈希查找系统,包括了数据结构(链表和哈希表)、哈希函数(基于字符串长度的简单哈希)、插入操作、查找操作以及显示所有记录的功能。虽然这个哈希函数较为简单,但足以展示...

    用C语言实现一个简单的哈希表(hash table)

    - 在这个C语言实现中,哈希函数可能是一个简单的模运算,例如`hash(key) = key % size`,其中`size`是哈希表的大小。 3. **冲突解决:链地址法**: - 链地址法是为每个数组元素创建一个链表,当新键映射到已有的...

Global site tag (gtag.js) - Google Analytics