哈希表开散列与闭散列的实现代码

闭散列

hash1.c

#include "hash1.h"
#include <stdio.h>
#include <stddef.h>


void HashInit(HashTable* ht, HashFunc hash_func){
    if(ht == NULL){
        return;
    }
    ht->size = 0;
    ht->func = hash_func;
    size_t i = 0;
    for(; i < HashMaxSize; ++i){
        ht->data[i].stat = Empty; 
    }
    return;
}

void HashDestroy(HashTable* ht){
    if(ht == NULL){
        return;
    }
    ht->size = 0;
    ht->func = NULL;
    size_t i = 0;
    for(; i < HashMaxSize; i++){
        ht->data[i].stat = Empty;
    }        
    return;
}

void HashInsert(HashTable* ht, KeyType key, ValType value){
    if(ht == NULL){
        return;
    }

    //设置负载因子为0.8
    if(ht->size >= 0.8 * HashMaxSize){
        //表示大于负载因上限
        return;
    }

    size_t offset = ht->func(key);
    while(1){
        if(ht->data[offset].stat != Valid){
            ht->data[offset].key = key;
            ht->data[offset].stat = Valid;
            ht->data[offset].value = value;
            ++ht->size;
        }else if(ht->data[offset].stat == Valid && ht->data[offset].key == key){
            //如果遇到key值相同的，插入失败
            return;
        }else{
            //线性探测找到下一个有效位置
            offset++;
            if(offset > HashMaxSize){
                offset = 0;
            }
        }
    }
    return;
}

int HashFind(HashTable* ht, KeyType key, ValType* value){
    if(ht == NULL){
        return 0;
    }
    if(ht->size == 0){
        return 0;
    }
    size_t offset = ht->func(key);
    while(1){
        if(ht->data[offset].key == key && ht->data[offset].stat == Valid){
            *value = ht->data[offset].value;
            return 1;
        }else if(ht->data[offset].stat == Empty){
            return 0;
        }else{
            ++offset;
            offset = offset > HashMaxSize ? 0 : offset;
        }
    }
    return 0;
}

void HashRemove(HashTable* ht, KeyType key){
    if(ht == NULL){
        return;
    }
    if(ht->size == 0){
        //空的哈希表
        return;
    }
    size_t offset = ht->func(key);
    while(1){
        if(ht->data[offset].key == key && ht->data[offset].stat == Valid){
            ht->data[offset].stat = Deleted;
            --ht->size;
            return;
        }else if(ht->data[offset].stat == Empty){
            //如果当前状态为空，表示查找失败
            return;
        }else{
            //线性地向下探测
            ++offset;
            offset = offset > HashMaxSize ? 0 : offset;
        }
    }
}

void HashPrnit(HashTable* ht, const char* message){
    if(ht == NULL || message == NULL){
        return;
    }
    printf("[%s]\n", message);
    size_t i = 0;
    for(;i <= ht->size; i++){
        if(ht->data[i].stat == Empty){
            continue;
        }
        printf("[%lu, %d : %d]\n", i, ht->data[i].key, ht->data[i].value);
    }
    return;
}

hash1.h

#pragma once
#include <stdio.h>
#include <stddef.h>

#define TestType printf("\n######################### %s ############################\n",__FUNCTION__)

//我们存放的是键值对
#define HashMaxSize 1000

typedef enum{
    Empty, //空状态
    Deleted, //被删除状态
    Valid, //有效状态
} Stat;

typedef int KeyType;
typedef int ValType;

typedef size_t (*HashFunc)(KeyType key);

//这个结构体表示哈希表中的一个元素
typedef struct HashElem{
   KeyType key;
   ValType value;
   Stat stat;
} HashElem;

//[0, size)不能表示有效元素
typedef struct HashTable{
    HashElem data[HashMaxSize];
    size_t size;
    HashFunc func;
} HashTable;

void HashInit(HashTable* ht, HashFunc hash_func);

void HashDestroy(HashTable* ht);

void HashInsert(HashTable* ht, KeyType key, ValType value);

int HashFind(HashTable* ht, KeyType key, ValType* value);

void HashRemove(HashTable* ht, KeyType key);

void HashPrnit(HashTable* ht, const char* message);

main1.c

#include "hash1.h"
#include <stdio.h>

size_t HashFuncDefault(KeyType key){
    return key % HashMaxSize;
}

