(三)dict哈希结构1

昨天分析完adlist的Redis代码,今天马上马不停蹄的继续学习Redis代码中的哈希部分的结构学习,不过在这里他不叫什么hashMap,而是叫dict,而且是一种全新设计的一种哈希结构,他只是通过几个简单的结构体,再搭配上一些比较常见的哈希算法,就实现了类似高级语言中HashMap的作用了。也让我见识了一些哈希算法的实现,比如dbj hash的算法实现,俗称times33,算法,就是不停的*33,。这种算是一种超级简单的哈希算法。

下面说说给我感觉Redis代码中哈希实现的不是那么简单,中间加了一些东西,比如说dictType定义了一些字典集合操作的公共方法,我把dict叫做字典总类,也可以说字典操作类,真正存放键值对的叫dictEntry,我叫做字典集合,字典集合存放在哈希表中,叫dictht,下面给出一张结构图来理理思路。

下面给出2个文件的代码解析:

dict.h:

<span style="font-size:14px;">/* Hash Tables Implementation. 
 * 
 * This file implements in-memory hash tables with insert/del/replace/find/ 
 * get-random-element operations. Hash tables will auto-resize if needed 
 * tables of power of two in size are used, collisions are handled by 
 * chaining. See the source code for more information... :) 
 * 
 * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com> 
 * All rights reserved. 
 * 
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met: 
 * 
 *   * Redistributions of source code must retain the above copyright notice, 
 *     this list of conditions and the following disclaimer. 
 *   * Redistributions in binary form must reproduce the above copyright 
 *     notice, this list of conditions and the following disclaimer in the 
 *     documentation and/or other materials provided with the distribution. 
 *   * Neither the name of Redis nor the names of its contributors may be used 
 *     to endorse or promote products derived from this software without 
 *     specific prior written permission. 
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE. 
 */ 
 
#include <stdint.h> 
 
#ifndef __DICT_H 
#define __DICT_H 
 
/* 定义了成功与错误的值 */ 
#define DICT_OK 0 
#define DICT_ERR 1 
 
/* Unused arguments generate annoying warnings... */ 
/* dict没有用到时,用来提示警告的 */ 
#define DICT_NOTUSED(V) ((void) V) 
 
/* 字典结构体,保存K-V值的结构体 */ 
typedef struct dictEntry {  
 //字典key函数指针 
 void *key;  
 union {  
 void *val;  
 //无符号整型值 
        uint64_t u64;  
 //有符号整型值 
        int64_t s64;  
 double d;  
    } v;  
 //下一字典结点 
 struct dictEntry *next;  
} dictEntry;  
 
/* 字典类型 */ 
typedef struct dictType {  
 //哈希计算方法,返回整形变量 
    unsigned int (*hashFunction)(const void *key);  
 //复制key方法 
 void *(*keyDup)(void *privdata, const void *key);  
 //复制val方法 
 void *(*valDup)(void *privdata, const void *obj);  
 //key值比较方法 
 int (*keyCompare)(void *privdata, const void *key1, const void *key2);  
 //key的析构函数 
 void (*keyDestructor)(void *privdata, void *key);  
 //val的析构函数 
 void (*valDestructor)(void *privdata, void *obj);  
} dictType;  
 
/* This is our hash table structure. Every dictionary has two of this as we 
 * implement incremental rehashing, for the old to the new table. */ 
/* 哈希表结构体 */ 
typedef struct dictht {  
 //字典实体 
    dictEntry **table;  
 //表格可容纳字典数量 
    unsigned long size;  
    unsigned long sizemask;  
 //正在被使用的数量 
    unsigned long used;  
} dictht;  
 
/* 字典主操作类 */ 
typedef struct dict {  
 //字典类型 
    dictType *type;  
 //私有数据指针 
 void *privdata;  
 //字典哈希表,共2张,一张旧的,一张新的 
    dictht ht[2];  
 //重定位哈希时的下标 
 long rehashidx; /* rehashing not in progress if rehashidx == -1 */ 
 //当前迭代器数量 
 int iterators; /* number of iterators currently running */ 
} dict;  
 
/* If safe is set to 1 this is a safe iterator, that means, you can call 
 * dictAdd, dictFind, and other functions against the dictionary even while 
 * iterating. Otherwise it is a non safe iterator, and only dictNext() 
 * should be called while iterating. */ 
