字典与哈希表 | 自己实现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;
}*/