void TestInit(){
    TestType;
    HashTable ht;
    HashInit(&ht, HashFuncDefault);
    printf("size expected 0, actual %lu\n", ht.size);
    printf("func expected %p, actual %p\n", HashFuncDefault, ht.func);
    return;
}

void TestHashDestroy(){
    TestType;
    HashTable ht;
    HashInit(&ht, HashFuncDefault);
    HashDestroy(&ht);
    printf("size expected 0, actual %lu\n", ht.size);
    printf("func expected NULL, actual %p\n",ht.func);
    return;
}

void TestHashRemove(){
    TestType;
    HashTable ht;
    HashInit(&ht, HashFuncDefault);
    HashInsert(&ht, 1, 1);
    HashInsert(&ht, 2, 2);
    HashInsert(&ht, 1001, 11);
    HashPrnit(&ht, "删除前");
    HashRemove(&ht, 1001);
    HashPrnit(&ht, "删除后");
    return;
}

void TestHashInsert(){
    TestType;
    HashTable ht;
    HashInit(&ht, HashFuncDefault);
    HashInsert(&ht, 1, 1);
    HashInsert(&ht, 1, 10);
    HashInsert(&ht, 2, 2);
    HashInsert(&ht, 1001, 11);
    HashInsert(&ht, 1002, 12);
    HashPrnit(&ht, "插入元素");
    return;
}

void TestFind(){
    TestType;
    HashTable ht;
    HashInit(&ht, HashFuncDefault);
    HashInsert(&ht, 1, 1);
    HashInsert(&ht, 1, 10);
    HashInsert(&ht, 2, 2);
    HashInsert(&ht, 1001, 11);
    HashInsert(&ht, 1002, 12);
    int value = 0;
    int ret = HashFind(&ht, 1002, &value);
    printf("ret expected is 1, actual %d\n", ret);
    printf("value epected is 12, actual %d\n", value);
    return;
}

int main(){
    TestInit();
    TestHashDestroy();
    TestHashInsert();
    TestFind();
    TestHashRemove();
    return 0;
}

开散列

hash2.h

#pragma once
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>

#define HASHMAXSIZE 1000

#define TestType printf("\n############################## %s ###############################\n", __FUNCTION__)

typedef int KeyType;
typedef int ValType;

typedef size_t (*HashFunc)(KeyType key);

typedef struct HashElem{
    KeyType key;
    ValType value;
    struct HashElem* next;
} HashElem;

typedef struct HashTable{
    HashElem* data[HASHMAXSIZE];
    size_t size;
    HashFunc func;
} HashTable;

void HashInit(HashTable* ht, HashFunc HashFuncDefault);

void HashDestroy(HashTable* ht);

HashElem* HashBucketFind(HashElem* Elem, KeyType to_find);

void HashInsert(HashTable* ht, KeyType key, ValType value);

int HashFind(HashTable* ht, KeyType key, ValType* value);

int HashSize(HashTable* ht);

void HashPrint(HashTable* ht,const char* msg);

void HashRemove(HashTable* ht, KeyType key);

size_t HashFuncDefault(KeyType key);

hash2.c

#include "hash2.h"

HashElem* CreateHashElem(KeyType key, ValType value){
    HashElem* new_node = (HashElem*)malloc(sizeof(HashElem));
    new_node->key = key;
    new_node->value = value;
    new_node->next = NULL;
    return new_node;
}

size_t HashFuncDefault(KeyType key){
    return key % HASHMAXSIZE;
}

void DestroyHashElem(HashElem* hash){
    free(hash);
    return;
}

void HashInit(HashTable* ht, HashFunc HashFuncDefault){
    if(ht == NULL){
        return;
    }
    ht->func = HashFuncDefault;
    ht->size = 0;
    size_t i = 0;
    for(;i < HASHMAXSIZE; i++){
        ht->data[i] = NULL;
    }
    return;
}

void HashDestroy(HashTable* ht){
    if(ht == NULL){
        return;
    }
    ht->func = NULL;
    ht->size = 0;
    size_t i = 0;
    for(; i < HASHMAXSIZE; i++){
        HashElem* cur = ht->data[i];
        while(cur != NULL){
            HashElem* tmp = cur;
            cur = cur->next;
            DestroyHashElem(tmp);
            tmp = NULL;
        }
    }
}

HashElem* HashBucketFind(HashElem* Elem, KeyType to_find){
    if(Elem == NULL){
        return NULL;
    }

    HashElem* cur = Elem;
    for(; cur != NULL; cur = cur->next){
        if(cur->key == to_find){
            break;
        }
    }
    return cur == NULL ? NULL : cur;

}

