zc_hashtable设计思想

哈希表（hash table），又叫散列表，是根据关键字和值（key-value）直接进行访问的数据结构。哈希表可实现O(1)查找时间复杂度，用于频繁查找的场景，能大大提高效率。哈希表通过关键字和一个映射函数hash(key) 计算出对应value，这个映射函数称为哈希函数。

常用的哈希表设计思想，是利用数组+链表来实现。其中，数组用来存放记录，链表用来解决冲突。用除留余数法计算key，求出对应位置hash(key) = key % p，p是数组长度，hash(key)就是数组索引。

实践中，注意：
1）数组往往作为冲突链表的头结点，而不存放数据。
2）先将key通过一个计算哈希值的算法，将其转换为hashCode，然后再用哈希函数进行位置计算，并不是直接对key调用哈希函数进行位置计算。

zc_hashtable数据结构

类似zc_arraylist，zc_hashtable用void*类型，来支持各种类型的key和value，因此也必须由调用者来实现具体的key和value的操作函数，包括申请内存、释放内存、判等、比较大小等。

每个zc_hashtable_entry_t都是一个哈希表表项，包含(hash_key, key, value)，以双链表形式将冲突链表串到一起；而哈希表zc_hashtable_t主要负责维护一个哈希数组（zc_hashtable_entry_t **tab），每一项tab[i]都指向一个哈希表表项。

思考：为什么zc_hashtable_t要用二维数组形式，维护哈希数组，而不用一维数组呢？
Re：如果是二维数组，那么每个链表头结点都是一个指针来表示，1）很容易判断是否为空；2）容易移动链表头结点，直接指针赋值即可，代价很小，无需头结点每个成员都赋值。个人觉得用一维数组应该也是可以的，而且实现更简单，但运行效率更低。

/**
* 哈希表项, 存放(key,value)
* @details 使用双向链表来组织链表, 便于查找. 因此, 在数组中, 该结构对应一个表项;
* 在链表中, 该结构对应一个链表节点.
*/
typedef struct zc_hashtable_entry_s {
    unsigned int hash_key;  /* hash值 */
    void *key;
    void *value;
    struct zc_hashtable_entry_s *prev;
    struct zc_hashtable_entry_s *next;
} zc_hashtable_entry_t;

/**
* 哈希表
* a_table = zc_hashtable_t<key, value>
*/
struct zc_hashtable_s {
    size_t nelem;    /* 元素总个数 */

    zc_hashtable_entry_t **tab;   /* hashtable 数组, 每个表项作为冲突链表头节点 */
    size_t tab_size; /* hashtable 数组大小*/

    zc_hashtable_hash_fn hash;     /* 计算hash值的函数 */
    zc_hashtable_equal_fn equal;   /* 判断2个元素key是否相等的函数 */
    zc_hashtable_del_fn key_del;   /* 根据key删除元素 */
    zc_hashtable_del_fn value_del; /* 根据value删除元素 */
};

typedef struct zc_hashtable_s zc_hashtable_t;

typedef unsigned int (*zc_hashtable_hash_fn) (const void *key);
typedef int (*zc_hashtable_equal_fn) (const void *key1, const void *key2);
typedef void (*zc_hashtable_del_fn) (void *kv);

zc_hashtable接口

提供基本的对象创建、析构，添加元素，根据key查找和删除元素的接口。zc_hashtable还提供顺序迭代，默认计算哈希值算法，key判等，等接口。
值得注意的是：虽然zc_hashtable有rehash、扩容的功能，但并未提供接口以供外部访问，而是内部调用。

/* 构造一个zc_hashtable对象 */
zc_hashtable_t *zc_hashtable_new( size_t a_size,
                zc_hashtable_hash_fn hash_fn,
                zc_hashtable_equal_fn equal_fn,
                zc_hashtable_del_fn key_del_fn,
                zc_hashtable_del_fn value_del_fn);

