公众号做漫画网站,西安市城乡建设管理局网站6,五金网站建设,茂名h5网站建设字典
概述
字典又称为符号表(symbol table)、关联数组(associative array)或映射(map)#xff0c;是一种保存键值对(key-value pair)的抽象数据结构#xff0c;在字典中#xff0c;一个键(key)可以和一个值(value)进行关联(或者说将键映射为值)#xff0c;这些关联的键和…字典
概述
字典又称为符号表(symbol table)、关联数组(associative array)或映射(map)是一种保存键值对(key-value pair)的抽象数据结构在字典中一个键(key)可以和一个值(value)进行关联(或者说将键映射为值)这些关联的键和值就称为键值对。字典中的每个键都是独一无二的程序可以在字典中根据键查找与之关联的值或者通过键来更新值又或者根据键来删除整个键值对等等
字典经常作为一种数据结构内置在很多高级编程语言里面但Redis所使用的C语言并没有内置这种数据结构因此Redis构建了自己的字典实现。字典在Redis中的应用相当广泛比如Redis的数据库就是使用字典来作为底层实现的对数据库的增删改查操作也是构建在对字典的操作之上的。
除了用来表示数据库之外字典还是哈希键的底层实现之一当一个哈希键包含的键值对比较多又或者键值对中的元素都是比较长的字符串时Redis就会使用字典作为哈希键的底层实现。
除了用来实现数据库和哈希键之外Redis的不少功能也用到了字典
例子
举个例子当我们执行代码中的命令之后会在数据库中创建一个键为msg值为hello world的键值对这个键值对就是保存在代表数据库的字典里面的。
redis SET msg hello world
OK举个例子website是一个包含3个键值对的哈希键这个哈希键的键都是一些数据库的名字而键的值就是数据库的主页网址:如代码所示。website键的底层实现就是一个字典字典中包含了3个键值对例如:Redis-Redis.io、MariaDB-MariaDB.org、MongoDB-MongoDB.org
redis HLEN webiste
(integer) 3
redis HGETALL website
1) Redis
2) Redis.io
3) MariaDB
4) MariaDB.org
5) MongoDB
6) MongoDB.org字典的实现
Redis的字典使用哈希表作为子层实现一个哈希表里面可以有多个哈希表节点而每个哈希表节点就保存了字典中的一个键值对
哈希表
Redis字典所使用的哈希表由dict.h/dictht结构定义:如代码所示 table属性是一个数组数组中的每个元素都是一个指向dict.h/dictEntry结构的指针每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小也即是table数组的大小而used属性则记录了哈希表目前已有节点(键值对)的数量。sizemask属性的值总是等于size-1,这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。
typedef struct dictht {// 哈希表数组dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩码用于计算索引值// 总是等于size -1unsigned long sizemask;// 该哈希表已有的数量unsigned long used;
}dictht;这是一个大小为4的空哈希表(没有包含任何键值对)
哈希表节点
哈希表节点使用dictEntry结构表示每个dictEntry结构都保存着一个键值对如代码所示.key属性保存着键值对中的键而v属性保存着键值对中的值其中键值对的值可以是一个指针或者是一个uint64_t整数又或者是一个int64_t整数。next属性是指向另一个哈希表节点的指针这个指针可以将多个哈希值相同的键值对连接在一起以此来解决键冲突(collision)的问题
typedef struct dictEntry {// 键void *key;union {void *val;uint64_t u64;int64_t s64;}v;// 指向下个哈希表节点形成链表struct dictEntry *next;} dictEntry;例子
举个例子该图就是通过next指针将两个索引值相同的键K1和K0连接在一起的
字典
Redis中的字典由dict.h/dict结构表示:如代码所示。 type属性和privdata属性是针对不同类型的键值对为创建多态字典而设置的:
1.type属性是一个指向dictType结构的指针每个dictType结构保存了一簇用于操作特定类型键值对 的函数Redis会为用途不同的字典设置不同的类型特定函数。2.而privdata属性则保存了需要传给那些类型特定函数的可选参数。
typedef struct dict {// 类型特定函数dictType *type;// 私有数据void *privdata;// 哈希表dictht ht[2];// rehash索引// 当rehash不在进行时值为-1int trehashidx; // rehasing not in progress if rehashidx -1
}dict;ht属性是一个包含两个项的数组数组中的每个项都是一个dictht哈希表一般情况下字典只使用ht[0]哈希表ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。除了ht[1]之外另一个和rehash有关的属性就是rehashidx它记录了rehash目前的进度如果目前没有在进行rehash那么它的值为-1.
typedef struct dictType {// 计算哈希值的函数unsigned int (*hashFunction)(const void *key);// 复制键的函数void *(*keyDup)(void *privdata, const void *key);// 复制值的函数void *(*valDup)(void *privdata, const void *obj);// 对比键的函数int (*keyCompare)(void *privdata,const void *key1, const void *key2);// 销毁键的函数void (*keyDestructor)(void *key);// 销毁值的函数void (*valDestructor)(void *privdata, void *obj);
}dictType;展示了一个普通状态下(没有进行rehash)的字典
哈希算法
当要将一个新的键值对添加到字典里面时程序需要先根据键值对的键计算出哈希值和索引值然后再根据 索引值将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。 Redis计算哈希值和索引值的方法如下: #使用字典设置的哈希函数计算键key的哈希值
hash dict-type-hashFunction(key);#使用哈希表的sizemask属性和哈希值计算出索引值 #根据情况不同ht[x]可以是ht[0]或者ht[1]
index hash dict-ht[x].sizemask;当字典被用作数据库的底层实现或者哈希键的底层实现时Redis使用MurmurHash2算法来计算键的哈希值的这种算法的优点在于即使输入的键是有规律的算法仍能给出一个很好的随机分布性并且算法的计算速度也非常快。
例子
举个例子如果要将一个键值对K0和V0添加到字典里面 那么程序会使用语句
hash dict-type-hashFunction(k0);计算k0的哈希值.假设计算得出的哈希值为8那么程序会继续使用语句:
index hash dict-ht[0].sizemask 8 3 0;计算出键K0的索引值0这表示包含键值对K0和V0的节点应该被放置到 哈希表数组真的索引0位置上如图所示
