设定哈希函数的方法通常有直接定址法、数字分析法、平方取中法、折叠法、除留取余法、随机数法等等。这里我们采用的是折叠法来计算哈希值。设关键字的类型为int,占4个字节。我们对这4个字节的数进行折叠相加,计算出这个关键字的哈希值。此哈希函数如下:
char hashtable_hashcode(int key) { char h_key = 0xff & key; h_key += 0xff & (key >> 8); h_key += 0xff & (key >> 16); h_key += 0xff & (key >> 24); return h_key; }
经过哈希函数计算后的值也有可能出现冲突,例如使用哈希函数对于1和256这两个关键字求值,结果均为1。解决哈希值冲突的办法也有很多,我们这里采用线性表来存放冲突哈希值的数据。对于1、2、3、4、256、257、258、259这8个关键字来说,它们的存储方式如下:
下面关于线性表的实现我们在前面的章节已经完成,这里不再叙述。我们来实现哈希表的代码:
//哈希表大小 #define INIT_SIZE (0xff) //哈希表 typedef struct s_hashtable { //线性表 s_list *list; } s_hashtable; bool hashtable_init(s_hashtable *ht, void (*free_data)()) { if (ht == null) { return false; } ht->list = (s_list *) malloc(sizeof(s_list) * INIT_SIZE); for (int i = 0; i < INIT_SIZE; i++) { init_list(&ht->list[i], free_data); } return true; } //销毁哈希表 bool hashtable_destory(s_hashtable *ht) { for (int i = 0; i < INIT_SIZE; i++) { //销毁线性表 destroy_list(&ht->list[i]); } free(ht->list); return true; } //插入数据到哈希表 bool hashtable_push(s_hashtable *ht, int key, void *value) { //计算哈希值 char h_key = hashtable_hashcode(key); //插入数据 return list_insert(&ht->list[h_key], key, value); } //移除一个数据 bool hashtable_remove(s_hashtable *ht, int key) { //计算哈希值 char h_key = hashtable_hashcode(key); //移除数据 return list_delete(&ht->list[h_key], key); } //取得数据 void* hashtable_get(s_hashtable *ht, int key) { //计算哈希值 char h_key = hashtable_hashcode(key); //取得数据 return list_get(&ht->list[h_key], key); } //计算哈希值 char hashtable_hashcode(int key) { char h_key = 0xff & key; h_key += 0xff & (key >> 8); h_key += 0xff & (key >> 16); h_key += 0xff & (key >> 24); return h_key; }
写一个main函数来使用这个哈希表:
#include "hashtable.h" int main(int argc, char **args) { s_hashtable ht; hashtable_init(&ht, null); int t1 = 1111; int t2 = 2222; int t3 = 3333; int t4 = 4444; int t5 = 5555; hashtable_push(&ht, 1, &t1); hashtable_push(&ht, 2, &t2); hashtable_push(&ht, 3, &t3); hashtable_push(&ht, 4, &t4); hashtable_push(&ht, 256, &t5); printf("%d\n", *(int *) hashtable_get(&ht, 1)); printf("%d\n", *(int *) hashtable_get(&ht, 2)); printf("%d\n", *(int *) hashtable_get(&ht, 3)); printf("%d\n", *(int *) hashtable_get(&ht, 4)); printf("%d\n", *(int *) hashtable_get(&ht, 256)); hashtable_destory(&ht); return 0; }
运行结果:
1111 2222 3333 4444 5555
本例代码:
code path chapter.07/e.g.7.6/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号