/* 析构一个zc_hashtable对象a_table */
void zc_hashtable_del(zc_hashtable_t *a_table);
/* 删除a_table所有元素 */
void zc_hashtable_clean(zc_hashtable_t *a_table);
/* 将(a_key, a_value)加入哈希表a_table */
int zc_hashtable_put(zc_hashtable_t *a_table, void *a_key, void *a_value);
/* 根据(a_key, a_value)在a_table中查找项 */
zc_hashtable_entry_t *zc_hashtable_get_entry(zc_hashtable_t *a_table, const void *a_key);
/* 根据a_key在a_table中查找a_value */
void *zc_hashtable_get(zc_hashtable_t *a_table, const void *a_key);
/* 从a_table中移除关键字为a_key的项 */
void zc_hashtable_remove(zc_hashtable_t *a_table, const void *a_key);
/* 找到a_table第1项, 用于顺序迭代a_table */
zc_hashtable_entry_t *zc_hashtable_begin(zc_hashtable_t *a_table);
/* 找到a_table中a_entry项的下一项 */
zc_hashtable_entry_t *zc_hashtable_next(zc_hashtable_t *a_table, zc_hashtable_entry_t *a_entry);

/* 循环遍历a_table */
#define zc_hashtable_foreach(a_table, a_entry) \
    for (a_entry = zc_hashtable_begin(a_table); a_entry; a_entry = zc_hashtable_next(a_table, a_entry))

/* 计算字符串str的哈希值, 采用DJBX33A算法 */
unsigned int zc_hashtable_str_hash(const void *str);
/* 判断2个key是否相等, 将key1和key2当做字符串 */
int zc_hashtable_str_equal(const void *key1, const void *key2);

接口实现

构造与析构

zc_hastable的构造函数，主要有这几部分工作：
1）申请zc_hashtable_t对象空间；
2）申请哈希表数组（二维数组）zc_hashtable_t::tab空间；
3）初始化其他成员，包括tab数组大小，元素个数，计算hash值函数，判等函数；
4）初始化key和value的删除函数；

至于表项（zc_hashtable_entry_t）初始化的工作，留到插入数据时再做，因为此时哈希表中并无元素。

构造函数：

/**
* 创建一个hashtable
* @param a_size hashtable数组初始大小
* @param hash 计算哈希值的哈希函数
* @param equal 比较函数, 用于比较key大小
* @param key_del 删除key所指对象
* @param value_del 删除value所指对象
* @return 如果成功, 返回新建的hashtable对象; 失败返回NULL, 环境变量ZLOG_PROFILE_ERROR
* 所指error log记录错误原因.
*/
zc_hashtable_t *zc_hashtable_new( size_t a_size,
                zc_hashtable_hash_fn hash,
                zc_hashtable_equal_fn equal,
                zc_hashtable_del_fn key_del,
                zc_hashtable_del_fn value_del)
{
    // FIXME: why zc_hashtable' initial size decided by user,
    // but that of zc_arraylist decided by self(default value)?

    zc_hashtable_t *a_table;

    a_table = calloc(1, sizeof(*a_table));
    if (!a_table) {
        zc_error("calloc fail, errno[%d]", errno);
        return NULL;
    }

    /* malloc + bzero */
    a_table->tab = calloc(a_size, sizeof(*(a_table->tab)));
    if (!a_table->tab) {
        zc_error("calloc fail, errno[%d]", errno);
        free(a_table);
        return NULL;
    }

    /* 初始化hashtable各成员值 */
    a_table->tab_size = a_size;
    a_table->nelem = 0;
    a_table->hash = hash;
    a_table->equal = equal;

    /* these two could be NULL */
    a_table->key_del = key_del;
    a_table->value_del = value_del;

    return a_table;
}

析构函数：
销毁整个哈希表的，对每个元素(key, value)调用相应的delete函数以释放空间。遍历哈希表的每个元素，依托于以每个数组元素为链表起点，用一个两层for循环搞定。
注意：delete key或value时，先判断空指针，避免造成未定义行为（因为不清楚外部传入的delete函数如何处理空指针）。

