调整空间
显然初始化内存大小是无法记录元素的，以及如果新增元素超过当前哈希表所能容纳的大小，或者哈希表中大部分的元素都被删除，不需要那么多空间，我们都需要对哈希表的空间进行调整。因此在khash.h有62行代码，即244-306，是负责哈希表的大小调整。
khash.h代码中只有kh_put_##name在h->n_occupied >= h->upper_bound时会调用kh_resize_##name，而且是先考虑h->n_buckets > (h->size<<1), 如果桶大小比实际存放元素数的2倍还大，说明是标记删除元素太多了，那么需要清空哈希表，否则是真的不够了。前者传给kh_resize_##name的new_n_buckets = h->n_buckets - 1, 后者new_n_buckets = h->n_buckets + 1
n_buckets会先经过kroundup32函数计算出新哈希表的大小（new_n_buckets），kroundup32涉及到一系列的位运算
#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
它的效果是得到比当前桶的大小大且距离最近的2^n,例如桶的数目是55，那么最近的就是64。如果桶的数目是297, 那么最近的就是512，如果是64，那么就是63。 如果是我写那就只能写出下面这种代码
int roundup32(int x) {
int tmp = x;
int y = 1;
while (tmp) {
tmp >>= 1;
y <<= 1;
}
return x==(y>>1) ? y>>1 : y;
}
接着，它还保证桶的数目最少是4，if (new_n_buckets < 4) new_n_buckets = 4;
我们先考虑申请的空间的可容纳上限比已有元素多的情况
if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0;
khash.h会先计算new_flags的数目，并初始化为0xaa. 如果当前的桶的大小低于新的桶的大小，那么就用krealloc重新申请内存，并将数据拷贝到新的内存地址中。
new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
if (!new_flags) return -1; \
memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
if (h->n_buckets < new_n_buckets) { /* expand */ \
khkey_t* new_keys = (khkey_t*)krealloc((void*)h->keys, new_n_buckets * sizeof(khkey_t)); \
if (!new_keys) { kfree(new_flags); return -1; } \
h->keys = new_keys; \
if (kh_is_map) {
\
khval_t* new_vals = (khval_t*)krealloc((void*)h->vals, new_n_buckets * sizeof(khval_t)); \
if (!new_vals) { kfree(new_flags); return -1; } \
h->vals = new_vals; \
} \
} /* otherwise shrink */
上面的代码相对简单，最复杂的268-294行重新计算hash的过程。重新计算哈希的本质本质就是缩小哈希表。
因为桶的大小是按照4,8,16,32,64,128,256,512,1024这种方式增加，所以只要是增加空间，当前的元素数目是不可能高于新的桶大小的可容纳范围的上限的。只有在h->n_buckets <= (h->size<<1)的情况下，也就是当前空间一般都是删除的元素的情况下，才会出现当前元素数目大于桶的可容纳上限的情况。
此时新的空间大小变为原来的一半，那么里面的元素就需要移动位置。搬运的时候，很有可能出现哈希碰撞。
搬运过程是一个嵌套循环，外层循环遍历旧哈希表的每个桶，如果发现它该位置上有元素，就记录它的key和value，然后我们算下它在新哈希表位置（如果找到不为空的，就往后移动），并将新位置标记为不为空。同时检查新哈希表位置对应的旧哈希表位置上是否有元素，如果有，就把该元素和待插入元素进行交换，我们的下一个任务就是为这个元素查找位置，否则就可以退出了。
for (j = 0; j != h->n_buckets; ++j) {
\
if (__ac_iseither(h->flags, j) == 0) {
\
khkey_t key = h->keys[j]; \
khval_t val; \
khint_t new_mask; \
new_mask = new_n_buckets - 1; \
if (kh_is_map) val = h->vals[j]; \
__ac_set_isdel_true(h->flags, j); \
while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
khint_t k, i, step = 0; \
k = __hash_func(key); \
i = k & new_mask; \
while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \
__ac_set_isempty_false(new_flags, i); \
if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \
{ khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
__ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \
}
else { /* write the element and jump out of the loop */ \
h->keys[i] = key; \
if (kh_is_map) h->vals[i] = val; \
break; \
} \
} \
} \
}
接下来的工作就是用krealloc重新调整内存大小, 重新计算其他元信息.
if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
h->keys = (khkey_t*)krealloc((void*)h->keys, new_n_buckets * sizeof(khkey_t)); \
if (kh_is_map) h->vals = (khval_t*)krealloc((void*)h->vals, new_n_buckets * sizeof(khval_t)); \
} \
kfree(h->flags); /* free the working space */ \
h->flags = new_flags; \
h->n_buckets = new_n_buckets; \
h->n_occupied = h->size; \
h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
