哈希公共服务

哈希链地址法

哈希的引入是数组和链表的结合体，有效解决了查询/插入/删除的性能问题。但不可避免的引入了哈希冲突问题，解决冲突的方法有多种，本文只针对链地址法的设计进行描述。

链地址法

链地址法简而言之即将所有哈希地址相同的记录都链接在同一链表中

算法设计

• 数据结构设计

/* 哈希单元定义 */
typedef struct {
    struct list_head list;
    void   *item;
} lib_hash_item_t;
/*  哈希表结构定义 */
typedef struct {
    u_int32_t   hash_table_size;
    u_int32_t   hash_item_num;
    u_int32_t   hash_bucket_warn_size;
    u_int32_t   max_conflict_size;
    u_int8_t    *hash_bucket_size;
    struct list_head *hash_table;
    hash_get_index_func_t  hash_get_index;
    hash_cmp_key_func_t    hash_cmp_key;
} lib_hash_t;

• 哈希函数声明

/* 创建哈希表 */
lib_hash_t *lib_create_hash(u_int32_t item_num, hash_get_index_func_t hash_get_index,  hash_cmp_key_func_t hash_cmp_key);

/* 删除哈希表 */
void lib_destroy_hash(lib_hash_t *hash);

/* 插入哈希单元 */
int lib_hash_insert_item(lib_hash_t * hash, void *item);

/* 删除哈希单元 */
void lib_hash_del_item(lib_hash_t * hash, void *item);

/* 查找哈希单元 */
void *lib_hash_find_item(lib_hash_t * hash, void *item);

• 哈希函数定义

/* 创建一张哈希表 */
lib_hash_t *lib_create_hash(u_int32_t item_num, hash_get_index_func_t hash_get_index, hash_cmp_key_func_t hash_cmp_key)
{
    int32_t     i;
    u_int32_t   hash_table_size;
    struct list_head *hash_table;
    lib_hash_t *hash;

    hash = malloc(sizeof(libss_hash_t));
    if (hash == NULL) {
        return NULL;
    }
    
    item_num = item_num == 0 ? MIN_HASH_SZ : item_num;
    hash_table_size = ((double)item_num) / HASH_GENE;
    hash_table = malloc(sizeof(struct list_head) * hash_table_size);
    if (hash_table == NULL) {
        free(hash);
        return NULL;
    }
    if ( (hash->hash_bucket_size = malloc( sizeof(hash->hash_bucket_size[0]) * 
     hash_table_size )) == NULL ){
        free(hash);
        free(hash_table );
        return NULL;
    }
        
    for (i = 0; i < hash_table_size; i++) {
        hash->hash_bucket_size[i] = 0;
        INIT_LIST_HEAD(&hash_table[i]);
    }
    
    hash->hash_item_num     = 0;
    hash->hash_table_size   = hash_table_size;
    hash->hash_table        = hash_table;
    hash->hash_get_index    = hash_get_index;
    hash->hash_cmp_key      = hash_cmp_key;
    hash->hash_bucket_warn_size = 0;
    hash->max_conflict_size = 0;
    
    return hash;
}

/* 删除哈希表 */
void lib_destroy_hash(lib_hash_t *hash)
{
    free(hash->hash_bucket_size);
    free(hash->hash_table);
    free(hash);
    
    return;
}

/* 哈希表中插入一个单元 */
int32_t lib_hash_insert_item(lib_hash_t *hash, void *item)
{
    u_int32_t              index;
    lib_hash_item_t        *hash_item;

    hash_item = malloc(sizeof(lib_hash_item_t));
    if (hash_item == NULL) {
        return (-ENOMEM);
    }
    /* 获取hash地址 */
    index = hash->hash_get_index(item) % hash->hash_table_size;
    hash_item->item = item;
   /* hash地址所在链表添加单元 */
    list_add(&hash_item->list, &hash->hash_table[index]);
    hash->hash_bucket_size[index]++;
   /* 更新hash冲突的最大节点数 */
    if (hash->hash_bucket_size[index] > hash->max_conflict_size) {
        hash->max_conflict_size = hash->hash_bucket_size[index];
    }
    hash->hash_item_num++;

    return 0;
}

/* 哈希表中删除一个单元 */
void lib_hash_del_item(lib_hash_t *hash, void *item)
{
    u_int32_t            index;
    struct list_head *pos, *n;
    lib_hash_item_t *hash_item;

    index = hash->hash_get_index(item) % hash->hash_table_size;
   /* 遍历哈希地址所在链表 */
    list_for_each_safe(pos, n, &hash->hash_table[index]) {
        hash_item = list_entry(pos, lib_hash_item_t, list);
        if (hash->hash_cmp_key(hash_item->item, item) == 0) {
            hash->hash_bucket_size[index]--;
            hash->hash_item_num--;
            list_del(&hash_item->list);
            free(hash_item);
            break;
        }
    }
}

/* 查找哈希表单元 */
void *lib_hash_find_item(lib_hash_t *hash, void *item)
{
    u_int32_t index;
    struct list_head *pos;
    lib_hash_item_t *hash_item;

    index = hash->hash_get_index(item) % hash->hash_table_size;
    list_for_each(pos, &hash->hash_table[index]) {
        hash_item = list_entry(pos, libss_hash_item_t, list);
        if (hash->hash_cmp_key(hash_item->item, item) == 0) {
            return hash_item->item;
        }
    }
    return NULL;
}