使用

1，redis的db space就是一个大map 2， hash value

定义

typedef struct dictht { dictEntry **table; unsigned long size; unsigned sizeMask;//size-1, eg: 0xFFFFFF unsigned long used; } dictht; struct dictEntry { void *key; union { void *value uint64_t u64; int64_t s64; } v; struct dictEntry *next; }; struct dict { dictType *type; void *private; dictht ht[2];//用来hash扩容的时候一个old一个new int trehashidx; //hash扩张的时候 } struct dictType { ... unsigned int (*hashFunction)(void *key); int (*keyCompare) (void *private, void *key1, void *key2); ... }

hash用的数组+链表来解决冲突 type用来指示 key value的类型 dictType包含了一系列对hash的key/value 操作的函数，没有面向对象的虚函数，只能这样搞 hashFunction一般使用murmurHash3

因为dictEntry没有指向tail的指针，所以总是头部插入 因为没有items数据，所以无法直接获取map的数量

rehash

当ht[0] size和used相差太大的时候，执行rehash，此时会把ht[1]当作临时hash表。size是hash table的大小，used是hash key value pair数量(hlen命令的返回值)。hash table新的size的计算公式 n = 2**k >= used*2，基本就是2倍扩张 loadFactor = used/size 没有bgsave的时候lf >=1就触发 bgsave的时候要为5 < 0.1的时候就触发收缩

渐进式rehash

每次crud的时候，就会把旧的hash表的trehashIndex上的所有dictEntry迁移到ht[1]。这个rehashIndex设计得很精妙，保证每次都会迁移一点。在迁移过程中会从0-size-1变化。 ht[2]和rehashIndex共同完成来rehash