/**
* 销毁整个hashtable
*/
void zc_hashtable_del(zc_hashtable_t *a_table)
{
    size_t i;
    zc_hashtable_entry_t *p;
    zc_hashtable_entry_t *q;

    if (!a_table) {
        zc_error("a_table[%p] is NULL, just do nothing", a_table);
        return;
    }

    /* 变量hashtable数组, 释放每个元素 */
    for (i = 0; i < a_table->tab_size; i++) {
        for (p = (a_table->tab)[i]; p; p = q) { /* 遍历每个数组项为头结点的链表 */
            q = p->next;
            if (a_table->key_del) {
                a_table->key_del(p->key);
            }
            if (a_table->value_del) {
                a_table->value_del(p->key);
            }
            free(p);
        }
    }

    if (a_table->tab)
        free(a_table->tab);
    free(a_table);
}

插入元素

往hashtable插入一个元素(key, value)，相当于C++ unordered_map<key, value>::insert。不过，由于C没有模板，由于要兼容不同类型的key、value，这里我们插入的key和value都是void*。

插入元素的策略是：
1）先查找该元素是否存在，如果存在，先释放旧的key、value，再更新key、value，元素计数保持不变；
2）如果不存在，就将其插入到对应链表表头，元素计数+1；

一个元素(key, value)，如何找到该插入到什么位置呢？
先计算key对应hash值hash_key = hash(key)；
然后对hash_key进行除留余数法，得到数为元素应该插到数组的哪个位置（哪个链表），index = hash_key % tab_size。
以tab[index]为链表起点，遍历冲突链表，顺序查找key值相等的项。如果能找到，说明元素已经存在；如果找不到或者链表为空，说明元素不存在。

如果插入元素后，哈希表元素太多导致查找效率降低怎么办？如何判断哈希表元素太多？
从上面问题分析可知，当冲突链表中元素过多时，哈希表退化成链表，查找效率由O(1)降为O(n)。当插入新元素时，如果哈希表当前元素个数nelem > 1.3 * 数组大小tab_size，就对哈希表进行扩容rehash（再散列）（见下文）。

/**
* 向hashtable插入一个元素(key, value)
* @details a_key和a_value应该由调用者提供, 并负责其初始化. 在冲突链表上插入项,
* 实际上用的直接插入查找算法在链表尾部插入(O(n)), 而非效率更高的头插法(O(1)).
*/
int zc_hashtable_put(zc_hashtable_t *a_table, void *a_key, void *a_value)
{
    unsigned int i;
    zc_hashtable_entry_t *p = NULL;

    /* 首先查找是否存在相同(key, value), 如果存在, 释放原来的key,value空间, 然后更新value;
     * 如果不存在, 就添加一个新节点(key, value)
     */

    i = a_table->hash(a_key) % a_table->tab_size; /* 除留取余法 */
    for (p = (a_table->tab)[i]; p; p = p->next) { /* 遍历链表, 找key对应节点 */
        if (a_table->equal(a_key, p->key)) {
            break;
        }
    }

    if (p) { /* a_key exist in hashtable */
        /* 释放旧的key, value空间 */
        if (a_table->key_del) {
            a_table->key_del(p->key);
        }
        if (a_table->value_del) {
            a_table->value_del(p->value);
        }
        /* 设置新的(key, value) */
        p->key = a_key;
        p->value = a_value;
        return 0;
    } else { /* a_key not exist in hashtable */
        if (a_table->nelem > a_table->tab_size * 1.3) { /* 负载因子 > 1.3, 需要rehash扩容 */
            int rc;

            rc = zc_hashtable_rehash(a_table);
            if (rc) {
                zc_error("rehash fail");
                return -1;
            }
        }

        p = calloc(1, sizeof(*p)); /* 新建链表节点, 用于存放(key, value) */
        if (!p) {
            zc_error("calloc fail, errno[%d]", errno);
            return -1;
        }

        p->hash_key = a_table->hash(a_key);
        p->key = a_key;
        p->value = a_value;
        p->next = NULL;
        p->prev = NULL;

        /* 如果对应链表非空， 就插入到链表头部
         * 注意: 双向链表不是双向循环链表
         */
        i = p->hash_key % a_table->tab_size;
        if ((a_table->tab)[i]) {
            (a_table->tab)[i]->prev = p;
            p->next = (a_table->tab)[i];
        }
        (a_table->tab)[i] = p;
        a_table->nelem++; /* 总元素个数+1 */
    }

    return 0;
}