/* 字典迭代器,如果是安全迭代器,这safe设置为1,可以调用dicAdd,dictFind */ 
/* 如果是不安全的,则只能调用dicNext方法*/ 
typedef struct dictIterator {  
 //当前字典 
    dict *d;  
 //下标 
 long index;  
 //表格,和安全值的表格代表的是旧的表格,还是新的表格 
 int table, safe;  
 //字典实体 
    dictEntry *entry, *nextEntry;  
 /* unsafe iterator fingerprint for misuse detection. */ 
 /* 指纹标记,避免不安全的迭代器滥用现象 */ 
 long long fingerprint;  
} dictIterator;  
 
/* 字典扫描方法 */ 
typedef void (dictScanFunction)(void *privdata, const dictEntry *de);  
 
/* This is the initial size of every hash table */ 
/* 初始化哈希表的数目 */ 
#define DICT_HT_INITIAL_SIZE     4 
 
/* ------------------------------- Macros ------------------------------------*/ 
/* 字典释放val函数时候调用,如果dict中的dictType定义了这个函数指针, */ 
#define dictFreeVal(d, entry) \ 
 if ((d)->type->valDestructor) \  
        (d)->type->valDestructor((d)->privdata, (entry)->v.val)  
 
/* 字典val函数复制时候调用,如果dict中的dictType定义了这个函数指针, */ 
#define dictSetVal(d, entry, _val_) do { \ 
 if ((d)->type->valDup) \  
        entry->v.val = (d)->type->valDup((d)->privdata, _val_); \  
 else \  
        entry->v.val = (_val_); \  
} while(0)  
 
/* 设置dictEntry中共用体v中有符号类型的值 */ 
#define dictSetSignedIntegerVal(entry, _val_) \ 
 do { entry->v.s64 = _val_; } while(0)  
 
/* 设置dictEntry中共用体v中无符号类型的值 */ 
#define dictSetUnsignedIntegerVal(entry, _val_) \ 
 do { entry->v.u64 = _val_; } while(0)  
 
/* 设置dictEntry中共用体v中double类型的值 */ 
#define dictSetDoubleVal(entry, _val_) \ 
 do { entry->v.d = _val_; } while(0)  
 
/* 调用dictType定义的key析构函数 */ 
#define dictFreeKey(d, entry) \ 
 if ((d)->type->keyDestructor) \  
        (d)->type->keyDestructor((d)->privdata, (entry)->key)  
 
/* 调用dictType定义的key复制函数,没有定义直接赋值 */ 
#define dictSetKey(d, entry, _key_) do { \ 
 if ((d)->type->keyDup) \  
        entry->key = (d)->type->keyDup((d)->privdata, _key_); \  
 else \  
        entry->key = (_key_); \  
} while(0)  
 
/* 调用dictType定义的key比较函数,没有定义直接key值直接比较 */ 
#define dictCompareKeys(d, key1, key2) \ 
    (((d)->type->keyCompare) ? \  
        (d)->type->keyCompare((d)->privdata, key1, key2) : \  
        (key1) == (key2))  
 
#define dictHashKey(d, key) (d)->type->hashFunction(key)   //哈希定位方法 
#define dictGetKey(he) ((he)->key)    //获取dictEntry的key值 
#define dictGetVal(he) ((he)->v.val)  //获取dicEntry中共用体v中定义的val值 
#define dictGetSignedIntegerVal(he) ((he)->v.s64) //获取dicEntry中共用体v中定义的有符号值 
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)  //获取dicEntry中共用体v中定义的无符号值 
#define dictGetDoubleVal(he) ((he)->v.d)  //获取dicEntry中共用体v中定义的double类型值 
#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)  //获取dict字典中总的表大小 
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)   //获取dict字典中总的表的总正在被使用的数量 
#define dictIsRehashing(d) ((d)->rehashidx != -1)   //字典有无被重定位过 
 
