Redis数据结构和对象（三）

Redis数据结构和对象（一）
Redis数据结构和对象（二）
Redis数据结构和对象（三）
Redis数据结构和对象（五）
Redis数据结构和对象（六）
Redis数据结构和对象（七）——对象

一，字典。

• 1,用途：表示数据库，哈希键的底层实现之一。
• 2,数据结构。
  
  • 1）哈希表结构。
    
  • 2）哈希表节点结构。
    
  • 3）字典结构。
    
  • 4）字典特定类型函数。
    
• 3，算法实现。
  
  • 1）哈希算法：根据键值对的键计算出哈希值和索引值。再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上。
  • 2）解决键冲突：使用链地址法解决冲突。多个哈希表节点可以用next指针构成一个单向链表。
  • 3）rehash。
    
    • 操作：
    • 为字典的ht[1]哈希表分配空间，分配的大小取决于所要执行的操作。
    • 将保存在ht[0]中的所有键值对重新计算哈希值和索引值然后放到ht[1]上面。
    • 迁移完成后，将ht[1]设置为ht[0]，然后ht[1]新建一个空白哈希表。
    • 哈希表的扩展
      
      • 无BGSAVE或者BGREWRITEAOF命令，且哈希表的负载因子大于等于1。
      • 服务器正在执行BGSAVE或者BGREWRITEAOF命令，且哈希表的负载因子大于等于5。
    • 哈希表的收缩。
      
      • 负载因子小于0.1
  • 4）渐进式rehash。
    
    • 步骤。
      
      • a) 为ht[1]分配空间。
      • b) 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0.
      • c) 除了执行特定的操作外，还会顺带将ht[0]哈希表在rehashidx索引上所有的键值对rehash到ht[1]，当rehash完成操作后，rehashidx属性的值加1。
      • d) 所有的键值对都完成后，rehashidx就会设定为-1，表示rehash操作已完成。
    • rehash期间执行的hash表操作。
      
      • 删除，查找，更新操作会在两个表上进行。如查找，先找ht[0],找不到就去找ht[1]。
      • 新增会只在ht[1]上进行。