注意：
1）zc_hashtable负责回调key、value的delete函数，但并不负责key、value的构造。因此在使用时，需要十分小心。

扩容rehash

zc_hashtable提供再散列（rehash）机制，通常rehash发生在哈希表容量扩大或缩小时，zc_hashtable只提供扩容rehash： zc_hashtable_rehash。

zc_hashtable_rehash 提供固定的2倍扩容，每调用一次就扩容一次。因此，元素是否过多的判断应该由调用者完成。扩容后，需要先把旧哈希表空间的元素“拷贝”到新空间，然后释放旧的空间。
注意：这里的“拷贝”并不是简单的再拷贝，而是重新计算其在数组中的位置，插入对应链表，即rehash（再散列）的过程。

/**
* 扩容 + rehash(再散列)
*/
static int zc_hashtable_rehash(zc_hashtable_t *a_table)
{
    size_t i;
    size_t j;
    size_t tab_size;
    zc_hashtable_entry_t **tab;
    zc_hashtable_entry_t *p;
    zc_hashtable_entry_t *q;

    zc_assert(a_table != NULL, );

    /* 申请新的hashtable, 数组容量为旧的2倍 */
    tab_size = 2 * a_table->tab_size; /* 数组扩容2倍 */
    tab = calloc(tab_size, sizeof(*tab));
    if (!tab) {
        zc_error("calloc fail, errno[%d]", errno);
        return -1;
    }

    /* 将旧hashtable数据拷贝到新hashtable */
    for (i = 0; i < a_table->tab_size; i++) {
        for (p = (a_table->tab)[i]; p; p = q) { /* p代表当前表项, q代表p->next */
            q = p->next;

            p->next = NULL;
            p->prev = NULL;
            /* 重新计算在新数组中的位置 */
            j = p->hash_key % tab_size;
            if (tab[j]) {
                tab[j]->prev = p;
                p->next = tab[j];
            }
            tab[j] = p;
        }
    }

    free(a_table->tab); /* 释放旧的hastable数组 */
    /* 更新新的hashtable数组 */
    a_table->tab = tab;
    a_table->tab_size = tab_size;

    return 0;
}

查找元素

zc_hashtable提供了2个接口，用于查找元素：
1）zc_hashtable_get_entry 根据key查找项zc_hashtable_entry_t；
2）zc_hashtable_get 根据key查找value；

由于插入数据（zc_hashtable_put）时，如果key相同，就会用新value覆盖旧value，而对旧的（key, value）调用delete函数以释放空间，因此，zc_hashtable中不存在相同key的元素。也就是说，zc_hashtable的数据(key)具有唯一性。

/**
* 根据key查找项
*/
zc_hashtable_entry_t *zc_hashtable_get_entry(zc_hashtable_t *a_table, const void *a_key)
{
    unsigned int i;
    zc_hashtable_entry_t *p;

    i = a_table->hash(a_key) % a_table->tab_size;
    for (p = (a_table->tab)[i]; p; p = p->next) { /* 从冲突链表头开始查找 */
        if (a_table->equal(a_key, p->key))
            return p;
    }

    return NULL;
}

