LinuxKernelのHashFunction(ハッシュ関数)の仕組みについて

昨日、こちらの勉強会に参加してきました。
アルゴリズムとデータ構造についてOSSから勉強する会 - connpass

こちらの記事では、Hash関数の仕組みについて、忘れないうちにまとめておきます。
会自身については↓を参照のこと。
アルゴリズムとデータ構造についてOSSから勉強する会に参加してみました - 手が震えたらBARに行こう

Hash関数って何？

さて、Hash関数とは何かというと、

hashFunctions("abcdef") = 9462463124717362

といった入力の値に対して一意の出力の対応をさせる関数のことです。

例えば？

一体、この関数をどんな風に使っているのかというと
例えば、動物園の動物名とその数を管理したい時には、普通にやると配列を使った以下の様なデータ構造になってしまいます。

zoo ┬(0) "かば, 5"
　　├(1) "きりん, 2"
　　├(2) "ぞう, 2"
　　├(3) "らいおん, 4"
　　├(4) "しまうま, 8"
　　└(5) "さい, 3"
　　　　　図1

問題点

だけれども、こんなデータ構造の場合、例えば、以下の様な問題が出た場合　

さいは何頭いますか？

zooの配列を全部調べあげてチェックしなければなりません。
そうすると計算量がO(n)になってしまいます。

これはちょっとやめたい。（スピードキングはWTFとか言うはず。）

解決策として、出てきたのが、Hash関数

そして、
なんとかならんかなー
なんとかならんかなー
といった末に出てきたのがHashというデータ構造
これは、どんなデータ構造かというと

ポインタ1（10000000）に、"かば, 5"
ポインタ2（20000000）に、"きりん, 2"
ポインタ3（30000000）に、"ぞう, 2"
ポインタ4（40000000）に、"らいおん, 4"
ポインタ5（50000000）に、"しまうま, 8"
ポインタ6（50000000）に、"さい, 3"

と書きこみをしてしまいます。
※ポインタはメモリ上のデータの住所だと思ってもらえれば大丈夫です。

そして、読みだす時には以下のようにします。

hashFunctions("かば")とすると、返り値が10000000と直接メモリの場所を教えてくれる為、
直接その番地を読みに行けばいいってわけです。

このおかげで、計算量は常に１（※1）になるので、zooが巨大なデータになっても大丈夫ってわけです。
（※1 hashFunctionsの計算量が常に1の場合においては）
このデータ構造を作る為の関数がHash関数だったりします。

で、具体的に、Hash関数の中はどうなってるん？

さて、前置きが長くなりましたが、こういう事をするためのHash関数は具体的にどんなふうに実装されているのか？という点をこれから説明します。
具体的な実装コードは以下のコードになります。（32ビット版）

static inline u32 hash_32(u32 val, unsigned int bits)
{
        /* On some cpus multiply is faster, on others gcc will do shifts */
        u32 hash = val * GOLDEN_RATIO_PRIME_32; --(*1)

        /* High bits are more random, so use them. */ --(*2)
        return hash >> (32 - bits);
}

引数の説明

これは何をしているのかというと、
まず引数valは上の図1における"かば"とか"きりん"ですね。
（実際には、文字列が入ったとしても、それを数値に変換して処理が進められるわけですが。）
で、bitsというのは、ハッシュテーブルのサイズのビットサイズの事を指します。
これも、図1の例で言うと、6を2進数で表現すると3桁必要なので、bitsは3となります。
なので、例えば、このhash関数を呼ぶとしたら

hash_32("かば", 3)

といったように呼ぶことになるのかと思います。（※2）
（※2 実際には、"かば"ではなく、なんらかの数値に変換されるかと思います。）

具体的なアルゴリズム

ここからは具体的な数値で計算を行ってみます。
それぞれのデータが以下のようになっている場合

(0) = 10(10進数) = 00000000000000000000000000001010(2進数)
(1) = 20(10進数) = 00000000000000000000000000010100(2進数)
(2) = 30(10進数) = 00000000000000000000000000011110(2進数)
(3) = 40(10進数) = 00000000000000000000000000101000(2進数)
(4) = 50(10進数) = 00000000000000000000000000110010(2進数)
(5) = 60(10進数) = 00000000000000000000000000111100(2進数)

図で書いてみると

(0) (1) (2) (3) (4) (5)
┝─┼─┼─┼─┼─┤

