FunctionGHW posted @ 2013年5月12日 15:55 in 数据结构 with tags hash table C 数据结构 , 3576 阅读

散列表(hash table)是一种仅支持 增,删,查 操作的集合,理想情况下, 查找一个元素的期望时间是\(O(1)\),因为我们在散列表中通过关键字key查找value, 就好像在数组中通过下标查找对应的值一样。算法导论上说:"散列表是普通数组概念的推广"。

实现一个散列表有两个比较重要的问题: 构造散列函数(hash function) 和 解决碰撞(collision)问题。 理想的散列函数能够让每个关键字都等可能的映射到表中的所有位置,这样数据在表中的分布是均匀的。 不过实际应用中基本不可能做到,只要能近似的满足这个条件就是个好的散列函数。一般情况下, 我们可以直接使用其他人设计的散列函数,我自己的实现 中用的就是BKDRHash,它不仅实现简单(看两遍后, 随手就能自己写出来),实际性能表现也非常的优秀。因为散列表中的元素数可以大于表的长度, 所以碰撞是不可避免的,解决的方法有链接法,开放寻址法,再散列,我用的是链接法,简单易懂。

接口定义如下,完整的 demo放在Github上,可供参考。 此次单独为每一个节点的key和val指定大小主要是考虑到字符串会方便点,因为字符串的长度可大可小, 不像其他类型有固定大小。

typedef unsigned char BYTE;

typedef struct HashLnkLstNode HashLnkLstNode;
typedef struct Hashtable Hashtable;

struct HashLnkLstNode
    BYTE* key;
    BYTE* val;
    size_t key_size;
    size_t val_size;
    HashLnkLstNode* next;

struct Hashtable
    size_t size; //This is the size of the table, 
                 //which contains all header of the single-linked list;
    size_t elemts_count; // The count can be greater than size;

    HashLnkLstNode** table;

//Create a new hashtable with size of specified value;
Hashtable* new_hashtable(size_t size);
//Get the size of a hashtable;
size_t hashtable_size(const Hashtable* table);
//Get the number of elements contained in the hashtable;
size_t hashtable_elemts_count(const Hashtable* table);
//The hash function;
size_t hashtable_hash(const BYTE* key, size_t key_size);
//Determines whether the hashtable contains a specific element;
int hashtable_contains_key(const Hashtable* table, const BYTE* key, size_t key_size);
//Search the hashtable and return the value with specific key;
BYTE* hashtable_getval(const Hashtable* table, const BYTE* key, size_t key_size);
//Add a new element into the hashtable, if the key has exist in the hashtable, do nothing;
void hashtable_add(Hashtable* table, 
                   const BYTE* key, 
                   size_t key_size, 
                   const BYTE* val, 
                   size_t val_size);
//Remove a specific element from the hashtable;
void hashtable_remove(Hashtable* table, const BYTE* key, size_t key_size);
//Dispose the hashtable;
void hashtable_dispose(Hashtable* table);
//Romove all elements of the hashtable;
void hashtable_empty(Hashtable* table);
Liwovosa 说:
2021年4月13日 16:18

It is an excellent blog, I have ever seen. I found all the material on this blog utmost unique and well written. And, I have decided to visit it again and again. 123movies

Liwovosa 说:
2021年4月13日 21:06

Thanks for picking out the time to discuss this, I feel great about it and love studying more on this topic. It is extremely helpful for me. Thanks for such a valuable help again. online casino

Liwovosa 说:
2021年4月14日 00:39 Wow, this is fascinating reading. I am glad I found this and got to read it. Great job on this content. I liked it a lot. Thanks for the great and unique info. best air fryers in India under 5000
SmithSeo 说:
2021年4月18日 05:04

I read your blog frequently, and I just thought I’d say keep up the fantastic work! It is one of the most outstanding blogs in my opinion. dadu online terpercaya

SmithSeo 说:
2021年4月19日 17:48

Excellent website! I adore how it is easy on my eyes it is. I am questioning how I might be notified whenever a new post has been made. Looking for more new updates. Have a great day! Training Adelaide

jackjohnny 说:
2021年7月05日 22:35

All the contents you mentioned in post is too good and can be very useful. I will keep it in mind, thanks for sharing the information keep updating, looking forward for more posts.Thanks สล็อต

jackjohnny 说:
2021年7月12日 18:40

This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article. 먹튀검증

登录 *

loading captcha image...
or Ctrl+Enter