`

HashTable简单实现,使用ELFHash 哈希

 
阅读更多

 

头文件

#ifndef __GHASH_H_
#define __GHASH_H_

#define HASHSIZE 512
typedef struct _Item
{
   char * key;
   char * value;
   struct Item * next;
} Item;

void GHashInit();
Item *  HashInSert(char * key,char * value);
int  HashRemove(char * key);
Item *  HashSearch(char * key);
void FreeGHash();
void PrintGHash();

#endif

 

c文件

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "GHash.h"

static struct Item *hashtab[HASHSIZE];

static void freeItem(Item * item);
static unsigned int _Hash(char *key);
static unsigned int _ELFHash(char *str);

void GHashInit()
{
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	  	hashtab[i]=NULL;
     }
}

Item *  HashInSert(char * key,char * value)
{
 	 Item * np;
 	 unsigned int hashval;
 	 if((np=HashSearch(key))==NULL)
 	 {
         np=(Item *)malloc(sizeof(Item));
         if(NULL==np || NULL ==(np->key = strdup(key))
		       || NULL ==(np->value = strdup(value)) )
         {
             return NULL;
         }
         hashval = _Hash(key);
         np->next = (Item *)hashtab[hashval];
         hashtab[hashval] = np;
     }
     else
     {
	  	 free(np->value);
	  	 if((np->value=strdup(value))== NULL)
	  	 {
		    return NULL;
         }
 	 }
 	 return np;
}
int  HashRemove(char * key)
{
}

Item *  HashSearch(char * key)
{
    Item  *np;

    for(np = (Item *)hashtab[_Hash(key)];
        np != NULL;
        np = np->next)
      if(strcmp(key,np->key) == 0)
           return np;
    return NULL;
}

void FreeGHash()
{
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	     if(hashtab[i]!=NULL)
	     {
		    Item * tmp;
		    Item * deln;
		    for(tmp=hashtab[i]; tmp!=NULL; tmp=hashtab[i])
		    {
			     hashtab[i]=tmp->next;
			     freeItem(tmp);
			}
		 }
     }
}
void PrintGHash()
{
 	 printf("Print Hash:\n");
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	     if(hashtab[i] !=NULL )
	     {
		    printf("%d---",i);
		    Item * tmp;
		    for(tmp=hashtab[i]; tmp!=NULL; tmp=tmp->next)
		    {
			     printf("%s:%s;",tmp->key,tmp->value);
			}
			printf("\n");
		 }
     }
}

static unsigned int _Hash(char *key)
{
    return _ELFHash(key)%HASHSIZE;
}

// ELF Hash Function
static unsigned int _ELFHash(char *str)
{
       unsigned int hash = 0;
       unsigned int x = 0;

       while (*str)
      {
           hash = (hash << 4) + (*str++);//hash左移4位,当前字符ASCII存入hash
           if ((x = hash & 0xF0000000L) != 0)
           {//如果最高的四位不为0,则说明字符多余7个,如果不处理,再加第九个字符时,第一个字符会被移出,因此要有如下处理。

           //该处理,如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位,否则会影响5-31位,因为C语言使用的算数移位
           hash ^= (x >> 24);
           //清空28-31位。
           hash &= ~x;
           }
       }

      //返回一个符号位为0的数,即丢弃最高位,以免函数外产生影响。(我们可以考虑,如果只有字符,符号位不可能为负)
     return (hash & 0x7FFFFFFF);

}

static void freeItem(Item * item)
{
   free(item->key);
   free(item->value);
   free(item);
}

 

 

 使用代码

 

Item * np;
  
  GHashInit();
  
  if((np=HashInSert("123","abc"))==NULL)
  {
     printf("Insert %s:%s wrong\n","123","abc");
  }
  PrintGHash();
  if((np=HashInSert("456","def"))==NULL)
     printf("Insert %s:%s wrong\n","456","def");
  PrintGHash();
  
  if((np=HashSearch("123")) ==NULL)
  {
		printf("not find 123\n");
  }
  printf("find 123:%s\n",np->value);
  
  FreeGHash();
  PrintGHash();

  

 

 

说明:

 HashInSert 当哈希表中存在了对应的Key值时,则使用新插入的Value替换以前的Value,即覆盖模式类型

 

分享到:
评论
2 楼 yiranwuqing 2012-03-30  
deepfuture 写道
关于字符串hash,我刚看了一下lucene的算法,非常不错,你可以看下这里
不过是用JAVA实现的
http://deepfuture.iteye.com/blog/1462184


hash的处理函数稍有不同,现有多种哈希算法,效果都不错
1 楼 deepfuture 2012-03-26  
关于字符串hash,我刚看了一下lucene的算法,非常不错,你可以看下这里
不过是用JAVA实现的
http://deepfuture.iteye.com/blog/1462184

相关推荐

    哈希表hashtable实现

    在本篇文章中,我们将深入探讨哈希表的实现,特别是基于C语言的简单实现,参考文件"hashtable.c"和"hashtable.h"。 1. 哈希函数:哈希表的核心是哈希函数,它将输入(键或关键字)转换为数组索引。一个好的哈希函数...

    HashTable_Array.rar_哈希函数

    哈希表(Hash Table)是一种数据结构,它通过哈希函数将键(Key)映射到数组的索引位置,从而实现快速查找、插入和删除操作。哈希表的效率高在于它通常可以在常数时间复杂度内完成这些操作,这在处理大量数据时尤为...

    哈希表 Hashtable的操作使用

    在.NET Framework中,`Hashtable`类是实现哈希表的一个经典示例。它支持键值对存储,并提供了多种方法来操作这些键值对。 #### 哈希表的常用操作 1. **添加元素**:使用`Add`方法可以向哈希表中添加新的键值对。...

    使用哈希表Hashtable填充ListBox

    在IT行业中,哈希表(HashTable)是一种常用的数据结构,它提供了一种高效的方式来存储和检索数据。在.NET框架中,`Hashtable`是System.Collections命名空间下的一个类,它实现了键值对(Key-Value Pair)存储,允许...

    哈希表-使用C++实现的哈希表-HashTable.zip

    在"哈希表_使用C++实现的哈希表_HashTable"这个压缩包中,很可能包含了用C++实现的哈希表源代码,可以作为学习和参考。源代码通常会包括哈希函数的定义、插入、查找和删除操作的实现,以及处理哈希冲突的策略。 ...

    哈希表-使用C语言实现哈希表数据结构-HashTable.zip

    5. **查找操作**:查找一个元素时,同样使用哈希函数找到对应的索引,然后遍历该索引处的链表,比较每个节点的键与目标键是否匹配。匹配则返回节点,否则返回未找到。 6. **删除操作**:删除元素需要找到目标键的...

    HashTable的java实现

    在Java编程语言中,哈希表(HashTable)是一种常见的数据结构,它提供了高效的数据存储和检索功能。哈希表基于哈希函数将键(Key)映射到数组的索引位置,通过键值对(Key-Value Pair)来存储数据。这种数据结构允许...

    简单HashTable c实现

    哈希表(HashTable)是一种常见的数据结构,它通过哈希函数将键(Key)映射到数组的索引位置,从而实现快速查找、插入和删除操作。在C语言中实现哈希表,需要理解哈希函数的设计、冲突解决策略以及数据结构的组织...

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

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

    哈希表的设计与实现C语言

    哈希表是一种高效的数据结构,它通过特定的算法——哈希函数,将任意大小的键(key)映射到一个固定大小的数组中,从而实现快速查找、插入和删除操作。在C语言中,实现哈希表需要理解其基本原理,并掌握如何利用...

    实例5 哈希表(Hashtable)和枚举器

    以下是一个简单的使用`Hashtable`和枚举器的例子: ```java import java.util.*; public class HashTableExample { public static void main(String[] args) { // 创建一个哈希表 Hashtable, Integer&gt; table = ...

    hash code 一种常用的哈希算法

    `Hashtable`类是Java中的一种早期集合框架实现,它使用哈希表来存储键值对。哈希函数在`Hashtable`中起到了关键作用,它负责计算对象的哈希码,以便快速定位数据。`Hashtable`内部通过键的哈希码来决定其在数组中的...

    哈希表-使用Java开发的哈希表-HashTable.zip

    在Java中,`HashTable`是早期版本(Java 1.0)提供的一种线程安全的哈希表实现。尽管现在已经被`HashMap`所替代,但理解`HashTable`的工作原理和特性仍然对深入理解Java集合框架以及数据结构有重要意义。 哈希表的...

    哈希表的C简单实现

    哈希表是一种高效的数据结构,...以上就是哈希表的C语言简单实现,包括了创建、销毁、清空、插入、删除、查询和计数等基本操作。实际应用中,还需要考虑哈希函数的设计、哈希表动态扩容等问题,以提高性能并减少冲突。

    哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现

    4. 插入元素:使用哈希函数找到插入位置,处理冲突。 ```c void insert(HashTable* hashTable, int key, void* value) { int index = hashFunction(key, hashTable-&gt;size); HashNode* newNode = (HashNode*)malloc...

    通用型哈希表HashTableT

    哈希表(Hash Table),又称为散列表,是一种数据结构,它通过关联键(Key)与值(Value)实现高效的数据查找、插入和删除操作。在计算机科学中,哈希表是实现关联数组的一种常见方法,它利用了“哈希函数”将键转化...

    C# .net HashTable

    `HashTable`类是基于哈希表数据结构实现的,这使得它能够通过键(key)来快速查找值(value)。在本文中,我们将深入探讨`HashTable`的各个方面,包括它的特点、使用方法、操作以及与其他数据结构的比较。 1. **...

    hash_src.zip_c hashtable_hash_hashtable

    哈希表(Hash Table)是一种数据结构,它通过使用哈希函数将键(Key)映射到一个数组的特定位置来存储和检索数据,提供快速的查找、插入和删除操作。在C语言中,实现哈希表需要考虑的关键点包括哈希函数的选择、解决...

    哈希表(HashTable)C++实现.docx

    这是因为`std::unordered_map`内部使用哈希函数来确定每个键的位置,从而避免了基于键排序所带来的额外开销。 #### 三、基本操作 下面我们将详细介绍`std::unordered_map`的基本操作及其在C++中的实现方式。 ####...

    hashtable:C语言中的异步哈希表服务器

    具有文本协议的简单异步哈希表服务器。 该项目仅用于学习目的。 特征: 带epoll的异步TCP服务器 简单文本协议 具有打开地址的哈希表(双哈希) 随机素数生成的通用哈希算法 霍纳法则的字符串哈希 当填充率&gt; = ...

Global site tag (gtag.js) - Google Analytics