void HashInsert(HashTable* ht, KeyType key, ValType value){
    if(ht == NULL){
        return;
    }
    //根据key算出offset
    size_t offset = ht->func(key);
    HashElem* ret = HashBucketFind(ht->data[offset], key);
    if(ret != NULL){
        //返回值不为空，表示已经有key
        return;
    }

    HashElem* new_node = CreateHashElem(key, value);
    new_node->next = ht->data[offset];
    ht->data[offset] = new_node;
    ++ht->size;
    return;
}

int HashFind(HashTable* ht, KeyType key, ValType* value){
    if(ht == NULL || value == NULL){
        return -1;
    }
    size_t offset = ht->func(key);
    HashElem* ret = HashBucketFind(ht->data[offset], key);
    if(ret == NULL){
        return 0;
    }
    *value = ret->value;
    return 1;
}

int HashSize(HashTable* ht){
    if(ht == NULL){
        return 0;
    }
    return ht->size;
}

int HashBucketFindEx(HashElem* head, KeyType to_find, HashElem** pre_node, HashElem** cur_node){
    HashElem* pre = NULL;
    HashElem* cur = head;
    for(;cur != NULL; pre = cur, cur = cur->next){
        if(cur->key == to_find){
            break;
        }
    }
    if(cur == NULL){
        return 0;
    }
    *cur_node = cur;
    *pre_node = pre;
    return 1;
}

void HashRemove(HashTable* ht, KeyType key){
    if(ht == NULL){
        return;
    }
    if(ht->size == 0){
        return;
    }
    size_t offset = ht->func(key);
    HashElem* pre = NULL;
    HashElem* cur = NULL;
    int ret = HashBucketFindEx(ht->data[offset], key, &pre, &cur);
    if(ret == 0){
        return;
    }
    if(pre == NULL){
        ht->data[offset] = cur->next;
    }else{
        pre->next = cur->next;
    }
    DestroyHashElem(cur);
    ht->size--;
    return;
}

void HashPrint(HashTable* ht,const char* msg){
    if(ht == NULL){
        return;
    }
    printf("[%s:]\n",msg);
    size_t i = 0;
    for(; i < HASHMAXSIZE; ++i){
        if(ht->data[i] == NULL){
            continue;
        }
        printf("%lu\n",i);
        HashElem* cur = ht->data[i];
        for(;cur != NULL; cur = cur->next){
            printf("[%d:%d] ", cur->key, cur->value);
        }
        printf("\n");
    }
    return;
}

main2.c

#include "hash2.h"
#include <stdio.h>


void TestHashInit(){
    TestType;
    HashTable ht;
    HashInit(&ht,HashFuncDefault);
    printf("func expected %p, actual %p\n", HashFuncDefault, ht.func);
    printf("size expected 0, actual %lu\n",ht.size);
    return;
}

void TestHashDestroy(){
    TestType;
    HashTable ht;
    HashDestroy(&ht);
    printf("func expected NULL, actual %p\n", ht.func);
    printf("size expected 0, actuall %lu\n",ht.size);
    return;
}

void TestHashInsert(){
    TestType;
    HashTable ht;
    HashInit(&ht, HashFuncDefault);
    HashInsert(&ht, 2, 10);
    HashInsert(&ht, 10, 13);
    HashInsert(&ht, 12, 14);
    HashInsert(&ht, 13, 15);
    HashPrint(&ht, "打印哈希表");
    return;
}

void TestHashFind(){
    TestType;
    HashTable ht;
    HashInit(&ht, HashFuncDefault);
    HashInsert(&ht, 2, 10);
    HashInsert(&ht, 10, 13);
    HashInsert(&ht, 12, 14);
    HashInsert(&ht, 13, 15);
    int Val;
    int ret = HashFind(&ht,13, &Val );
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect 15, actual %d\n", Val);
    return;
}

void TestHashRemove(){
    HashTable ht;
    HashInit(&ht, HashFuncDefault);
    HashInsert(&ht, 2, 10);
    HashInsert(&ht, 10, 13);
    HashInsert(&ht, 12, 14);
    HashInsert(&ht, 13, 15);
    HashPrint(&ht, "删除前");
    HashRemove(&ht,12);
    HashPrint(&ht, "删除后");
    return;
}

int main(){
    TestHashInit();
    TestHashDestroy();
    TestHashInsert();
    TestHashFind();
    TestHashRemove();
    return 0;
}