阅读此文前，推荐先看Klib之khash学习笔记
C语言标准库并没有字典(map)和集合(set)这种数据结构，因此如果想需要在C语言使用这种数据结构，要么自己根据不同数据类型都写一种函数，或者就是用别人写好的数据结构来用。
Khash.h提供了一种基于开放寻址法的泛型的哈希表, 这里的开放寻址法是一种解决哈希冲突的方法，当哈希函数时计算的位置已经有元素的时候，它会基于当前位置往后探测(probe), 找到一处没有元素的位置。当然还有一种方法，就是拉链法，也就是在冲突的地方，创建一个链表，里面存放具有相同哈希地址的不同元素。
哈希函数
khash.h根据不同的初始化函数会替换成不同的哈希函数，一共有是那种int,int64和str
#define kh_int_hash_func(key) (khint32_t)(key)
#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
#define kh_str_hash_func(key) __ac_X31_hash_string(key)
int就是将原值转换成khint32_t，int64用到了位运算，通过右移，按位异或和左移操作，最后转换成khint32_t。这两个哈希函数都非常简单，降低了哈希函数计算的时间。
稍微复杂的就是字符串的哈希函数， 它的计算方式如下
static kh_inline khint_t __ac_X31_hash_string(const char *s)
{
khint_t h = (khint_t)*s;
if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s;
return h;
}
此外还有一个在2011-09-16 (0.2.6)增加的哈希函数kh_int_hash_func2, 能够比较好的处理一些不怎么随机的数据，它的计算过程就非常的复杂了，默认不启用,。
static kh_inline khint_t __ac_Wang_hash(khint_t key)
{
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
#define kh_int_hash_func2(key) __ac_Wang_hash((khint_t)key)
数据结构
数据结构通常和算法都是搭配使用，因此理解这个数据结构的设计，就能理解后续的代码逻辑。
khash.h的定义的kh_##name##_t数据结构一共有7个部分
- n_buckets: 记录桶的数目，也就是哈希表的空间
- size: 当前记录元素
- n_occupied: 当前占据的多少元素
- upper_bound: 上限大小
- flags: 记录当前位置是否有数据
- keys: 指向key的指针
- vals: 指向value的指针
#define __KHASH_TYPE(name, khkey_t, khval_t) \
typedef struct kh_##name##_s { \
khint_t n_buckets, size, n_occupied, upper_bound; \
khint32_t *flags; \
khkey_t *keys; \
khval_t *vals; \
} kh_##name##_t;
关于桶的大小n_buckets:作者以2的n次方大小，保证有足够的空间，降低哈希碰撞。
关于size和n_occupied: 之所以有两个变量来记录哈希表中的元素，是为了降低删除运算。我们不需要在每一次删除运算时，都进行内存的释放和调整，而只要将对应的位置标记为删除状态即可，也就是减少size，而不减少n_occupied.
关于上限upper_bound: 当桶剩下的空间不够时，那么出现哈希碰撞的概率就会变大，因此就需要对哈希表进行调整，计算公式如下。
tatic const double __ac_HASH_UPPER = 0.77;
h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5);
剩下的flags,keys和vals都是指针，用于指向实际地址，是实际记录数据类型的数据结构。
new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t));
memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t));
khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t));
khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t));
如下是数据结构的示意图
数据结构示意图
具体的赋值和删除操作，在后续介绍。
网友评论