C语言简单实现Hashtable

hashtable是根据key查询value的一种数据结构，使用数组结构来存储所有的元素，使用一种方式将key映射到数组的不同下标，查询时key就可以直接映射到value，时间复杂度为O(1),因此，hashtable结构经常用于查询的目的。

要实现hashtable，主要有以下2点

1.寻找一种隐射关系，将key映射到数组的某个下标，本文使用简单的取余方式来得
到key在元素中的下标，如果为了hashtable映射更具有一致性
（尽可能的多隐射到不同的下标，少产生冲突），请自行阅读更多的资料
2.不同的key可能会映射到数组的同一个下标，那么如何处理这种冲突，
本文使用的链表来处理冲突。

本文不对理论做过多说明，只用代码说明是如何实现的，如果觉得实现有问题，欢迎拍砖。

#ifndef LINKED_HASHTABLE_H
#define LINKED_HASHTABLE_H

#include 

typedef void (*free_hashtable_func)(void *); ///< 释放函数指针声明


#define CKEYHASHTABLESIZE 8317  

#define  HASH_TABLE_OUT_MEMORY  -1
#define  HASH_TABLE_NO_CUR_ELEMENT -2   //不存在当前元素
#define  HASH_TABLE_NO_CUR_KEY -3    //不存在当前元素的key
#define  HASH_TABLE_NO_EXIST  -4
#define  HASH_TABLE_NO_KEY_ELEMENT   -5 //table中不存在对应key的元素
#define  HASH_TABLE_KEYALREADYEXISTS -6 //table中不能插入key存在的值

struct key_hash_table;
struct key_hash_element;


 int hash_table_new(struct key_hash_table **table, int cover_old_value);


void hash_table_free(struct key_hash_table *table);


void hash_table_custom_free(struct key_hash_table *table,
                            free_hashtable_func free_func);


void hash_table_goto_first_element(struct key_hash_table *table);



void hash_table_goto_last_element(struct key_hash_table *table);



int hash_table_has_cur_element(struct key_hash_table *table);


int hash_table_del_cur_element(struct key_hash_table *table);


void *hash_table_get_cur_element(struct key_hash_table *table);


uint32_t hash_table_get_cur_key(struct key_hash_table *table);


int hash_table_goto_key_element(struct key_hash_table *table,const uint32_t key);


int hash_table_has_key_element(struct key_hash_table *table, const uint32_t key);


int hash_table_add_element(struct key_hash_table* table,const uint32_t key,
                           void *value,int b_need_free_value);


void hash_table_goto_next_element(struct key_hash_table* table);



void hash_table_goto_prev_element(struct key_hash_table* table);



int hash_table_del_key_element(struct key_hash_table *table,const uint32_t key);

#endif //

#include 

#include 
#include 
#include 
#include 

#include "linked_hashtable.h"


typedef struct key_hash_element
{
    int hashindex;  
    int b_need_free_value; 
    uint32_t key;  
    void* value; 
    struct key_hash_element *hashprev,*hashnext;  
    struct key_hash_element *listprev,*listnext; 
}key_hash_element_t;


typedef struct key_hash_table
{
    key_hash_element_t *element_table[CKEYHASHTABLESIZE]; 
    key_hash_element_t *firsthashelem,*lasthashelem; 
    key_hash_element_t *curhashelem; 
    int cover_old_value;
}key_hash_table;


static inline int get_hash_table_index(const uint32_t key)
{
    return key % CKEYHASHTABLESIZE;
}

int hash_table_new(key_hash_table **table, int cover_old_value)
{
    key_hash_table *temp = *table;
    if(temp != 0) memset(temp,0,0);
    else
    {
        temp = (key_hash_table *)calloc(1, sizeof(key_hash_table));
    }
    if(temp == NULL) return HASH_TABLE_OUT_MEMORY;
    temp->cover_old_value = cover_old_value;
    *table = temp;
    return 0;
}

void hash_table_free(key_hash_table *table)
{
    if(table == NULL) return;

    key_hash_element_t *list_tmp = NULL,*list_tmp_next = NULL;//用于存放hashtable桶的元素：list_tmp从第一个开始，list_tmp用于保存哈希桶下一个元素（用于纵向列表）
    
    list_tmp = table->firsthashelem;
    while(list_tmp != 0)//释放元素内存空间
    {
        key_hash_element_t *hash_tmp,*hash_next_tmp; //用于保存横向hashtable的元素，可能多个不同的key，hash值是一样的，这时候就需要在桶中的同一个元素使用链表标识
        hash_tmp = list_tmp->hashnext;//
        while(hash_tmp != 0)
        {
            hash_next_tmp = hash_tmp->hashnext;
            if(hash_tmp->b_need_free_value) //如果需要删除元素内容空间
            {
                free(hash_tmp->value);
                hash_tmp->value = NULL;
            }
            free(hash_tmp);
            hash_tmp = hash_next_tmp;
        }
        list_tmp_next = list_tmp->listnext;//获取hashtbale的下一个元素
        if(list_tmp->b_need_free_value)
        {
            free(list_tmp->value);
            list_tmp->value = NULL;
        }
        free(list_tmp);
        list_tmp = list_tmp_next;
    }
    table->firsthashelem = 0;
    table->lasthashelem = 0;
    table->curhashelem = 0;

    for (int i = 0 ; i < CKEYHASHTABLESIZE ; i++)
        table->element_table[i] = NULL;

    free(table);//释放table自身
}

