数据结构 -- 散列表

散列表作为一种能够提供高效插入，查找，删除 以及遍历的数据结构，被应用在很多不同的存储组件之中。
就像rocksdb中的hashskiplist，redis的有序集合，java的 LinkedHashMap 等 都是一些非常有特色的核心数据结构，来提供线上高效的数据操作能力。

本节对工业级散列表的基本实现 探索一番，希望加深自己对存储产品设计理念的理解。

工业级的散列表需要具有如下能力：

1. 初始大小
   散列表的初始大小，刚开始的时候需要拥有一定量的存储空间，根据实际应用情况可以通过设置散列表的初始大小，从而减少动态扩容的次数，依次提升性能。

2. 装载因子 和 动态扩容
   最大装载因子默认是0.75， 即散列表中已存储的元素个数达到了总大小的0.75，则开始扩容

3. 散列冲突的解决
   根据实际情况选择通用的两种方案： 开放寻址法 和 链表法
   开放寻址法：使用数组进行底层存储，出现冲突时重新探测数据中的空闲位置，进一步插入，该方法能够利用CPU缓存功能进行加速，但是比较耗费内存空间。
   基本过程如下:
   
   插入key3的时候hash函数计算的散列值也为3，和key2的散列值冲突，那么将向key2之后插入，但是发现key2之后没有空间了，则跳到数据开头重新遍历找到第一个空闲的位置插入。

   链表法：将相同散列值的元素放入到相同的槽位，每一个槽位用链表管理相同hash值的元素
   该方法能够高效利用内存（链表节点生成新节点的时候才会分配空间），只是对CPU缓存不太友好，地址之间并不是连续的，CPU缓存基本不能生效。（这里可以通过一些有序的数据结构进行优化-- 跳表和红黑树）
   

   插入的key3有和key1相同的散列值，则将key3直接插入到key1对应的bucket链表末尾，实际过程需要有序，所以这里插入到hashtab[2]的时候还需要找到对应的链表节点前驱。

4. 散列函数
   散列函数的设计不追求复杂，但是需要高效，计算但散列值要分布均匀。
   java的LinkedHashMap的散列函数设计如下:

   int hash(Object key) {int h = key.hashCode();return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
   }
   

   其中，hashCode()返回的是Java对象的hash code。比如String类型的对象的hashCode()就是下面这样:

   public int hashCode() {int var1 = this.hash;if(var1 == 0 && this.value.length > 0) {char[] var2 = this.value;for(int var3 = 0; var3 < this.value.length; ++var3) {var1 = 31 * var1 + var2[var3];}this.hash = var1;}return var1;
   }
   

   设计的过程中尽可能保证数据的随机性，就像手机号的后四位 一般是随机均匀分布，这样取用数据的过程即可作为hash函数。

通过以上四点的设计，我们基本能够完成一个工业级的散列表实现，再做一个总结，工业级的散列表的特性：

• 支持快速的查询、插入、删除操作;
• 内存占用合理，不能浪费过多的内存空间;
• 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况

工业级散列表的设计实现思路：

• 设计一个合适的散列函数;
• 定义装载因子阈值，并且设计动态扩容策略
• 选择合适的散列冲突解决方法

通过以上设计，使用C语言编写一个简单的工业级散列表实现如下，散列冲突是通过链表解决的

listhash.h

#ifndef __HASHTAB_H__
#define __HASHTAB_H__typedef struct _hashtab_node
{void * key;void * data;struct _hashtab_node *next;
}hashtab_node;typedef struct _hashtab
{hashtab_node **htables; /*哈希桶*/int size;              /*哈希桶的最大数量*/int nel;               /*哈希桶中元素的个数*/int (*hash_value)(struct _hashtab *h,const void *key); /*哈希函数*/int (*keycmp)(struct _hashtab*h,const void *key1,const void *key2);/*哈希key比较函数，当哈希数值一致时使用*/void (*hash_node_free)(hashtab_node *node);
}hashtab;#define HASHTAB_MAX_NODES  (0xffffffff)typedef int (*hash_key_func)(struct _hashtab *h,const void *key); /*哈希函数*/
typedef int (*keycmp_func)(struct _hashtab*h,const void *key1,const void *key2);/*哈希key比较函数，当哈希数值一致时使用*/
typedef void (*hash_node_free_func)(hashtab_node *node);
/*根据当前结构体元素的地址，获取到结构体首地址*/
#define offsetof(TYPE,MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container(ptr,type,member) ({\const typeof( ((type *)0)->member) *__mptr = (ptr);\(type *) ( (char *)__mptr - offsetof(type,member));})hashtab * hashtab_create(int size,hash_key_func hash_value,keycmp_func keycmp,hash_node_free_func hash_node_free);
void *hashtab_expand(hashtab*h);
void hashtab_destory(hashtab *h);
int hashtab_insert(hashtab * h,void *key,void *data);
hashtab_node *hashtab_delete(hashtab *h, void *key);
void *hashtab_search(hashtab*h,void *key);#endif