↓(GOLDEN_RATIO_PRIME_32をかけてあげることで、メモリのアドレスの間隔を広げる）

(0)      (1)      (2)      (3)      (4)      (5)
┝────────┼────────┼────────┼────────┼────────┤

で、GOLDEN_RATIO_PRIME_32は下記のように記載がある為、この値を使ってみます。

/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL

実際に計算してみるとGOLDEN_RATIO_PRIME_32の数値は、2654404609でした。
なので、これをかけあわせると、以下のようになります。（これが、コード中の(*1)の所）

(0) = 26544046090(10進数) = 11000101110001001100000000000001010(2進数)
(1) = 53088092180(10進数) = 110001011100010011000000000000010100(2進数)
(2) = 79632138270(10進数) = 1001010001010011100100000000000011110(2進数)
(3) = 106176184360(10進数) = 1100010111000100110000000000000101000(2進数)
(4) = 132720230450(10進数) = 1111011100110101111100000000000110010(2進数)
(5) = 159264276540 (10進数) = 10010100010100111001000000000000111100(2進数)

で、次に、それを(*2)の箇所で、32-3 = 29 個　ビットを右シフトします。

//<-------------32ビット幅(a)------------><-------------桁落ち部分(b)------------->
0:| 00000000000000000000000000000110 | 00101110001001100000000000001010
1:| 00000000000000000000000000000110 | 001011100010011000000000000010100
2:| 00000000000000000000000000000100 | 1010001010011100100000000000011110
3:| 00000000000000000000000000000110 | 0010111000100110000000000000101000
4:| 00000000000000000000000000000111 | 1011100110101111100000000000110010
5:| 00000000000000000000000000000100 | 10100010100111001000000000000111100

(赤字はシフトした部分／青字は桁落ちした部分)

(a)この部分がハッシュ関数の返り値となる
(b)この部分は桁落ちして、消えてしまいます

じゃあ、それで改めて、0～6はどんな風になってるかというと
0:| 00000000000000000000000000000110 = 6
1:| 00000000000000000000000000000110 = 6
2:| 00000000000000000000000000000100 = 4
3:| 00000000000000000000000000000110 = 6
4:| 00000000000000000000000000000111 = 7
5:| 00000000000000000000000000000100 = 4
ですね。

0と1と3の値とか、2と5の値とかが被ってますね。・・・
でも、いいんです。
Hash関数は、かぶってていい。

かぶっちゃまずいのは、HashTablesのデータ構造の場合。
ただ、こちらの場合は、HashTablesの方できちんと対策されているので、大丈夫かと思います。
これらについては、また今度、今日はこんなところまでです。

あと、今回は6個のデータで行ってみましたが、64個データがあるうちの6個を取り出してきて、上記の処理と同じ処理を行った場合はどんな値になるのか？というのを見てみると、
なるほど！！って感じになるかもしれません。
（つまり、bitsが7になる場合ですね。）

勉強したばかりで、間違っている所などあれば、直していきたいと思いますので、指摘いただければと思います。
よろしくお願い致します。

64ビット版では・・・？

おまけ。ちなみに、64ビット版では、以下のようになっています。

static __always_inline u64 hash_64(u64 val, unsigned int bits)
{
        u64 hash = val;

        /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
        u64 n = hash;
        n <<= 18;
        hash -= n;
        n <<= 33;
        hash -= n;
        n <<= 3;
        hash += n;
        n <<= 3;
        hash -= n;
        n <<= 4;
        hash += n;
        n <<= 2;
        hash += n;

        /* High bits are more random, so use them. */
        return hash >> (64 - bits);
}

bit演算をビシバシずらしているのは、一体なんぞや？と申しますと、
これこそが、64ビット版のGOLDEN_RATIO_PRIMEをかけている所です。

もともと、定義されているのは、下記の状態となっているので、
これが表現できるように、ガシガシビット演算をしているわけですね。

/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL

さすが、LinuxKernel！

また、面白いのが、

/*  Sigh, gcc can't optimise this alone like it does for 32 bits. */

意訳(はぁ、gccでは32ビットの時だけしか、最適化されない)とかソースコードに書いちゃってる所が面白いですね。
僕は普段は、javascriptとかでで仕事のコードを書いている時は過度な最適化とかは、あまり気にしていないのですが
Kernel書いてる人たちは、こういう所でもため息出しちゃうんですね。
この部分は、勉強会でも、面白いよねーみたいな話になっていました。

参考URL
なんで、GOLDEN_RATIO_PRIMEかけるんですか？などなどの理由が乗ってました。
黄金比と素数とハッシュと | Syoyo Fujita's Blog

Linux Kernel 2.6のHashFunctionsのソースコード
linux-2.6/include/linux/hash.h at b3a3a9c441e2c8f6b6760de9331023a7906a4ac6 · mirrors/linux-2.6 · GitHub

当日使ったスライドはこちらになります。

Hash functions from tabun_muri

Hash functions

え？なんで、HashTablesに取り消し線が引かれているかって？
間に合わなかった。
今回はあえて、HashFunctionsだけにしたのじゃよ。

よろしくお願いいたします。