/* API */ 
dict *dictCreate(dictType *type, void *privDataPtr);   //创建dict字典总类 
int dictExpand(dict *d, unsigned long size);    //字典扩增方法 
int dictAdd(dict *d, void *key, void *val);    //字典根据key, val添加一个字典集 
dictEntry *dictAddRaw(dict *d, void *key);     //字典添加一个只有key值的dicEntry 
int dictReplace(dict *d, void *key, void *val); //替代dict中一个字典集 
dictEntry *dictReplaceRaw(dict *d, void *key);  //替代dict中的一个字典,只提供一个key值 
int dictDelete(dict *d, const void *key);    //根据key删除一个字典集 
int dictDeleteNoFree(dict *d, const void *key);  //字典集删除无、不调用free方法 
void dictRelease(dict *d);   //释放整个dict 
dictEntry * dictFind(dict *d, const void *key);  //根据key寻找字典集 
void *dictFetchValue(dict *d, const void *key);  //根据key值寻找相应的val值 
int dictResize(dict *d);  //重新计算大小 
dictIterator *dictGetIterator(dict *d); //获取字典迭代器 
dictIterator *dictGetSafeIterator(dict *d);  //获取字典安全迭代器   
dictEntry *dictNext(dictIterator *iter);   //根据字典迭代器获取字典集的下一字典集 
void dictReleaseIterator(dictIterator *iter); //释放迭代器 
dictEntry *dictGetRandomKey(dict *d);  //随机获取一个字典集 
void dictPrintStats(dict *d);  //打印当前字典状态 
unsigned int dictGenHashFunction(const void *key, int len); //输入的key值,目标长度,此方法帮你计算出索引值 
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len); //这里提供了一种比较简单的哈希算法 
void dictEmpty(dict *d, void(callback)(void*)); //清空字典 
void dictEnableResize(void);  //启用调整方法 
void dictDisableResize(void); //禁用调整方法 
int dictRehash(dict *d, int n); //hash重定位,主要从旧的表映射到新表中,分n轮定位 
int dictRehashMilliseconds(dict *d, int ms);  //在给定时间内,循环执行哈希重定位 
void dictSetHashFunctionSeed(unsigned int initval); //设置哈希方法种子 
unsigned int dictGetHashFunctionSeed(void);  //获取哈希种子 
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata); //字典扫描方法 
 
/* Hash table types */ 
/* 哈希表类型  */ 
extern dictType dictTypeHeapStringCopyKey;  
extern dictType dictTypeHeapStrings;  
extern dictType dictTypeHeapStringCopyKeyValue;  
 
#endif /* __DICT_H */ 
</span>  

原文发布于微信公众号 - 高性能服务器开发(easyserverdev)

原文发表时间:2018-04-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏函数式编程语言及工具

SDP(9):MongoDB-Scala - data access and modeling

    MongoDB是一种文件型数据库,对数据格式没有硬性要求,所以可以实现灵活多变的数据存储和读取。MongoDB又是一种分布式数据库,与传统关系数据库不同...

40540
来自专栏GIS讲堂

geotools中shp和geojson格式的相互转换

1.1K30
来自专栏软件开发 -- 分享 互助 成长

CRC校验码

循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码也叫(N,K)码。对于一个给定的(N,K)码,可以证明...

32560
来自专栏码匠的流水账

聊聊storm的OpaquePartitionedTridentSpoutExecutor

本文主要研究一下storm的OpaquePartitionedTridentSpoutExecutor

9530
来自专栏码匠的流水账

聊聊flink的SourceFunction

flink-streaming-java_2.11-1.6.2-sources.jar!/org/apache/flink/streaming/api/func...

30830
来自专栏码匠的流水账

聊聊flink的CsvReader

flink-java-1.6.2-sources.jar!/org/apache/flink/api/java/ExecutionEnvironment.jav...

25320
来自专栏码匠的流水账

聊聊flink的CsvReader

flink-java-1.6.2-sources.jar!/org/apache/flink/api/java/ExecutionEnvironment.jav...

17620
来自专栏葡萄城控件技术团队

深入浅出OOP(五): C#访问修饰符(Public/Private/Protected/Internal/Sealed/Constants)

访问修饰符(或者叫访问控制符)是面向对象语言的特性之一,用于对类、类成员函数、类成员变量进行访问控制。同时,访问控制符也是语法保留关键字,用于封装组件。 Pub...

34790
来自专栏扎心了老铁

java优雅的使用elasticsearch api

本文给出一种优雅的拼装elasticsearch查询的方式,可能会使得使用elasticsearch的方式变得优雅起来,使得代码结构很清晰易读。 建立elast...

1.2K70
来自专栏高性能服务器开发

(二)结构体分析

继上次的redis源码分析(一)之后,本人开始订制着一份非常伟大的计划-啃完redis源代码,也对他进行了切块划分,鉴于本人目前对他的整个运行流畅还不特别清楚的...

35160

扫码关注云+社区

领取腾讯云代金券