学步园

字符串 hash算法times33据说很经典，也很简单，就是不断的乘33，nHash = nHash*33 + *key++，没找到什么资料说这个比较好的理由，自己做了个测试，不多说，代码如下，测试环境win32 vc2008

hashmap.h

#ifndef _HASH_MAP_H_<br /> #define _HASH_MAP_H_<br /> typedef unsigned int size_t;<br /> struct hash_map;<br /> struct hash_map *hash_create(size_t size, int (*hash_cmp)(void*, void*),<br /> int (*hash_key)(void*));<br /> int hash_insert(struct hash_map *map, void *key, void *data);<br /> int hash_delete(struct hash_map *map, void *key);<br /> void* hash_value(struct hash_map *map, void *key);<br /> void hash_destroy(struct hash_map *map);<br /> void hash_print(struct hash_map *map);<br /> #endif 

hashmap.c

#include "hashmap.h"<br /> #include <malloc.h><br /> struct hash_node<br /> {<br /> void *key;<br /> void *data;<br /> struct hash_node *next;<br /> };<br /> struct hash_map<br /> {<br /> size_t size;<br /> struct hash_node **hash_list;<br /> int (*hash_cmp)(void*, void*);<br /> int (*hash_key)(void*);<br /> };<br /> struct hash_map *hash_create(size_t size, int (*hash_cmp)(void*, void*),<br /> int (*hash_key)(void*))<br /> {<br /> int i = 0;<br /> struct hash_map *map = (struct hash_map*)malloc(sizeof(struct hash_map));<br /> if(0==map)<br /> return 0;<br /> map->size = size;<br /> map->hash_cmp = hash_cmp;<br /> map->hash_key = hash_key;<br /> map->hash_list = (struct hash_node**)malloc(size*sizeof(struct hash_node*));<br /> if(0==map->hash_list)<br /> return 0;<br /> while(i<map->size){<br /> map->hash_list[i] = 0;<br /> i++;<br /> }<br /> return map;<br /> }<br /> int hash_insert(struct hash_map *map, void *key, void *data)<br /> {<br /> struct hash_node *p;<br /> int hash_key = map->hash_key(key)%map->size;<br /> if(hash_key>map->size)<br /> return -1;<br /> p = map->hash_list[hash_key];<br /> if(0==p)<br /> {<br /> map->hash_list[hash_key] = (struct hash_node*)malloc(sizeof(struct hash_node));<br /> if(0==map->hash_list[hash_key])<br /> return -1;<br /> map->hash_list[hash_key]->key = key;<br /> map->hash_list[hash_key]->data = data;<br /> map->hash_list[hash_key]->next = 0;<br /> }<br /> while(p)<br /> {<br /> if(map->hash_cmp(p->key, key))<br /> p->data = data;<br /> if(0==p->next)<br /> {<br /> p->next = (struct hash_node*)malloc(sizeof(struct hash_node));<br /> if(0==p->next)<br /> return -1;<br /> p->next->key = key;<br /> p->next->data = data;<br /> p->next->next = 0;<br /> p = p->next;<br /> }<br /> p = p->next;<br /> }<br /> return 0;<br /> }<br /> int hash_delete(struct hash_map *map, void *key)<br /> {<br /> struct hash_node *p;<br /> struct hash_node *q;<br /> int hash_key = map->hash_key(key)%map->size;</p> <p> p = map->hash_list[hash_key];<br /> q = map->hash_list[hash_key];<br /> if(hash_key>map->size || 0==p)<br /> return -1;<br /> while(p)<br /> {<br /> if(map->hash_cmp(p->key, key))<br /> {<br /> if(p != q)<br /> q->next = p->next;<br /> free(p);<br /> p = 0;<br /> }<br /> q = p;<br /> p = p->next;<br /> }<br /> return 0;<br /> }<br /> void* hash_value(struct hash_map *map, void *key)<br /> {<br /> int hash_key = map->hash_key(key)%map->size;</p> <p> struct hash_node *p = map->hash_list[hash_key];<br /> if(hash_key>map->size || 0==p)<br /> return 0;<br /> while(p)<br /> {<br /> if(map->hash_cmp(p->key, key))<br /> return p->data;<br /> p = p->next;<br /> }<br /> return 0;<br /> }<br /> void hash_destroy(struct hash_map *map)<br /> {<br /> int i = 0;<br /> struct hash_node *p;<br /> struct hash_node *q;<br /> while(i<map->size)<br /> {<br /> p = map->hash_list[i];<br /> if(p)<br /> {<br /> while(p)<br /> { q = p;<br /> p = p->next;<br /> free(q);<br /> }<br /> }<br /> i++;<br /> }<br /> free(map->hash_list);<br /> free(map);<br /> return;<br /> }<br /> void hash_print(struct hash_map *map)<br /> {<br /> int i = 0;<br /> int count = 0;<br /> struct hash_node *p;<br /> while(i < map->size)<br /> {<br /> p = map->hash_list[i];<br /> while(p)<br /> {<br /> count++;<br /> p = p->next;<br /> }<br /> printf("node %d = %d/n",i, count);<br /> count = 0;<br /> i++;<br /> }<br /> }<br />  

testhashmap.cpp

// hashmap.cpp : 定义控制台应用程序的入口点。<br /> //<br /> #include "stdafx.h"<br /> #include "malloc.h"<br /> #include "stdlib.h"<br /> extern "C"<br /> {<br /> #include "hashmap.h"<br /> }<br /> #include <string.h><br /> int hash_cmp(void *src, void *des)<br /> {<br /> return (0 == strcmp((char*)src, (char*)des));<br /> }<br /> int hash_key(void *key)<br /> {<br /> char *p = (char*)key;<br /> int nhash = 5381;<br /> while(*p)<br /> {<br /> nhash += (nhash << 5) + *p;<br /> p++;<br /> }<br /> return nhash;<br /> }<br /> char *rand_str(char *str, int len)<br /> {<br /> int i;<br /> for(i=0;i<len;++i)<br /> str[i]='A'+rand()%26;<br /> str[++i]='/0';<br /> return str;<br /> }<br /> int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> struct hash_map *map = hash_create(100, hash_cmp, hash_key);<br /> int i = 0;<br /> while (i<10000)<br /> {<br /> int c = rand()%10;<br /> char *s = (char*)malloc(c*sizeof(char));<br /> rand_str(s, c);<br /> hash_insert(map, s, s);<br /> i++;<br /> }<br /> hash_print(map);<br /> hash_destroy(map);<br /> return 0;<br /> }<br />  

通过打印每个节点的字符串个数，显示分布还是比较平衡的