内容简介:通过对《Redis设计与实现》一书的学习,我打算动手自己实现一份“Redis源代码”作为自己的学习记录。对Redis感兴趣的同学可以查看我的另一篇文章本章介绍的是Redis源代码中的字典及其内部哈希表的实现。
通过对《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; }*/
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。