redis(3)字典

1、字典，又称符号表（symbol table）、关联数组（associative array）、或者映射（map）,是一种用于保存键值对（key-value pair）的抽象数据结构。使用场景，string hash
2、在字典中，一个键（key）可以和一个值（value）进行关联，称为键值对。
3、字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，通过键来更新值，或者根据键来删除整个键值对。
4、Redis所使用c语言没有这种数据结构，因此redis构建了自己的字典实现。
5、字典实现

5.1、哈希表
table属性是一个数组，数组中的每一个元素是指向一个dictEntry结构的指针，每个dictEntry,保存着一个键值对
size记录hash表大小，即table大小used目前已有节点的数量，sizemask总是等于size-1

h1.jpg h2.jpg

5.2、hash表节点
key属性保存着键值对的键，v则保存着值，值可以是一个指针，比如指向一个字符串对象，或者一个64位整数，或者32位整数，next指向另一个hash表节点指针，以此来解决冲突

h3.jpg

6.1、字典
type和privdata是针对不同类型的键值对，为创建多态字典而设置。type属性是一个指向dictType结构指针
privdata属性则保存需要传给那些类型函数的可选参数
ht属性是一个包含两个项的数组，数组中的每个项是一个dictht哈希表，ht[0]哈希表，ht[1]只在rehash的时候使用，rehashidx记录rehash进度。没有rehash的时候值-1.

h4.jpg

6.2、哈希算法
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
假设hash值=8 8 & ht[0].sizemask

6.3、解决键冲突
当有两个或以上数量的键被分配到了哈希表数组的同一索引上面时，我们称为键发生了冲突（collision）。
redis的哈希表使用链表地址法（separate chaining）来解决冲突，通过next指针构成一个单向链表。这就解决了键冲突的问题。

6.4、rehash
当hash表键值对数量太多或者太少时，程序需要对hash表的大小进行相应的扩展或者收缩。扩展和收缩哈希表的工作可以通过rehash重新散列操作完成。
6.4.1、ht[1]分配空间 = ht[0].used，如果扩展 ,ht[1] 大小为第一个大于等于ht[0].used*2的n 次方幂
6.4.2、将保存在ht[0]中所有的键值对rehash到ht[1]上面，当全部迁移到ht[1],ht[0] ht[1] 互换名称
负载银子 = 哈希表以保存节点数量/哈希表大小

7、渐进式rehash,当数据量小时候，可以一次性完毕，但是当数据量是百万，千万，甚至更多，需要利用rehashidx进行渐进式rehash