哈希鏈地址法

哈希的引入是數(shù)組和鏈表的結(jié)合體，有效解決了查詢/插入/刪除的性能問(wèn)題。但不可避免的引入了哈希沖突問(wèn)題，解決沖突的方法有多種，本文只針對(duì)鏈地址法的設(shè)計(jì)進(jìn)行描述。

鏈地址法

鏈地址法簡(jiǎn)而言之即將所有哈希地址相同的記錄都鏈接在同一鏈表中

算法設(shè)計(jì)

• 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

/* 哈希單元定義 */
typedef struct {
    struct list_head list;
    void   *item;
} lib_hash_item_t;
/*  哈希表結(jié)構(gòu)定義 */
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;

• 哈希函數(shù)聲明

/* 創(chuàng)建哈希表 */
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);

• 哈希函數(shù)定義

/* 創(chuàng)建一張哈希表 */
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;
}

/* 哈希表中插入一個(gè)單元 */
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沖突的最大節(jié)點(diǎn)數(shù) */
    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;
}

/* 哈希表中刪除一個(gè)單元 */
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;
}