redis 数据结构 字典

哈希表和字典 结构:要点rehash时机redis内的使用

哈希表和字典

我就不明白了，c里面没有，c++的stl里有啊，redis为什么要自己实现

结构:

/** * 哈希节点 **/ typedef struct dictEntry{ void *key;//键，任意类型 union{//值，三选一，或者是自定义val，或者是无符号64位整型，或者有符号64位整型 void *val; uint64_tu64;// ts64是啥 int64_ts64;//同，ts64是啥 } struct dictEntry *next; } /** * 哈希表 **/ typedef struct dictht{ dictEntry **table;//指向dictEntry数组的指针,*dictEntry是指向一个哈希节点，**dictEntry是指向一个节点数组的 unsigned long size;//数组的大小 unsigned long sizemark;//和java的hashMap一样，有一个掩码，大小等于size-1，用于落桶的计算 unsigned long used;//当前已有节点个数 } /** * 字典 **/ typedef struct dict{ /** type和privatedata是类型特定的函数 **/ dictType *type;//一个dictType内保存一组用于特定类型的hash计算、键比较，复制键值，删除键值的方法 void *privatedata;//保存向dictType内函数传参的参数，更多细节，还需向后看 /** end **/ dictht ht[2];//两个hashTable，一般ht[0]用于正常存储，另一个在rehash的时候被需要，rehash是一个长期的过程，所以，存在一段时间内，两个ht内都有数据的情况 int rehashIndex;//rehash时使用，表明当前需要操作的dictEntry数组的下标，当不在rehash的时候，该值为-1 }

要点

哈希表使用链表法解决hash冲突的问题，而且链表使用头插法，将最近的冲突节点放到链表头部，复杂度为o(1)，这里的链表是单链表 2 rehash，当达到负载因子的阈值的时候，启动rehash，redis的rehash不是一口气完成的，而是将其拆解到每一次对字典的操作(增删改查)当中，每一次rehash原哈希表的一个数组的链表到另一个哈希表中，这个时候rehashIndex的作用就是表明下一个将要进行rehash操作的数组下标。进行完rehash后，会将新的哈希表设为ht[0]使用

rehash时机

负载因子计算：和java 的hashmap一样，使用节点数/数组大小表示，需要注意的是，节点数不是已使用的桶(bucket)数量，也就是说，如果所有节点hash都一样，进而解决hash冲突放到同一个dictEntry的链表里，它们每一个都会被用于负载因子的计算。什么时候扩大：负载因子大于等于1，并且服务器没有执行BGSAVE,BGREWRITEAOF指令；或者服务器在执行BGSAVE或BGREWRITEAOF指令，并且负载因子大于等于5如何扩大：当前已有节点数*2的最近的2的幂次为什么要区别BGSAVE和BGREWRITEAOF指令?这两个指令会导致redis服务器启动子进程，而在子进程内，数据是和父进程共享的，只有需要改变时使用写时复制的方式将修改的数据新建一份，所以为了防止子进程新建数据，提高性能，会区别这两个指令。什么时候缩小：当负载因子小于0.1的时候如何缩小：当前已有节点数，的最近的2的幂次

redis内的使用

redis数据库本身，以及哈希键值等