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

栏目: 数据库 · 发布时间: 5年前

内容简介:通过对《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;
}*/

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

匠心体验

匠心体验

[法] 艾米丽·布歇 / 吴 博 / 人民邮电出版社 / 2016-11 / 69.00元

本书针对在智能手机和平板电脑的网站及应用程序设计,详细剖析了移动终端服务的用户体验设计要点,阐述了营造舒适的感官体验、甄选内容及功能、提高用户效率、优化等待时间、合理实施教学、情感设计等方面的设计诀窍,并通过大量实例,呈现当今移动终端服务设计中的亮点与雷区。一起来看看 《匠心体验》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

MD5 加密
MD5 加密

MD5 加密工具