int hash_table_del_cur_element(key_hash_table *table)
{
    if(table == NULL) return 0;

    if (table->curhashelem)
    {
        key_hash_element_t *list_tmp,*list_tmp_next;//用于存放hashtable桶的元素：list_tmp从第一个开始，list_tmp_next用于保存下一个元素（用于纵向列表）
        int index;
        
        index = table->curhashelem->hashindex;//获取下标位置
        list_tmp = table->curhashelem->hashprev;//横向的前一个元素
        list_tmp_next = table->curhashelem->hashnext;

        if (list_tmp == 0)
        {
            table->element_table[index] = list_tmp_next;//设置为当前元素的下一个元素
            if (list_tmp_next != 0)//如果存在，则设置前一个元素为空，如果不存在下一个元素，相当于table[index] = 0
                list_tmp_next->hashprev = 0;
        }
        else //
        {
            list_tmp->hashnext = list_tmp_next;
            if (list_tmp_next != 0)
                list_tmp_next->hashprev = list_tmp;
        }

        
        list_tmp = table->curhashelem->listprev;
        list_tmp_next = table->curhashelem->listnext;

        if (list_tmp == 0) //要删除的元素为hash桶中为第一个元素
        {
            table->firsthashelem = list_tmp_next; //将要删除元素的下一个元素设置为第一个元素
            if (list_tmp_next != 0)//如果下一个元素存在，设置下一个元素的前一个元素为空
                list_tmp_next->listprev = 0;
            else //要删除的元素同时也是最后一个元素，说明只有一个元素，这时候相当于头和尾都设置为空
                table->lasthashelem = 0;
        }
        else
        {
            list_tmp->listnext = list_tmp_next;
            if (list_tmp_next != 0)
                list_tmp_next->listprev = list_tmp;
            else // table->curhashelem 为列表中的最后一个元素
                table->lasthashelem = list_tmp;
        }
        //删除当前元素所指向的内存
        if(table->curhashelem->b_need_free_value)
        {
            free(table->curhashelem->value);
        }
        free(table->curhashelem);
        table->curhashelem = list_tmp_next; // 设置当前元素指向下一个元素
    }
    else
        return HASH_TABLE_NO_CUR_ELEMENT;
    return 0;
}

void hash_table_custom_free(key_hash_table *table, free_hashtable_func free_func)
{
    if(table == NULL)  return;
    key_hash_element_t *list_tmp = NULL,*list_tmp_next = NULL;//用于存放hashtable桶的元素：list_tmp从第一个开始，list_tmp_next用于保存下一个元素（用于纵向列表）
    
    list_tmp = table->firsthashelem;
    while(list_tmp != 0)//释放元素内存空间
    {
        key_hash_element_t *hash_tmp,*hash_next_tmp; //用于保存横向hashtable的元素，可能多个不同的key，hash值是一样的，这时候就需要在桶中的同一个元素使用链表标识
        hash_tmp = list_tmp->hashnext;//
        while(hash_tmp != 0)
        {
            hash_next_tmp = hash_tmp->hashnext;
            free_func(hash_tmp->value);
            free(hash_tmp);
            hash_tmp = hash_next_tmp;
        }
        list_tmp_next = list_tmp->listnext;//获取hashtbale的下一个元素
        free_func(list_tmp->value);
        free(list_tmp);
        list_tmp = list_tmp_next;
    }
    table->firsthashelem = 0;
    table->lasthashelem = 0;
    table->curhashelem = 0;

    for (int i = 0 ; i < CKEYHASHTABLESIZE ; i++)
        table->element_table[i] = NULL;

    free(table);//释放table自身
}

