哈希表的C语言链表实现

• 1 哈希表的特点
• 2 代码实现
• • 2.1 链表部分
  • • 2.1.1 链表结点的结构
    • 2.1.2 创建链表
    • 2.1.3 销毁链表
    • 2.1.4 头插新结点
    • 2.1.5 根据id搜索链表
  • 2.2 Hash表部分
  • • 2.2.1 创建Hash表
    • 2.2.2 清空表中元素
    • 2.2.3 摧毁整个Hash表
    • 2.2.4 Hash函数
    • 2.2.5 插入哈希表
    • 2.2.6 根据key搜索Hash表返回数据
• 3 测试例程
• • 测试结果

1 哈希表的特点

结合了数组（索引快）和链表（可灵活增删结点）的优点。

2 代码实现

2.1 链表部分

2.1.1 链表结点的结构

typedef struct __tag_node{
    int id;
    struct  __tag_node *pNext;
    int satellite;
}Node;

2.1.2 创建链表

Node *LinkedList_Create(void)
{
    Node *p = malloc(sizeof(Node));
    if(p == NULL){
        return NULL;
    }
    p->pNext = NULL;
    p->id = 0; // The total quantity of nodes

    return p;
}

2.1.3 销毁链表

void LinkedList_Destroy(Node *list)
{
    Node *p = list->pNext; // Reserved header node
    while(p){
        Node *tmp = p;
        p = p->pNext;
        free(tmp);
    }
    list->pNext = NULL;
    list->id = 0;
}

2.1.4 头插新结点

/**
 * @brief Inserting a new node in the linked list
 * @param list, The linked list will be inserted
 * @param id, id number
 * @param the satellite value of the id
 **/
int LinkedList_InsertHead(Node *list, int id, int dat)
{
    Node *p = malloc(sizeof(Node *));
    if(p == NULL){
        return -1;
    }
    p->id = id;
    p->pNext = list->pNext;
    list->pNext = p;

    p->satellite = dat;

    return 1;
}

2.1.5 根据id搜索链表

/**
 * @brief search the id
 * @param list, The hash table will be searched
 * @param key, key
 * @retval the satellite value of the id
 **/
int LinkedList_Search(Node *list, int id)
{
    Node *p = list->pNext;

    for(Node *p = list->pNext; p; p = p->pNext){
        if(id == p->id){
            return p->satellite;
        }
    }

    return 0;
}

2.2 Hash表部分

2.2.1 创建Hash表

Node **HashTable_Create(int len)
{
    Node **p = malloc(len * sizeof(Node *));
    for(int i = 0; i < len; i++){
        p[i] = LinkedList_Create();
    }

    return p;
}

2.2.2 清空表中元素

void HashTable_Clear(Node **arr, int len)
{
    for(int i = 0; i < len; i++){
        LinkedList_Destroy(*(arr+i));
    }
}

2.2.3 摧毁整个Hash表

void HashTable_Destroy(Node **arr, int len)
{
    HashTable_Clear(arr, len);
    for(int i = 0; i < len; i++){
        free(arr[i]);
    }
    free(arr);
}

2.2.4 Hash函数

int HashTable_hashFunc(int key, int len)
{
    return key % len;
}

2.2.5 插入哈希表

int HashTable_Insert(int key, int value, Node **table, int length)
{
    if(LinkedList_InsertHead(table[HashTable_hashFunc(key, length)], key, value)){
        return 1;  // Success
    }else{
        return -1; // Failure
    }
}

2.2.6 根据key搜索Hash表返回数据

/**
 * @brief search the key
 * @param table, The hash table will be searched
 * @param length, The length of the hash table
 * @retval the value of the key
 **/
int HashTable_Search(int key, Node **table, int length)
{
    return LinkedList_Search(table[HashTable_hashFunc(key, length)], key);
}

3 测试例程

#define __MAX_LEN_TABLE_ 10

int main(int argc, char *argv[])
{
    Node **pHashTable;
    pHashTable = HashTable_Create(__MAX_LEN_TABLE_);

    if(HashTable_Insert(12, 125, pHashTable, __MAX_LEN_TABLE_)){
        printf("Insert key = 12, value = 125 successful!\r\n");
    }else{
        printf("Insert key = 12 fail!\r\n");
    }

    if(HashTable_Insert(22, 255, pHashTable, __MAX_LEN_TABLE_)){
        printf("Insert key = 22, value = 255 successful!\r\n");
    }else{
        printf("Insert key = 255 fail!\r\n");
    }

    int value = HashTable_Search(22, pHashTable, __MAX_LEN_TABLE_);
    printf("value of key=22 is %d\r\n", value);

    value = HashTable_Search(12, pHashTable, __MAX_LEN_TABLE_);
    printf("value of key=12 is %d\r\n", value);

    HashTable_Destroy(pHashTable, __MAX_LEN_TABLE_);
    
    return 0;
}

测试结果