字典与哈希表 | 自己实现Redis源代码(3)

通过对《Redis设计与实现》一书的学习，我打算动手自己实现一份“Redis源代码”作为自己的学习记录。

对 Redis 感兴趣的同学可以查看我的另一篇文章 造个轮子 | 自己动手写一个Redis 。

本章介绍的是Redis源代码中的字典及其内部哈希表的实现。

字典dict的实现

dict的API

（1）创建一个新的字典

dict dictCreate(dictType type,int hashSize);

（2）根据key寻找其在hashTable中对应的结点

dictEntry lookup(dict d,void *key);

（3）将给定的键值对添加到字典里面

（如果键已经存在于字典，那么用新值取代原有的值）

bool dictInsert(dict d, void key, void *val);

（4）返回给定的键的值

void dictFetchValue(dict d, void *key);

（5）从字典中删除给定键所对应的键值对

void dictDelete(dict d, void key);

（6）释放给定字典，以及字典中包含的所有键值对

void dictRelease(dict *d);

头文件

#ifndef __DICT_H
#define __DICT_H

//哈希表的结点使用dictEntry结构来表示
//每个dictEntry结构都保存着一个key-value
typedef struct dictEntry{
    //键
    void *key;
    //值
    void *value;
    //指向下个哈希表结点，形成链表——避免键冲突
    struct dictEntry *next;
}dictEntry;

//保存一组用于操作特定类型键值对的函数
typedef struct dictType {
    //计算哈希值的函数
    unsigned int (*hashFunction)(void *key,int size);
    //复制键的函数
    void *(*keyDup)(void *key);
    //复制值的函数
    void *(*valDup)(void *obj);
    //对比键的函数
    int (*keyCompare)(void *key1, void *key2);
    //销毁键的函数
    void (*keyDestructor)(void *key);
    //销毁值的函数
    void (*valDestructor)(void *obj);
} dictType;

//哈希表
typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    int size;
    //该哈希表已有结点的数量
    int used;
} dictht;

//字典
//其实字典就是对普通的哈希表再做一层封装
//增加了一些属性
typedef struct dict {
    //类型特定函数
    dictType *type;
    //哈希表
    dictht *ht;
} dict;

//创建一个新的字典
//需要传入哈希表的大小
dict *dictCreate(dictType *type,int hashSize);
//根据key寻找其在hashTable中对应的结点
dictEntry* lookup(dict *d,void *key);
//将给定的键值对添加到字典里面
//将给定的键值对添加到字典里面，如果键已经存在于字典，
//那么用新值取代原有的值
bool dictInsert(dict *d, void *key, void *val);
//返回给定的键的值
void *dictFetchValue(dict *d, void *key);
//从字典中删除给定键所对应的键值对
void dictDelete(dict *d, void *key);
//释放给定字典，以及字典中包含的所有键值对
void dictRelease(dict *d);

#endif

dict API的实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dict.h"

//哈希表的大小
#define HASHSIZE 10

//定义对哈希表进行相关操作的函数集
//计算哈希值的函数
unsigned int myHashFunction(void *key,int size){
    char* charkey=(char*)key;
    unsigned int hash=0;
    for(;*charkey;++charkey){
        hash=hash*33+*charkey;
    }
    return hash%size;
}
//复制键的函数
void *myKeyDup(void *key){
    return key;
}
//复制值的函数
void *myValDup(void *obj){
    return obj;
}
//对比键的函数
int myKeyCompare(void *key1, void *key2){
    char*charkey1=(char*)key1;
    char*charkey2=(char*)key2;
    return strcmp(charkey1,charkey2);
}
//销毁键的函数
void myKeyDestructor(void *key){
    //free(key);
}
//销毁值的函数
void myValDestructor(void *obj){
    //free(obj);
}

//创建一个新的字典
dict *dictCreate(dictType *type,int hashSize){
    dict* d=(dict*)malloc(sizeof(dict));
    //对hashTable进行相关操作的特定函数集
    if(type==NULL){
        printf("PIG Redis WARNING : Type is NULL.\n");
    }
    d->type=type;
    //哈希表初始化
    d->ht=(dictht*)malloc(sizeof(dictht));
    d->ht->size=hashSize;
    d->ht->used=0;
    d->ht->table=(dictEntry**)malloc(sizeof(dictEntry*)*hashSize);
    //全部结点都设为NULL
    for(int i=0;i<hashSize;i++){
        d->ht->table[i]=NULL;
    }
    return d;
}