int hash_table_add_element(key_hash_table* table,const uint32_t key,void *value,int bNeedFreeValue)
{
    if(table == NULL) return HASH_TABLE_NO_EXIST;
    key_hash_element_t *e,*newelem;
    int index = get_hash_table_index(key);//不同的元素可能获取到相同的index
    e = table->element_table[index];
    int found = 0;
    while(!found && e != 0)
    {
        if (e->key == key)
            found = 1;
        else
            e = e->hashnext;
    }
    if(!found)
    {
        //元素key不存在，往hash table中添加新元素
        newelem = (key_hash_element_t*)calloc(1, sizeof(key_hash_element_t));
        newelem->value = value;
        newelem->key = key;
        newelem->hashindex = index;
        newelem->b_need_free_value = bNeedFreeValue;
        if (newelem == 0)
            return HASH_TABLE_OUT_MEMORY;
        e = table->element_table[index];
        table->element_table[index] = newelem;
        newelem->hashnext = e;
        if (e != 0)
            e->hashprev = newelem;
        if (table->firsthashelem == 0)// hash列表中还不存在元素
        {
            table->firsthashelem = newelem;
            table->lasthashelem = newelem;
        }
        else //hash列表中已经存在一些元素
        {
            table->lasthashelem->listnext = newelem;
            newelem->listprev = table->lasthashelem;
            table->lasthashelem = newelem;
        }
    }else
    {

        if (table->cover_old_value)//替换元素
        {
            hash_table_goto_key_element(table, key);
            table->curhashelem->value = value;
        }
        else
        {
            return HASH_TABLE_KEYALREADYEXISTS;
        }
    }
    return 0;
}

int hash_table_goto_key_element(key_hash_table *table,const uint32_t key)
{
    if(table == NULL)
        return HASH_TABLE_NO_EXIST;
    int index = get_hash_table_index(key);//获取下标位置（hash 函数-如何根据key来得到hash的位置）
    table->curhashelem = table->element_table[index];
    int found = 0;
    while(!found && table->curhashelem != 0)
    {
        if (table->curhashelem->key == key)
            found = 1;
        else
            table->curhashelem = table->curhashelem->hashnext;
    }
    if (!found)
        return HASH_TABLE_NO_KEY_ELEMENT;
    return 0;
}

int hash_table_has_key_element(key_hash_table *table, const uint32_t key)
{
    if(table == NULL) return 0;
    key_hash_element_t *tmp;
    int index = get_hash_table_index(key);
    tmp = table->element_table[index];
    int found = 0;
    while(!found && tmp != 0)
    {
        if (tmp->key == key)
            found = 1;
        else
            tmp = tmp->hashnext;
    }
    return found;
}

int hash_table_del_key_element(key_hash_table *table, const uint32_t key)
{
    if(table == NULL) return HASH_TABLE_NO_EXIST;
    int status;
    status = hash_table_goto_key_element(table,key);
    if (status < 0)
        return status;
    return hash_table_del_cur_element(table);
}

void hash_table_goto_first_element(key_hash_table *table)
{
    if(table != NULL)
        table->curhashelem = table->firsthashelem;
}

void hash_table_goto_prev_element(key_hash_table *table)
{
    if(table && table->curhashelem)
        table->curhashelem = table->curhashelem->listprev;
}

void hash_table_goto_last_element(key_hash_table *table)
{
    if(table != NULL)
        table->curhashelem = table->lasthashelem;
}

void hash_table_goto_next_element(key_hash_table *table)
{
    if(table && table->curhashelem)
        table->curhashelem = table->curhashelem->listnext;
}

uint32_t hash_table_get_cur_key(key_hash_table *table)
{
    if(table != NULL && table->curhashelem != NULL)
        return table->curhashelem->key;
    return HASH_TABLE_NO_CUR_KEY;
}

void *hash_table_get_cur_element(key_hash_table *table)
{
    if(table != NULL)
        return  table->curhashelem->value;
    return NULL;
}

int hash_table_has_cur_element(key_hash_table *table)
{
    if(table != NULL)
        return (table->curhashelem == 0)? 0 : 1;
    return 0;
}

void test_hashtable()
{
    struct key_hash_table *hashtable = NULL;
    hash_table_new(&hashtable, 1);
    int a = 1;
    int b = 2 ;
    hash_table_add_element(hashtable,1,&a,0);
    hash_table_add_element(hashtable,1,&b,0);
    hash_table_add_element(hashtable,2,&b,0);
    hash_table_add_element(hashtable,3,&a,0);
    hash_table_del_key_element(hashtable,1);
    hash_table_del_key_element(hashtable,3);
    hash_table_del_key_element(hashtable,3);
    hash_table_goto_first_element(hashtable);
    while(hash_table_has_cur_element(hashtable))
    {
        int *c = (int *) hash_table_get_cur_element(hashtable);
        printf("c::%dn", *c);
        hash_table_goto_next_element(hashtable);
    }
    hash_table_free(hashtable);
}