`
varsoft
  • 浏览: 2501624 次
  • 性别: Icon_minigender_1
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

[转]libhash中的哈希函数

阅读更多


随便贴一个libhash中的hash函数,写的貌似不错,贴出来玩玩。

hash.h

/*
*AustralianPublicLicenceB(OZPLB)
*
*Version1-0
*
*Copyright(c)2004NationalICTAustralia
*
*Allrightsreserved.
*
*Developedby:Embedded,Real-timeandOperatingSystemsProgram(ERTOS)
*NationalICTAustralia
*
http://www.ertos.nicta.com.au
*/

#ifndef_HASH_H
#define_HASH_H

#include
<stdint.h>

structhashtable{
structhashentry**table;
unsigned
intsize;
structhashentry*spares;
};

structhashentry{
structhashentry*next;
uintptr_tkey;
void*value;
};

structhashtable*hash_init(unsignedintsize);
voidhash_free(structhashtable*tablestruct);
uintptr_thash_hash(uintptr_tkey);
void*hash_lookup(structhashtable*tablestruct,uintptr_tkey);
inthash_insert(structhashtable*tablestruct,uintptr_tkey,void*value);
voidhash_remove(structhashtable*tablestruct,uintptr_tkey);

#endif/*!_HASH_H*/

hash.c

#include<stdint.h>
#include
<stdlib.h>
#include
<assert.h>

#include
"hash.h"

structhashtable*
hash_init(unsigned
intsize)
{
structhashtable*tablestruct;
intcounter;

/*Ourhashfunctiononlyworkswithpower-of-2bucketsizesforspeed.*/
assert((size
&(size-1))==0);

tablestruct
=malloc(sizeof(structhashtable));assert(tablestruct);
if(!tablestruct){
returnNULL;
}
tablestruct
->table=malloc(size*sizeof(structhashentry*));
if(!tablestruct->table){
returnNULL;
}
for(counter=0;counter<size;counter++){
tablestruct
->table[counter]=NULL;
}
assert(tablestruct
->table);
tablestruct
->size=size;
tablestruct
->spares=NULL;

returntablestruct;
}

/*Refhttp://www.concentric.net/~Ttwang/tech/inthash.htm*/
uintptr_t
hash_hash(uintptr_tkey)
{
#if(UINTPTR_MAX==UINT32_MAX)
key
+=~(key<<15);
key
^=(key>>10);
key
+=(key<<3);
key
^=(key>>6);
key
+=~(key<<11);
key
^=(key>>16);
#elif(UINTPTR_MAX==UINT64_MAX)
key
+=~(key<<32);
key
^=(key>>22);
key
+=~(key<<13);
key
^=(key>>8);
key
+=(key<<3);
key
^=(key>>15);
key
+=~(key<<27);
key
^=(key>>31);
#else
#errorunsupportedwordsize
#endif
//printf("newkeyis%d ",key);
returnkey;
}

void*
hash_lookup(
structhashtable*tablestruct,uintptr_tkey)
{
uintptr_thash;
structhashentry*entry;

hash
=hash_hash(key)&(tablestruct->size-1);
for(entry=tablestruct->table[hash];entry!=NULL;entry=entry->next){
if(entry->key==key){
returnentry->value;
}
}
returnNULL;
}

/*Addthekeytothehashtable.Assumesthekeyisnotalreadypresent.*/
int
hash_insert(
structhashtable*tablestruct,uintptr_tkey,void*value)
{
uintptr_thash;
structhashentry*entry;

hash
=hash_hash(key)&(tablestruct->size-1);
//printf("bucketis%d ",hash);

entry
=malloc(sizeof(structhashentry));
if(!entry){
return-1;
}
entry
->key=key;
entry
->value=value;
entry
->next=tablestruct->table[hash];

tablestruct
->table[hash]=entry;
return0;
}

/*Removesthekeyfromthehashtable.Doesnotsignalanerrorifthekey
*wasnotpresent.
*/
void
hash_remove(
structhashtable*tablestruct,uintptr_tkey)
{
uintptr_thash;
structhashentry*entry,*tmpentry;

hash
=hash_hash(key)&(tablestruct->size-1);
entry
=tablestruct->table[hash];
/*Ifthisisthefirstentrythenitneedsspecialhandling.*/
if(entry&&entry->key==key){
tmpentry
=entry->next;
free(entry);
tablestruct
->table[hash]=tmpentry;
}
else{
while(entry){
if(entry->next&&entry->next->key==key){
tmpentry
=entry->next;
entry
->next=entry->next->next;
free(tmpentry);
break;
}
entry
=entry->next;
}
}
}

hash_free.c

#include<stdint.h>
#include
<stdlib.h>

#include
"hash.h"

void
hash_free(
structhashtable*tablestruct)
{
intcounter;
structhashentry*entry,*prev;

/*Needtofreebucketsandtablestructandeveryitemineverychain*/
for(counter=0;counter<tablestruct->size;counter++){
entry
=tablestruct->table[counter];
while(entry){
prev
=entry;
entry
=entry->next;
free(prev);
}
}
free(tablestruct
->table);
free(tablestruct);
}

来源:http://ertos.nicta.com.au/software/kenge/libhash/devel/

更多结果:http://www.google.cn/search?complete=1&hl=zh-CN&q=libhash&meta=

分享到:
评论

相关推荐

    哈希函数的应用(数据结构课程设计)

    在本文中,我们将探讨哈希函数的应用的一些方面,并设计一个基于哈希函数的查找系统。 哈希函数的定义 哈希函数是一种将输入值(通常是字符串或数字)映射到固定长度的输出值的函数。哈希函数的输出值称为哈希值或...

    一些经典简单的哈希函数

    哈希函数是计算机科学中的一种常用技术,用于将输入数据转换为固定长度的输出,即哈希值。哈希函数的主要应用场景包括哈希表、数据压缩、数字签名、身份验证等。 在给定的文件中,我们可以看到多种经典的哈希函数,...

    一些有关哈希函数的随记

    这篇随记将探讨哈希函数的基本概念、性质以及在实际应用中的重要性。 哈希函数,也称为散列函数,是一种特殊的算法,它将任意长度的输入(也称为预映射或消息)转化为固定长度的输出,这个输出通常被称为哈希值或...

    常用哈希函数结构 数据结构

    在IT领域,特别是数据结构与算法中,哈希函数扮演着至关重要的角色。它们被广泛应用于各种场景,如数据库索引、密码存储、缓存管理等,以提高数据检索的速度和效率。本文将深入探讨几种常用的哈希函数,包括SDBMHash...

    哈希函数与数据完整性

    - **带密钥的哈希函数**:这类函数在计算过程中会引入一个密钥,通常用于安全性更高的场景,如消息认证码(Message Authentication Code, MAC)。 从功能上来看,哈希函数可以分为: - **改动检测码(MDC)**:主要...

    字符串哈希函数设计

    字符串哈希函数是一种在计算机科学中用于快速查找和比较字符串的有效方法。它的核心思想是将一个字符串转换为一个整数值,这个数值可以作为字符串的一种紧凑表示,便于存储、比较和查找。在本实验中,我们将关注如何...

    从标准假设中保留属性的哈希函数_Property-Preserving Hash Functions from Standard

    《从标准假设中保留属性的哈希函数》这篇论文探讨了一种特殊类型的哈希函数——属性保留哈希函数(Property-Preserving Hash Functions),这种函数能够在压缩输入数据的同时,保持某些特定属性,允许在仅知道哈希值...

    散列表(哈希函数)电话簿通讯录

    哈希函数设计的目标是确保不同的输入会产生不同的哈希值,尽管在实际应用中可能会出现哈希冲突,即不同的输入产生了相同的哈希值。当冲突发生时,有多种解决策略,如开放寻址法、链地址法或再哈希法。 在这个电话簿...

    哈希函数&MD5.doc

    ### 哈希函数及其应用 #### 一、哈希函数概述 哈希函数作为一种重要的密码...然而,随着技术的发展,一些哈希函数(如MD5)的安全性受到了挑战,因此在实际应用中选择更加安全的哈希算法(如SHA系列)是非常必要的。

    易语言PHP哈希函数

    尽管在现代哈希函数中已不再常用,但学习和理解HashPJW有助于我们了解哈希函数的基本原理。 在PHP中,可以使用`hash()`函数来计算哈希值,它支持多种算法,包括MD5、SHA-1、CRC32等。而使用易语言实现PHP哈希函数,...

    毕业论文:哈希函数的构造方法

    在哈希函数的构造方法中,有多种不同的方法可以选择,每种方法都有其特点和优缺。下面我们将对哈希函数的构造方法进行详细的介绍。 1. 直接定址法 直接定址法是一种简单的哈希函数构造方法,它的思想是将输入字符...

    哈希函数和时序关联规则

    ### 哈希函数与时序关联规则 #### 引言 随着信息技术的快速发展和数据库技术的广泛应用,数据挖掘作为一种从海量数据中提取有价值信息的技术,已成为研究热点。特别是关联规则挖掘,它能够揭示出数据之间的有趣关系...

    数据结构课程设计-哈希函数的应用

    哈希函数的目的是将关键字轉换为哈希地址,以便在哈希表中存储和查找元素。 2. 构造哈希表 哈希表是通过哈希函数将关键字映射到数组中的一个数据结构。构造哈希表需要选择合适的哈希函数和解决冲突的方法。在本...

    用C语言实现常用的字符串哈希函数

    用C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等

    易语言源码PHP哈希函数易语言源码.rar

    《易语言源码PHP哈希函数解析》 在IT领域,源码是程序的灵魂,它揭示了软件运行的...在使用过程中,我们应该深入理解哈希函数的特性,注意其安全性问题,并根据实际需求选择合适的哈希算法,以实现高效、安全的编程。

    用C语言实现MD5哈希函数

    用C语言实现MD5哈希函数,它是将文件的每一行进行MD5加密,输出一个128位的哈希值。

    完美哈希函数的实现

    用C++实现的完美哈希函数,打印C语言的32个关键字的哈希值,并且判断所输入的字符串是否为关键字

    哈希函数和数字签名概述.pdf

    哈希函数和数字签名是信息安全中两个重要的概念。哈希函数是一种将任意长度的消息映射成一个较短的定长输出报文的函数,而数字签名则是一种使用私钥对消息进行 签名的方式,以证明消息的真实性和完整性。 哈希函数...

Global site tag (gtag.js) - Google Analytics