//根据key寻找其在hashTable中对应的结点
dictEntry* lookup(dict *d,void *key){
    dictEntry* node;
    //该key在hashTable中对应的下标
    unsigned int index;
    index=d->type->hashFunction(key,d->ht->size);
    for(node=d->ht->table[index];node;node=node->next){
        if(!(d->type->keyCompare(key,node->key))){
            return node;
        }
    }
    return NULL;
}

//将给定的键值对添加到字典里面
bool dictInsert(dict *d, void *key, void *val){
    unsigned int index;
    dictEntry* node;
    if(!(node=lookup(d,key))){
        index=d->type->hashFunction(key,d->ht->size);
        node=(dictEntry*)malloc(sizeof(dictEntry));
        if(!node)return false;
        node->key=d->type->keyDup(key);
        node->next=d->ht->table[index];
        d->ht->table[index]=node;
    }
    //若存在,直接修改其对应的value值
    node->value=d->type->valDup(val);
    return true;
}

//返回给定的键的值
void *dictFetchValue(dict *d, void *key){
    unsigned int index;
    dictEntry* node;
    //找不到这个结点
    if(!(node=lookup(d,key))){
        return NULL;
    }
    return node->value;
}

//从字典中删除给定键所对应的键值对
void dictDelete(dict *d, void *key){
    dictEntry* node;
    dictEntry* temp;
    //该key在hashTable中对应的下标
    unsigned int index;
    index=d->type->hashFunction(key,d->ht->size);
    node=d->ht->table[index];
    //key相同
    if(!(d->type->keyCompare(key,node->key))){
        d->ht->table[index]=node->next;
        d->type->keyDestructor(node->key);
        d->type->valDestructor(node->value);
        free(node);
        return;
    }
    temp=node;
    node=node->next;
    while(node){
        if(!(d->type->keyCompare(key,node->key))){
            temp->next=node->next;
            d->type->keyDestructor(node->key);
            d->type->valDestructor(node->value);            
            free(node);
            return;
        }
        temp=node;
        node=node->next;
    }
    return;
}
//释放给定字典，以及字典中包含的所有键值对
void dictRelease(dict *d){
    dictEntry* node;
    dictEntry* temp;
    for(int i=0;i<d->ht->size;i++){
        node=d->ht->table[i];
        //printf("%d\n",i);
        while(node){
            char* t=(char*)node->value;
            //printf("%s\n",t);
            temp=node;
            node=node->next;
            d->type->keyDestructor(temp->key);
            d->type->valDestructor(temp->value);
            free(temp);
        }
    }
    free(d->ht);
    free(d->type);
    free(d);
}

/*int main(){
    dictType*type=(dictType*)malloc(sizeof(dictType));
    type->hashFunction=myHashFunction;
    type->keyDup=myKeyDup;
    type->valDup=myValDup;
    type->keyCompare=myKeyCompare;
    type->keyDestructor=myKeyDestructor;
    type->valDestructor=myValDestructor;
    dict* d=dictCreate(type,HASHSIZE);
    
    char*key1="sss";
    char*value1="111";
    bool result=dictInsert(d,key1,value1);
    if(result){
        printf("insert1 success\n");
    }else{
        printf("insert1 fail\n");
    }

    char*key2="3sd";
    char*value2="ddd";
    result=dictInsert(d,key2,value2);
    if(result){
        printf("insert2 success\n");
    }else{
        printf("insert2 fail\n");
    }

    char*key3="ddds";
    char*value3="1ss";
    result=dictInsert(d,key3,value3);
    if(result){
        printf("insert3 success\n");
    }else{
        printf("insert3 fail\n");
    }
    
    char *value4=(char*)dictFetchValue(d,key3);
    printf("---%s\n",value4);

    dictDelete(d,key3);
    value4=(char*)dictFetchValue(d,key3);
    printf("---%s\n",value4);

    dictRelease(d);
    system("pause");
    return 0;
}*/