做维修广告在哪个网站,建设一个网站首先需要,如何韩国视频网站模板下载 迅雷下载地址,dedecms 金融类网站模板前言 字典又称符号表#xff0c;关联数组或者映射(map)。是一种保存键值对的抽象数据结构。在字典中一个键和一个值进行关联。这些关联的值被称为键值对。 字典中每一个键都是独一无二的#xff0c;没有重复的。我们可以通过键来查找值#xff0c;更新值或者删除整个键值对等…前言 字典又称符号表关联数组或者映射(map)。是一种保存键值对的抽象数据结构。在字典中一个键和一个值进行关联。这些关联的值被称为键值对。 字典中每一个键都是独一无二的没有重复的。我们可以通过键来查找值更新值或者删除整个键值对等操作。 字典在Redis中应用广泛比如Redis数据库的底层就是使用字典来实现的。对数据库的增删查改该操作也是构建在对字典的操作之上。 出来用来表示数据库外字典还是哈希键(说的是Redis的key)的底层实现之一当一个哈希键包含的哈希键比较多又或者键值对中的元素都是比较长的字符串时Redis会使用字典作为哈希键的底层实现。 由于Redis是用C语言实现的没有内置字典数据结构Redis自己构建了字典的实现。
一.字典的实现 Redis的字典使用作为底层实现每一个哈希表节点就保存了字典中的一个键值对。 1.1 哈希表 Redis字典所使用的哈希表有dict.h/dictht结构来定义
/* 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;//哈希表大小掩码用于计算索引值//总是等于size-1unsigned long sizemask;//该哈希表已有的节点数unsigned long used;
} dictht;
table: 是一个数组数值中的每一个元素都是指向dictEntry类型指针每一个dictEntry中都保存着一个键值对。size: 记录了哈希表的大小也就是table的大小。used: 记录了哈希表中已有的节点(键值对)数。sizemask: 值总是等于size-1这个属性和哈希值共同决定了一个键应该被放到table数组的哪一个索引上。 1.2 哈希表节点 哈希表的节点使用dictEntry结构表示每一个dictEntry都保存这一个键值对
typedef struct dictEntry {//键void *key;//值union {void *val;uint64_t u64;int64_t s64;double d;} v;//指向下一个节点形成链表struct dictEntry *next;
} dictEntry;
key: 保存键值对中的键v: 保存键值对中的值。可以是一个指针或者是上面的三种类型next: 指向另一个哈希表节点的指针可以将哈希值相同的节点连接到一起解决哈希冲突。 1.3 字典 Redis的字典由dict.h/dict结构表示
typedef struct dict {//类型特定函数dictType *type;//私有数据void *privdata;//哈希表dictht ht[2];//rehash索引//当rehash不在进行时值为-1long rehashidx; /* rehashing not in progress if rehashidx -1 *///rehash中断标志//大于0表示rehash被中断int16_t pauserehash; /* If 0 rehashing is paused (0 indicates coding error) */
} dict; type和privdata属性是针对不同类型的键值对为创建多态字典而设置的
type: 属性是指向一个dictType结构的指针每一个dictType结构中保存了一簇用于操作特定类型键值对的函数Redis会为用途不同的字典设置不同类型的特定函数。privdata: 属性保存了需要传给那些类型特定函数的可选参数。
typedef struct dictType {//计算哈希值函数uint64_t (*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 *privdata, void *key);//销毁值函数void (*valDestructor)(void *privdata, void *obj);int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;
ht属性: 是一个包含两个项的数组每一个项都是一个dict哈希表。一般情况下字典只是用ht[0]哈希表ht[1]只会在对对ht[0]进行rehash时使用。rehashidx: 记录rehash进度如果没有进行rehash该值为-1。 1.4 哈希算法 当将一个新键值对添加到字典时程序需要先根据键值对的键计算出哈希值和索引值。然后再根据索引值将包含新键值对的哈希表的节点放在哈希表数组指定索引上。
//Redis计算哈希值和索引值方法
//使用字典设置的哈希函数计算key的哈希值
hash dict-type-hashFunction(key);//使用哈希表的sizemask属性和哈希值计算出索引值
//根据情况不同ht[x]可以是ht[0]或ht[1]
index hash dict-ht[x].sizemask; 当字典被作为数据库或者哈希见底层实现时Redis使用的是MurmurHash算法来计算键的哈希值。MurmurHash算法是由Austin Appleby于2008年发明这种算法有点在于即使输入的键是有规律的算法仍然能给出很好的随机分布而且算法速度也很快。MurmurHash现在也有很多版本。 1.5 解决键冲突 当由两个或者两个以上的键被分配到哈希表的同一个索引上我们称这些键发生了冲突。 Redis的哈希表使用链地址法来解决键冲突。实际Redis的哈希表是一个哈希桶哈希表的节点中有一个next指针冲突的键会以单向链表的方式连接在哈希表的同一索引位置。 程序会使用头插法将新节点加到链表中。 哈希表介绍链接【精选】哈希表(散列表)介绍_hash表_两片空白的博客-CSDN博客 1.6 rehash 1.6.1 步骤 随着操作的不断进行哈希表保存的键值对会逐渐地增多或者减少。为了让哈希表的负载因子维持在一个合理范围内当哈希表保存的键值对的数量太多或者太少时程序需要对哈希表的大小进行扩展或者收缩。 扩展和收缩操作可以通过执行rehash(重新排列)操作来完成。Redis对字典的哈希表的rehash步骤如下 1. 为字典的ht[1]哈希表分配空间这个哈希表的空间大小取决于要执行的操作以及ht[0]中当前包含的键值对的数量(也就是ht[0]中used属性的值)。
如果执行的是扩展操作那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂。比如used为33*2等于6第一个大于等于6的2的n次方幂为8ht[1]的大小为8。如果执行的是收缩操作那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂。 2. 将保存在ht[0]中的所有键值对rehash到ht[1]上rehash是指以ht[1]哈希表重新计算键的哈希值和索引值然后将键值对按照索引放到ht[1]指定位置。 3. 将ht[0]包含的所有键值对都迁移到ht[1]后ht[0]就变成了一个空的哈希表。释放ht[0]空间将ht[1]设置为ht[0]并在ht[1]新创建一个空的哈希表为下一次rehash做准备。 举个例子 假设程序要对下面的字典的ht[0]进行扩展操作那么程序会进行以下操作 ht[0].used当前的值为44*28正好是2的3次幂所以程序会将ht[1]哈希表的大小设置为8。下图为分配空间之后的样子 将ht[0]包含的4个键值对都rehash到ht[1] 释放ht[0]将ht[1]设置为ht[0]然后为ht[1]分配一个空哈希表。至此对哈希表的扩展执行完毕程序成功将哈希表的大小从原来的4扩展到8。 1.6.2 哈希表的扩展和收缩 1. 当以下任意一个条件满足时程序会自动开始对哈希表执行扩展操作
redis服务器目前没有进行BGSAVE命令或者BGREWRITEAOF命令并且哈希表的负载因子大于等于1。redis服务器正在进行BGSAVE命令或者BGREWRITEAOF命令并且哈希表的负载因子大于等于5。 哈希表的负载因子公式load_factor ht[0].used / ht[0].size 根据BGSAVE命令或者BGREWRITEAOF命令是否正在执行服务器执行扩展操作的负载因子不同这是因为在执行BGSAVE命令或者BGREWRITEAOF命令的过程中Redis需要创建当前服务器进程的子进程而大多数操作系统都是通过写时复制技术来优化子进程效率。所以在子进程存在期间服务器会提高执行扩展操作所需的负载因子为了避免子进程存在期间进行哈希表的扩展操作从而避免不必要的内存写入最大限度的节约内存。 2. 当哈希表的负载因子小于0.1时程序自动开始对哈希表进行收缩操作。 1.7 渐进式rehash 1.7.1 步骤 在字典进行扩展和收缩操作时需要将哈希表ht[0]上所有键值对rehash到ht[1]上但是rehash的动作并不是一次性集中完成的而是分多次渐进式完成的。 原因是当哈希表中保存的键值对数量很大那么要一次性的将所有键值对全部rehash到ht[1]的话庞大的计算量可能会导致服务器在一段时间内停止服务。 哈希表渐进式rehash的详细步骤
为ht[1]分配空间让字典同时拥有ht[0]和ht[1]两个哈希表。在字典中维持一个rehashindex索引计数器变量并把它设置为0表示rehash工作正式开始。在rehash进行期间每次对字典进行查找删除插入或者更新操作时程序除了执行指定的操作外还会顺带将ht[0]哈希表在rehashindex所索引上的所有键值对rehash到ht1[1]上当rehash工作完成之后程序将rehashindex属性值加一。随着字典的操作的不断执行最终在某个时间点上ht[1]哈希表上的所有键值对全部被rehash到ht[1]上这时程序将rehashindex属性值设为-1表示rehash操作已经完成。 渐进式rehash好处在于它采用分而治之的方式将rehash键值对所需要的计算工作均摊到对字典进行查找插入删除或更新操作上从而避免集中式rehash带来的庞大工作量。 rehash演示 1.7.2 渐进式rehash期间对哈希表的操作 因为在rehash期间字典中同时存在ht[0]和ht[1]两张哈希表。字典在进行查找插入删除和更新操作时会在两个哈希表上进行操作。例如在字典中查找某一个键时程序会先在ht[0]中查找如果没有找到会继续再ht[1]中查找。 另外再rehash期间新增到字典中的键值对一律会保存到ht[1]中而ht[0]不会进行任何添加操作这一操作保证了ht[0]包含的键值对的数量只减不增并且随着rehash操作最终会变成一个空表。 1.8 API
