字典与哈希表 | 自己实现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-valuetypedef 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);#endifdict 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=hash33+charkey; } return hash%size;}//复制键的函数void myKeyDup(void key){ return key;}//复制值的函数void myValDup(void obj){ return obj;}//对比键的函数int myKeyCompare(void key1, void key2){ charcharkey1=(char)key1; charcharkey2=(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(){ dictTypetype=(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); charkey1=“sss”; charvalue1=“111”; bool result=dictInsert(d,key1,value1); if(result){ printf(“insert1 success\n”); }else{ printf(“insert1 fail\n”); } charkey2=“3sd”; charvalue2=“ddd”; result=dictInsert(d,key2,value2); if(result){ printf(“insert2 success\n”); }else{ printf(“insert2 fail\n”); } charkey3=“ddds”; charvalue3=“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;}/