Redis内部数据结构——词典dictType以及哈希算法的选择
Redis内部数据结构——词典dictType以及哈希算法的选择
词典dict概览提到了使用Hash Table作为Redis 词典的内部实现，需要考虑三个要点。这章讨论第一个问题：Redis哈希算法的选择。
哈希是把任意长度的输入通过哈希算法转换为固定长度的值。根据不同的使用场景，人们设计出了多种哈希算法，我们常见的有CRC，MD5，HMAC，SHA-256等等，关于多种哈希算法，可以在查看wiki。
Redis作为一个高性能的key-value内存服务器，哈希算法需要从计算效率以及减少碰撞的角度选择。
dictType
dict的数据结构：
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;dictType *type;一个指向dictType结构的指针（type）。它通过自定义的方式使得dict的key和value能够存储任何类型的数据。其中包括自定义的哈希函数。
dict.h/dictType的数据结构：
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;dictType结构包含几个函数指针，允许dict的调用者自定义涉及key和value的操作。
- hashFunction：定义对key进行哈希值计算的哈希算法。
- keyDup和valDup：定义key和value的拷贝函数，用于对key和value进行深拷贝，而不仅仅是传递对象指针。
- keyCompare：定义key的比较操作，在根据key进行查找时会用到。
- keyDestructor和valDestructor：定义对key和value的析构函数。
私有数据指针（privdata）就是在dictType的某些操作被调用时会传回给调用者。
dict.c Redis哈希算法siphash
从dictType数据结构，我们知道Redis的哈希算法是由dictType的函数指针*hashFunction定义。在dict.c中有dictType的实现：
dictType BenchmarkDictType = {
hashCallback,
NULL,
NULL,
compareCallback,
freeCallback,
NULL,
NULL
};
uint64_t hashCallback(const void *key) {
return dictGenHashFunction((unsigned char*)key, strlen((char*)key));
}
uint64_t dictGenHashFunction(const void *key, int len) {
return siphash(key,len,dict_hash_function_seed);
}在dict.c定义了BenchmarkDictType，最后我们跟到提供哈希算法的是siphash。
如果对Redis历史版本了解，在3.2, 3.0, 2.8, 2.6 使用的MurmurHash2 哈希算法，而4.0以后改为了siphash。以下是Redis作者antirez对选择siphash的一个解释：
Redis uses a reduced rounds version of siphash that is faster than the hashing fucntion we were using, so upgrading was actually a speedup (verified experimentally). AFAIK there are no known attacks on the reduced rounds we use, so for know the current approach sounds good.
大意是：Redis对siphash做了部分删减，经实验验证，改后的siphash要比旧版本的哈希算法（murmurhash2）要快，并且没有发现一些已知的攻击。
这里要提一下哈希洪水攻击（Hash-Flooding Attack），n个key通过hash计算出来的值都相同，那么就会退化成链表，这样查找1个数的时候复杂度就是O(n)。哈希碰撞攻击在知道hash算法的前提下恶意构造n个相同hash值的key，这样hash表的查找效率就被拖慢到了O(n^2)。
查了一些资料，siphash是计算快，计算的哈希值分布均匀良好且不可以预测。可以认为是碰撞极少的一种哈希算法。