/**
* 根据key查找value
*/
void *zc_hashtable_get(zc_hashtable_t *a_table, const void *a_key)
{
    unsigned int i;
    zc_hashtable_entry_t *p;

    // 下面代码等价于
    // p = zc_hashtable_get_entry(a_table, a_key);
    // return (!p ? NULL : p->value);

    i = a_table->hash(a_key) % a_table->tab_size;
    for (p = (a_table->tab)[i]; p; p = p->next) {
        if (a_table->equal(a_key, p->key))
            return p->value;
    }
    return NULL;
}

删除元素

根据key删除哈希表中的元素(key, value)。元素位于以数组项为起点的某个冲突链表中，需要先查找，然后再将其充链表中删除。

查找的过程，前面已经讲过：
1）计算数组索引index = hash(key) % tab_size；
2）以tab[index]为头结点，顺序查找冲突链表；

如果查找链表失败，则删除失败；如果查找成功，则说明元素存在，需要将其从链表中断开，然后delete元素。

如何将一个节点从链表断开？
冲突链表是一个双向链表（注意不是双向循环链表），删除的节点可能是表头，或者表中节点（或表尾）。
表头特点：prev为空；表尾特点：next为空；
而数组始终指向表头，因此将节点从链表中删除时，需要特别小心表头节点的处理。

/**
* 根据key删除项
*/
void zc_hashtable_remove(zc_hashtable_t *a_table, const void *a_key)
{
    zc_hashtable_entry_t *p;
    unsigned int i;

    if (!a_table || !a_key) {
        zc_error("a_table[%p] or a_key[%p] is NULL, just do nothing", a_table, a_key);
        return;
    }

    /* 查找key为a_key的项 */
    i = a_table->hash(a_key) % a_table->tab_size;
    for (p = (a_table->tab)[i]; p; p = p->next) {
        if (a_table->equal(a_key, p->key))
            break;
    }

    if (!p) { /* 查找失败 */
        zc_error("p[%p] not found in hashtable", p);
        return;
    }

    /* 查找成功, 此时p指向待删除项 */

    /* 释放原有的key, value */
    if (a_table->key_del) {
        a_table->key_del(p->key);
    }
    if (a_table->value_del) {
        a_table->value_del(p->value);
    }

    /* 断开链表与p的连接 */
    if (p->next) {
        p->next->prev = p->prev;
    }
    if (p->prev) {
        p->prev->next = p->next;
    } else {
        /* 双向链表prev为NULL, 表示该节点是头结点
           直接将p的下一个节点(next)衔接到头结点 */
        i = p->hash_key % a_table->tab_size;
        a_table->tab[i] = p->next;
    }

    free(p); /* 释放p所指项 */
    a_table->nelem--; /* 总元素个数-1 */
}

顺序迭代哈希表

如果外部用户要遍历哈希表，但又不想了解哈希表的细节实现，比如数组+链表的实现。该如何实现？
zc_hashtable提供了宏函数zc_hashtable_foreach，用来顺序遍历哈希表的每个元素。

/* 循环遍历a_table */
#define zc_hashtable_foreach(a_table, a_entry) \
    for (a_entry = zc_hashtable_begin(a_table); a_entry; a_entry = zc_hashtable_next(a_table, a_entry))

zc_hashtable_foreach的实现依赖于2个函数：zc_hashtable_begin和zc_hashtable_next。
zc_hashtable_begin用于获得哈希表中第一个包含元素的节点；zc_hashtable_next用于获取哈希表中，指定元素的下一个节点。当元素位于链表中（非表尾时，next域非空），表项的next节点就是下一个节点；当元素位于链表尾时（next域为空），需要换到数组对应位置的下个位置，即为链表尾的下一个元素，后续可以以该位置为新链表头结点。

