REDISソースコードのいくつかの学ぶべき技術の詳細02

1.Redisにおけるハッシュ関数の実装:
Redisは整数keyと文字列keyに対して異なるハッシュ関数を採用している
整数keyの場合、redisはThomas Wangの32 bit Mix Functionを使用し、dict.c/dictIntHashFunction関数を実現した.

 1 /* Thomas Wang's 32 bit Mix Function */
 2 unsigned int dictIntHashFunction(unsigned int key)
 3 {
 4     key += ~(key << 15);
 5     key ^=  (key >> 10);
 6     key +=  (key << 3);
 7     key ^=  (key >> 6);
 8     key += ~(key << 11);
 9     key ^=  (key >> 16);
10     return key;
11 }

このコードのすばらしさはまだよく研究していないので、研究が終わったらここで補うことができますが、2つの最初のリンクを見つけました.
まずはThomas Wang大神本人のリンク:
http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
また、他の人が上のリンクやその他の資料に基づいて書いたまとめです.
http://blog.csdn.net/jasper_xulei/article/details/18364313
 
文字列形式のkeyの場合、redisはMurmurHash 2アルゴリズムとdjbアルゴリズムを使用します.
MurmurHash 2アルゴリズムはkeyに対して大文字と小文字に敏感であり,大端機械と小端機械では生成結果が一致しない.
redisのdict.c/dictGenHashFunctionは、MurmurHash 2アルゴリズムのC言語実装である.

 1 unsigned int dictGenHashFunction(const void *key, int len) {
 2     /* 'm' and 'r' are mixing constants generated offline.
 3      They're not really 'magic', they just happen to work well.  */
 4     uint32_t seed = dict_hash_function_seed;
 5     const uint32_t m = 0x5bd1e995;
 6     const int r = 24;
 7 
 8     /* Initialize the hash to a 'random' value */
 9     uint32_t h = seed ^ len;
10 
11     /* Mix 4 bytes at a time into the hash */
12     const unsigned char *data = (const unsigned char *)key;
13 
14     while(len >= 4) {
15         uint32_t k = *(uint32_t*)data;
16 
17         k *= m;
18         k ^= k >> r;
19         k *= m;
20 
21         h *= m;
22         h ^= k;
23 
24         data += 4;
25         len -= 4;
26     }
27 
28     /* Handle the last few bytes of the input array  */
29     switch(len) {
30     case 3: h ^= data[2] << 16;
31     case 2: h ^= data[1] << 8;
32     case 1: h ^= data[0]; h *= m;
33     };
34 
35     /* Do a few final mixes of the hash to ensure the last few
36      * bytes are well-incorporated. */
37     h ^= h >> 13;
38     h *= m;
39     h ^= h >> 15;
40 
41     return (unsigned int)h;
42 }

一方、redisはdjb関数を用いて、大文字と小文字を区別しないハッシュ関数dict.c/dictGenCaseHashFunctionを実現した.

1 unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
2     unsigned int hash = (unsigned int)dict_hash_function_seed;
3 
4     while (len--)
5         hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
6     return hash;
7 }

以上の3つのハッシュ関数(dictIntHashFunction,dictIntHashFunction,dictGenCaseHashFunction)は、それぞれredisの異なる場所で使用され、異なる場合におけるハッシュ要件を実現するために使用されており、次に詳細に説明する.
 
2.Redisにおける異なる場合におけるいくつかの異なるハッシュ関数の使用