listhash.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include"listhash.h"/* 创建 */
hashtab *hashtab_create(int size,hash_key_func hash_value,keycmp_func keycmp,hash_node_free_func hash_node_free) 
{hashtab *h = NULL;int hash_num = 0; // 初始化hash元素的个数if(size < 0 || hash_value == NULL || keycmp == NULL) {return NULL;}h = (hashtab *)malloc(sizeof(hashtab));if(h == NULL) {return NULL;}h->htables = (hashtab_node**)malloc(size * sizeof(hashtab_node*));if(h->htables == NULL) {return NULL;}h->size = size;h->hash_value = hash_value;h->keycmp = keycmp;h->hash_node_free = hash_node_free;h->nel = 0;for(;hash_num < size; hash_num++) {h->htables[hash_num] = NULL;}return h;
}/* 销毁 */
void hashtab_destory(hashtab *h) 
{int i = 0;hashtab_node *cur = NULL;hashtab_node *tmp = NULL;if(h == NULL) {return;}for (;i < h->size; ++i) {cur = h->htables[i];while(cur != NULL) {tmp = cur;cur = cur->next;h->hash_node_free(tmp);}}free(h->htables);free(h);return ;
}/* 插入 */
int hashtab_insert(hashtab *h ,void *key, void *data) {if(h == NULL || key == NULL || data == NULL) {return -1;}unsigned int hvalue = 0;hashtab_node *cur = NULL;hashtab_node *prev = NULL;hashtab_node *tmp = NULL;hvalue = h->hash_value(h,key);cur = h->htables[hvalue];/* hashtable 中的元素在hash链上也是有序的 */while(cur != NULL && (h->keycmp(h,key,cur->key) > 0)) {// 找到待插入key的前驱节点prev = cur;cur = cur->next;}if(cur != NULL && (h->keycmp(h, key, cur->key) == 0)) { // 当前key存在return 1;}tmp = (hashtab_node *)malloc(sizeof(hashtab_node));if(tmp == NULL) {return -1;}tmp->key = key;tmp->data = data;if(prev == NULL) {tmp->next = h->htables[hvalue];h->htables[hvalue] = tmp;}else {tmp->next = prev->next;prev->next = tmp;}h->nel ++;// if(h->size * 3 / 4 <= h->nel) {//    hashtab_expand(h);// }return 0;
}/* 删除 */
hashtab_node *hashtab_delete(hashtab *h, void *key) 
{if(h == NULL || key == NULL) {return NULL;}unsigned int hvalue = 0;hashtab_node *cur = NULL;hashtab_node *prev = NULL;hvalue = h->hash_value(h,key);cur = h->htables[hvalue];while(cur != NULL && (h->keycmp(h,key,cur->key) >= 0) ) {// 找到待删除节点的前驱节点if(h->keycmp(h,key,cur->key) == 0) { // 找到匹配的keyif(prev == NULL) { // 需要删除的key就是hvalue所在hash链上的第一个keyh->htables[hvalue] = cur -> next;}else {prev->next = cur->next;}h->nel --;return cur;}prev = cur;cur = cur ->next;}return NULL;
}/* 查找 */
void *hashtab_search(hashtab*h,void *key) 
{if(h == NULL || key == NULL) {return NULL;}unsigned int hvalue = 0;hashtab_node *cur = NULL;hvalue = h->hash_value(h,key);cur = h->htables[hvalue];if(cur == NULL) { // 先确认hash桶是否存在return NULL;}while(cur != NULL) {if(h->keycmp(h,key,cur->key) == 0) {return cur->data;}cur = cur ->next;}return NULL;
}void hashtab_dump(hashtab *h) 
{int i = 0;hashtab_node *cur = NULL;if(h == NULL) {return;}printf("\r\n----开始--size[%d],nel[%d]------------", h->size, h->nel);for(;i< h->size; ++i) {printf("\r\n htables[%d]:",i);cur = h->htables[i];while(cur != NULL) {printf("key[%s],data[%s] ", cur->key, cur->data);cur = cur ->next;}}printf("\r\n----结束--size[%d],nel[%d]------------", h->size, h->nel);
}/* 扩容 */
void  *hashtab_expand(hashtab *tmp_h) {if(tmp_h == NULL || (tmp_h ->size * 3 / 4 > tmp_h->nel)) {return NULL;}printf("begin expand\n");hashtab *new_h = NULL;hashtab *h = tmp_h;hashtab_node *cur = NULL;int i = 0;new_h = hashtab_create(h->size * 2, h->hash_value,h->keycmp, h->hash_node_free);for (;i < h->size; ++i) {cur = h->htables[i];while(cur != NULL) {hashtab_insert(new_h, cur->key, cur->data);cur = cur->next;}}printf("before destory\n");hashtab_destory(tmp_h);printf("end destory\n");// hashtab_dump(new_h);tmp_h = new_h;return NULL;
}struct test_node
{/* data */char key[30];char data[30];
};unsigned int simple_hash(const char *str)
{register unsigned int hash = 0;register unsigned int seed = 131;while(*str){hash = hash*seed + *str++;}return hash & (0x7FFFFFFF);
}int hashtable_hvalue(hashtab *h, const void *key) 
{return simple_hash(key) % h->size;
}int hashtable_compare(hashtab*h, const void *key1, const void *key2)
{return strcmp(key1, key2); 
}void hashtable_node_free(hashtab_node *cur) 
{struct test_node *tmp = NULL;tmp = container(cur->key,struct test_node,key);free(tmp);free(cur);
}int main ()
{int res = 0;char *pres = NULL;hashtab_node * node = NULL;struct test_node *p = NULL;hashtab *h = NULL;h = hashtab_create(6,hashtable_hvalue,hashtable_compare,hashtable_node_free);// 创建一个hash桶大小为5的hash表assert(h!= NULL);while(1){p = (struct test_node*)malloc(sizeof(struct test_node));assert(p != NULL);printf("\r\n 输入key  value，输入\"quit\"退出");scanf("%s",p->key);scanf("%s",p->data);if(strcmp(p->key,"quit") == 0){free(p);break;}res = hashtab_insert(h,p->key,p->data);if (res != 0){free(p);printf("\r\n key[%s],data[%s] insert failed %d",p->key,p->data,res);}else{printf("\r\n key[%s],data[%s] insert success %d",p->key,p->data,res);}}hashtab_dump(h);while(1){p = (struct test_node*)malloc(sizeof(struct test_node));assert(p != NULL);printf("\r\n 请输入key 查询value的数值，当可以等于\"quit\"时退出");scanf("%s",p->key);if(strcmp(p->key,"quit") == 0){free(p);break;}pres = hashtab_search(h,p->key);if (pres == NULL){printf("\r\n key[%s] search data failed",p->key);}else{printf("\r\n key[%s],search data[%s] success",p->key,pres);}free(p);}hashtab_dump(h);while(1){p = (struct test_node*)malloc(sizeof(struct test_node));assert(p != NULL);printf("\r\n 请输入key 删除节点的数值，当可以等于\"quit\"时退出");scanf("%s",p->key);if(strcmp(p->key,"quit") == 0){free(p);break;}node = hashtab_delete(h,p->key);if (node == NULL){printf("\r\n key[%s] delete node failed ",p->key);}else{printf("\r\n key[%s],delete data[%s] success",node->key,node->data);h->hash_node_free(node);}free(p);hashtab_dump(h);}hashtab_destory(h);return 0;}