/**
* 找到hashtable的第1个元素对应项
* @note 常用于迭代器遍历hashtable
*/
zc_hashtable_entry_t *zc_hashtable_begin(zc_hashtable_t *a_table)
{
    size_t i;
    zc_hashtable_entry_t *res = NULL;
    zc_hashtable_entry_t *p;

    /* 从数组的第1个链表开始遍历(i=0), 找到第一个非空节点 */
    for (i = 0; i < a_table->tab_size; i++) {
        for (p = (a_table->tab)[i]; p; p = p->next) {
            if (p) {
                res = p;
                break;
            }
        }
    }

    return res;
}

/**
* 返回下一个元素对应项
*/
zc_hashtable_entry_t *zc_hashtable_next(zc_hashtable_t *a_table, zc_hashtable_entry_t *a_entry)
{
    size_t i;
    size_t j;
    zc_hashtable_entry_t *res = NULL;

    /* a_entry位于非链表尾 */
    if (a_entry->next)
        return a_entry->next;

    /* a_entry位于链表尾, 需要换一个链表 */

    i = a_entry->hash_key % a_table->tab_size;
    for (j = i + 1; j < a_table->tab_size; j++) {
        if ((a_table->tab)[j]) {
            res = (a_table->tab)[j];
            break;
        }
    }

    return res;
}

用户如何实现遍历哈希表呢？
下面是一个例子，用于打印每个元素的key和value，其中，元素(key, value)都是常量字符串。

// test/test_hashtable.c

void myfree(void *kv) { }
int main(void)
{
    zc_hashtable_t *a_table;
    zc_hashtable_entry_t *a_entry = NULL;
    /* 构造哈希表并插入数据 */
    a_table = zc_hashtable_new(20,
        zc_hashtable_str_hash,
        zc_hashtable_str_equal,
        myfree, myfree);
    zc_hashtable_put(a_table, "aaa", "bnbb");
    zc_hashtable_put(a_table, "bbb", "bnbb");
    zc_hashtable_put(a_table, "ccc", "bnbb");

        // 顺序迭代哈希表a_table
    zc_hashtable_foreach(a_table, a_entry) {
        printf("k[%s],v[%s]\n", (char*)a_entry->key, (char*)a_entry->value);
    }

    zc_hashtable_del(a_table);
    return 0;
}

计算哈希值的算法

zc_hashtable提供默认的计算key对应哈希值（hash_key）的算法zc_hashtable_str_hash，实际上用的DJBX33A算法，适用于字符串计算哈希值。

/**
* 一种计算符串的hash值的算法
* @details DJBX33A, 又名Times33 哈希算法
* 公式: hash(i) = hash(i-1) * 33 + str[i]
*
* @see
* https://blog.csdn.net/weixin_43932088/article/details/85983436
* http://www.partow.net/programming/hashfunctions/
* http://www.cse.yorku.ca/~oz/hash.html
*/
unsigned int zc_hashtable_str_hash(const void *str)
{
    unsigned int h = 5381;
    const char *p = (const char *)str;

    while (*p != '\0') {
        h = ((h << 5) + h) + (*p++); /* hash * 33 + c */
    }
    return h;
}

关键字判等

key判等是实现查找、删除的重要环节，对于void*类型的key，如何判等呢？
zc_hashtable提供默认的判等函数zc_hashtable_str_equal，用于比较2个key是否相等，采用的办法是将key1, key2所对应内存解释为字符串，然后利用字符串比较函数strcmp进行比较。

/**
* 一种比较两个关键字是否相等的方法
* @details 将key1, key2所指内存当做字符串进行比较.
*/
int zc_hashtable_str_equal(const void *key1, const void *key2)
{
    return (STRCMP((const char*)key1, ==, (const char*)key2));
}

#define STRCMP(_a_, _C_, _b_) ( strcmp(_a_, _b_) _C_ 0 )

小结

1）zc_hashtable哈希表采用数组+链表形式组织数据，数组每个槽位对应一个链表即冲突链表，用于解决冲突。而每个数组的表项也能对应一个元素(key, value)。
2）冲突链表采用的是双向链表，注意与双向循环链表的区别。

参考

https://blog.csdn.net/Cdreamfly/article/details/125770858