Rubyのハッシュテーブルの仕組みを徹底的に理解する
ハッシュとは
一般的に理解すると抽象的で分かり難くなってしまうが、ハッシュとは、あるデータから、一定の計算をして求めた、目的に沿った数値、と思っている。それでは、どのような目的に利用されるのか？自分の知識で考えてみた。
- 暗号化
- webアプリケーション等で、パスワードをDBに保存する時、生のパスワードをハッシュに変換して保存する。
- Digest::SHA1.hexdigest等で求めたハッシュから、元のデータを復元するのが非常に困難という特性を利用する。
- 保存しているパスワードハッシュが、たとえ漏洩したとしても、不正利用を防止できる。
- パスワードを照合するときも、ハッシュに変換して、保存しているパスワードハッシュと一致するかどうかで判断する。
- 同等の確認
- 長い文字列データを比較する時、全ての文字が等しいかチェックするのは非常に時間がかかる。
- しかし、長い文字列データをハッシュに変換しておき、ハッシュ同士を数値として比較すれば効率が良い。
- 改竄のチェックとか、チェックデジットとして利用してデータ通信時の文字化け検出などの利用が考えられる。
- ハッシュテーブルによる高速検索
- ハッシュテーブルとは、キーに対応する値を、瞬時に取り出すことができるテーブル。
- キーと値をペアにしたテーブルを検索する時、if文を使って先頭から順に照合していくと、以下の問題が発生する。
- キーの位置が最初か、最後かによって検索時間が変わってくる。
- キーが増える程に、平均の検索時間も増加する。
- この問題を解決するには、if文によるキーの照合を止める必要がある。
- キーをインデックス（先頭から何番目のデータかを表現する数値）に変換すれば、対応する値の格納位置を特定できる。
- キーが何万件あろうと、インデックスを見れば、対応するデータを瞬時に取り出せるのだ。
今回、理解しようと思っているのは、このハッシュテーブルの仕組み。Rubyでは{:apple => 120, :orange => 100}のように表現すれば、Hashオブジェクトが生成され、簡単に利用できる。便利なのでよく使うが、その裏で、どのような仕組みで実現されているか、気にしたことが無かった。当初、if文で地道に検索しているんだろうな、位にしか考えていなかった。とんでもない！もっと素晴らしく効率的な仕組みなのに。
Rubyでは、Hashオブジェクトに限らず、予約語の検索でも完全ハッシュ関数を利用して効率的に処理されているらしい。ハッシュテーブルを理解すれば、より効率的な処理方法を発想できるかもしれない。物事を効率的に処理する重要な技術なのだ。
Rubyのソースコードと解説
ソースコードと解説は以下のリンクから取得した。解説されているのは、ruby 1.7.3 2002-09-12版だが、ハッシュテーブルの仕組みに大きな変化は無さそうなので、1.8.7でも大変参考になる。
ハッシュテーブル
前回の日記：どのようにして一番右の1のビット位置を求めているのか？で理解した、M系列を活用する方法も、ハッシュテーブルを利用していると言える。
- 1、2、4、8、16、...、9223372036854775808（2の63乗）という64ビットの2のn乗数値を、0から63の数値（ハッシュ）に変換している。
- 変換する時に重複は無く、64ビットの2のn乗数値は、必ず0から63のたった一つの値と対応している。
- このように重複の無いハッシュを得られることを完全ハッシュと言う。
- しかもこの場合、変換される数値も0から63で、変換前の要素数とぴったり一致していて無駄が無い。
- このような完全無駄無しハッシュが、単純な演算だけで実現できてしまうシンプルさが凄いところ。
一方、M系列を利用しないで、Rubyのハッシュで実装しても、やはりハッシュテーブルが利用される訳だ。目に見えるRubyコードは、ものすごくシンプル。しかし、内部的なC言語の処理は遥かに複雑だ。ハッシュに変換する方法も、ハッシュテーブルの構造も。それは、あらゆるキーをハッシュに変換して、ハッシュは重複する可能性もあり、それでも的確に検索できるようにしているためだ。
- Rubyのハッシュテーブルは、単純な配列ではない。st_tableという構造体である。
- st_tableは、さらにst_table_entryという構造体へのポインタを複数持っている。
- st_table_entryは、以下の要素を持っている。
- キーを変換したハッシュ、
- キー、
- 値、
- 次のst_table_entryへのポインタ
- キーを変換したハッシュは重複する可能性があるので...
- ハッシュテーブルでヒットしたst_table_entryのキーを見て、重複した別のキーでないか確認する。
- もし、重複している別のキーであれば、次のst_table_entryに移動して、一致するキーが見つかるまで繰り返す。
- キーが一致していたら、値を読み出して返す。
つまり、キーが一致するまで、ポインタが指し示すst_table_entryへの移動を繰り返すことになる。キー値の検索はまずハッシュテーブルで行い、ハッシュが重複している場合はさらにif文で比較照合する、というハイブリッドなハッシュテーブルになっている。
図5: st_tableのデータ構造
-
-
- 上記の仕組みは、チェイン法という、アルゴリズムとして確立された手法であった。
- 参考ページ:アルゴリズムとデータ構造編 第１４章 ハッシュ探索�（チェイン法）
- 大変参考になりました。感謝です！その他のアルゴリズム解説も素晴らしいです！
-
st_tableに関連する構造体
- 図5の構造体は、以下のように定義されている。
/* ---------- ruby_1_8_7/st.h ---------- */ #if SIZEOF_LONG == SIZEOF_VOIDP typedef unsigned long st_data_t; #elif SIZEOF_LONG_LONG == SIZEOF_VOIDP typedef unsigned LONG_LONG st_data_t; #else # error ---->> st.c requires sizeof(void*) == sizeof(long) to be compiled. <<---- #endif struct st_hash_type { int (*compare)(); int (*hash)(); }; struct st_table { struct st_hash_type *type; int num_bins; int num_entries; struct st_table_entry **bins; };
/* ---------- ruby_1_8_7/st.c ---------- */ struct st_table_entry { unsigned int hash; st_data_t key; st_data_t record; st_table_entry *next; };
ポインタのポインタ
- st_tableのstruct st_table_entry **binsは、ポインタマークが二つ付いている。
- つまり、ポインタのポインタ、と言うことになる。何だか頭が混乱するが...
- binsは配列を指していて、もしその配列に値が保存されていれば、値の型 *bins となるはずなのだが、
- そこにはさらに、st_table_entryへのポインタがいくつも収められている。
- だから、「st_table_entryへのポインタ型の、ポインタだよ。」と理解すれば、少しは分かり易いだろうか？
(st_table_entry*) (*bins)
- ちなみに、binsは st_init_table_with_size() で取得されている。（以下の関数ポインタで抜粋したコード参照）
tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
関数ポインタ
- ところで、st_tableの中に、st_hash_typeという（自分にとって）見慣れない構造体があることに気付く。
- これは、関数を指し示すポインタの構造体である。
- 関数ポインタであるcompareやhashに、特定の関数を指定すれば、その関数をポインタ識別子で呼び出すことができる。
例：
- st_init_numtableを呼び出して生成されたst_tableでは...
-
-
- xcallocとは？
-
/* ---------- ruby_1_8_7/st.c ---------- */ #ifdef RUBY #define malloc xmalloc #define calloc xcalloc #endif #define alloc(type) (type*)malloc((unsigned)sizeof(type)) #define Calloc(n,s) (char*)calloc((n),(s)) st_table* st_init_numtable(void) { return st_init_table(&type_numhash); } st_init_table(type) struct st_hash_type *type; { return st_init_table_with_size(type, 0); } st_table* st_init_table_with_size(type, size) struct st_hash_type *type; int size; { st_table *tbl; ...（中略）... size = new_size(size); /* round up to prime number */ tbl = alloc(st_table); tbl->type = type; /* tbl->type->compare = numcmp; tbl->type->hash = numhash; */ tbl->num_entries = 0; tbl->num_bins = size; tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); return tbl; } static struct st_hash_type type_numhash = { numcmp, numhash, }; static int numcmp(x, y) long x, y; { return x != y; } static int numhash(n) long n; { return n; }
- st_tableのメンバ名を指定して、numcmp(x,y)あるいはnumhash(n)を呼び出すことができる。
(*table->type->compare)(x,y); /* numcmp(x, y)と同等 */ (*table->type->hash)(n); /* numhash(n)と同等 */
- なぜ、わざわざ上記のような遠回しな関数呼び出しをするのか？
- それは、st_hash_typeの指定を変更するだけで、ハッシュテーブルの種類に応じた比較（compare）やハッシュ変換（hash）を呼び出すことができるから。
- ハッシュテーブルは、Rubyのいろいろな部分で活躍している。
- しかし、利用する場所によって、ハッシュテーブルの種類が少しだけ異なる。
つまり、オブジェクト指向でないC言語で、オブジェクト指向的にハッシュテーブルを継承したような効果を狙っているのだ。コードの重複を最小限にするために。
Hashオブジェクトの実装
# ---------- ruby_1_8_7/hash.c ---------- static int rb_any_cmp(a, b) VALUE a, b; { VALUE args[2]; if (a == b) return 0; if (FIXNUM_P(a) && FIXNUM_P(b)) { return a != b; } if (TYPE(a) == T_STRING && RBASIC(a)->klass == rb_cString && TYPE(b) == T_STRING && RBASIC(b)->klass == rb_cString) { return rb_str_cmp(a, b); } if (a == Qundef || b == Qundef) return -1; if (SYMBOL_P(a) && SYMBOL_P(b)) { return a != b; } args[0] = a; args[1] = b; return !rb_with_disable_interrupt(eql, (VALUE)args); } static int rb_any_hash(a) VALUE a; { VALUE hval; int hnum; switch (TYPE(a)) { case T_FIXNUM: case T_SYMBOL: hnum = (int)a; break; case T_STRING: hnum = rb_str_hash(a); break; default: hval = rb_funcall(a, id_hash, 0); if (!FIXNUM_P(hval)) { hval = rb_funcall(hval, '%', 1, INT2FIX(536870923)); } hnum = (int)FIX2LONG(hval); } hnum <<= 1; return RSHIFT(hnum, 1); } static struct st_hash_type objhash = { rb_any_cmp, rb_any_hash, }; static VALUE hash_alloc0(klass) VALUE klass; { NEWOBJ(hash, struct RHash); OBJSETUP(hash, klass, T_HASH); hash->ifnone = Qnil; return (VALUE)hash; } static VALUE hash_alloc(klass) VALUE klass; { VALUE hash = hash_alloc0(klass); /* Hashオブジェクトが持つハッシュテーブルに、objhashタイプで初期化したハッシュテーブルを設定する */ RHASH(hash)->tbl = st_init_table(&objhash); return hash; } VALUE rb_hash_new() { return hash_alloc(rb_cHash);/* rb_cHash = rb_define_class("Hash", rb_cObject); */ }
/* ---------- ruby_1_8_7/string.c ---------- */ int rb_str_hash(str) VALUE str; { register long len = RSTRING(str)->len; register char *p = RSTRING(str)->ptr; register int key = 0; #if defined(HASH_ELFHASH) register unsigned int g; while (len--) { key = (key << 4) + *p++; if (g = key & 0xF0000000) key ^= g >> 24; key &= ~g; } #elif defined(HASH_PERL) while (len--) { key += *p++; key += (key << 10); key ^= (key >> 6); } key += (key << 3); key ^= (key >> 11); key += (key << 15); #else while (len--) { key = key*65599 + *p; p++; } key = key + (key>>5); #endif return key; }
/* ---------- ruby_1_8_7/ruby.h ---------- */ struct RHash { struct RBasic basic; struct st_table *tbl; int iter_lev; VALUE ifnone; };
- Hashオブジェクトのキーには、数値・シンボル・文字列が利用できる。
- st_tableのtypeがobjhashになると、以下のcompare・hashが呼び出されることになる。
(*table->type->compare)(x,y); /* rb_any_cmp(x, y)と同等 */ (*table->type->hash)(n); /* rb_any_hash(n)と同等 */
- rb_any_cmp・rb_any_hashの中で、キーの種類に応じて処理されていた。
ハッシュの検索方法
- まず、マクロ定義されたdo_hash(key,table)を実行することで、ハッシュ変換が始まる。......（4）
- (*(table)->type->hash)( (key) )は、ポインタによる関数呼び出し。......（1）
- ハッシュテーブルのタイプに応じたハッシュ変換関数が呼び出される。
- FIND_ENTRY()はキーに対応するエントリを検索する......（5）
- 求めたハッシュhash_valを、テーブルサイズ(table)->num_binsで割った余りが、求めるエントリの相対位置bin_posを示す。......（2）
- ハッシュテーブルの先頭からbin_posをインデックス指定して、求めるエントリのポインタptrを取得する。......（3）
- 取得したエントリのポインタptrが、果たして、検索キーと一致しているかチェックする。......（C）
- PTR_NOT_EQUAL()とEQUAL()マクロによって、キーが一致していないとtrueを返す。......（B）
- (*table->type->compare)( (x),(y) )でハッシュテーブルのタイプに応じた比較をする。......（A）
- COLLISION;はデバッグ用のマクロなので、無視してOKらしい。
- キーが一致していなければ、次のポインタに移動する。キーが一致するまで繰り返す。......（D）
- 最後の ptr = ptr->next; が不要な気がするが、......（E）
- if と whileのPTR_NOT_EQUALの第2引数が、ptrとptr->nextで違っていることに注意。
- if を whileに置き換えれば、続く4行は不要になりそうだけど、COLLISIONを有効にしたいから、このようにしている？
- 最後に、ptr->recordとすれば、キーに対応した値が取得できる。
/* ---------- ruby_1_8_7/st.c ---------- */ #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0) /* A */ #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key)) /* 1 */ #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ /* B */ ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ bin_pos = hash_val%(table)->num_bins;\ /* 2 */ ptr = (table)->bins[bin_pos];\ /* 3 */ if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\ /* C */ COLLISION;\ while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ /* D */ ptr = ptr->next;\ }\ ptr = ptr->next;\ /* E */ }\ } while (0) int st_lookup(table, key, value) st_table *table; register st_data_t key; st_data_t *value; { unsigned int hash_val, bin_pos; register st_table_entry *ptr; hash_val = do_hash(key, table); /* 4 */ FIND_ENTRY(table, ptr, hash_val, bin_pos); /* 5 */ if (ptr == 0) { return 0; } else { if (value != 0) *value = ptr->record; return 1; } }
ハッシュテーブルのサイズ
- ハッシュテーブルに必要なサイズは、st_init_table_with_size()の中で、new_size()を呼び出して計算している。
/* ---------- ruby_1_8_7/st.c ---------- */ /* * MINSIZE is the minimum size of a dictionary. */ #define MINSIZE 8 /* Table of prime numbers 2^n+a, 2<=n<=30. */ static long primes[] = { 8 + 3, 16 + 3, 32 + 5, 64 + 3, 128 + 3, 256 + 27, 512 + 9, 1024 + 9, 2048 + 5, 4096 + 3, 8192 + 27, 16384 + 43, 32768 + 3, 65536 + 45, 131072 + 29, 262144 + 3, 524288 + 21, 1048576 + 7, 2097152 + 17, 4194304 + 15, 8388608 + 9, 16777216 + 43, 33554432 + 35, 67108864 + 15, 134217728 + 29, 268435456 + 3, 536870912 + 11, 1073741824 + 85, 0 }; static int new_size(size) int size; { int i; #if 0 /* 決して実行されないブロック */ for (i=3; i<31; i++) { if ((1<<i) > size) return 1<<i; } return -1; #else int newsize; for (i = 0, newsize = MINSIZE; i < sizeof(primes)/sizeof(primes[0]); i++, newsize <<= 1) { if (newsize > size) return primes[i]; } /* Ran out of polynomials */ return -1; /* should raise exception */ #endif }
テーブルサイズはなぜ素数なのか？
- キーから値を取得するには、ハッシュ%テーブルサイズで余りを取得する。その余りが、求めるキーのインデックスになっている。
- ハッシュテーブルを効率良く利用するには、インデックスの重複を無くし、キーと値が1対1となる関係を目指す必要がある。
- それを実現するために、素数で割ることで、その余りが一様にばらけた値になるようだ。
- 以下のページで、面白い実験結果を見ることができる。（大変参考になりました。感謝です！）
- データ構造とアルゴリズム >> 表検索アルゴリズム >> ハッシュ検索 >> ハッシュ関数の選び方
ハッシュテーブルにエントリを追加
- st_add_direct()は、エントリを無条件に追加する。
- st_insert()は、ハッシュテーブルにキーが存在するか調べて...
- キーが存在しない時だけ追加する。
- キーが存在したら上書きする。
- どちらも、追加する時は、マクロ定義 ADD_DIRECT()で処理している。
- ハッシュテーブルが混雑していたら、......if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY)
- ハッシュテーブルのサイズを再設定して、作り直す。......rehash(table)
- st_table_entryに、必要事項を書き込んで、st_tableに追加する。st_tableのエントリ数を+1する。
#define ST_DEFAULT_MAX_DENSITY 5 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ do {\ st_table_entry *entry;\ if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\ rehash(table);\ bin_pos = hash_val % table->num_bins;\ }\ \ entry = alloc(st_table_entry);\ /* 新規エントリを生成 */ \ entry->hash = hash_val;\ entry->key = key;\ entry->record = value;\ entry->next = table->bins[bin_pos];\ /* 新規エントリのnext ← 今まで先頭だったエントリの位置 */ table->bins[bin_pos] = entry;\ /* ハッシュテーブルが指す先頭のエントリ ← 新規エントリの位置 */ table->num_entries++;\ } while (0) int st_insert(table, key, value) register st_table *table; register st_data_t key; st_data_t value; { unsigned int hash_val, bin_pos; register st_table_entry *ptr; hash_val = do_hash(key, table); FIND_ENTRY(table, ptr, hash_val, bin_pos); if (ptr == 0) { ADD_DIRECT(table, key, value, hash_val, bin_pos); return 0; } else { ptr->record = value; return 1; } } void st_add_direct(table, key, value) st_table *table; st_data_t key; st_data_t value; { unsigned int hash_val, bin_pos; hash_val = do_hash(key, table); bin_pos = hash_val % table->num_bins; ADD_DIRECT(table, key, value, hash_val, bin_pos); } static void rehash(table) register st_table *table; { register st_table_entry *ptr, *next, **new_bins; int i, old_num_bins = table->num_bins, new_num_bins; unsigned int hash_val; new_num_bins = new_size(old_num_bins+1); new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*)); for(i = 0; i < old_num_bins; i++) { ptr = table->bins[i]; while (ptr != 0) { next = ptr->next; hash_val = ptr->hash % new_num_bins; ptr->next = new_bins[hash_val]; new_bins[hash_val] = ptr; ptr = next; } } free(table->bins); table->num_bins = new_num_bins; table->bins = new_bins; }
予備知識
C言語に疎いので、以下のようなことも、ちゃんと理解しておく必要があった。
#defineのマクロ機能
- 自分が使ったことがある#defineは、以下のような使い方。
#define PI 3.14 s = PI * r * r
- すると、Cプリプロセッサは、以下のように置き換えて解釈してくれる。
s = 3.14 * r * r
- つまり、#defineは、第1引数を、第2引数で置き換えるのだ。
- 置き換えの機能をうまく利用すれば、以下のように関数定義のような使い方も可能。
#define PI 3.14 #define sq(r) ((r)*(r)) s = PI * sq(r)
- すると、以下のように解釈される。
s = 3.14 * ((r)*(r))
- なぜ、カッコがいっぱい必要なのかは、以下のページが大変参考になりました。（感謝です！）
- さらに、以下のようにすると、複数行に渡る関数定義のように利用できてしまうなんて！
#define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ bin_pos = hash_val%(table)->num_bins;\ ptr = (table)->bins[bin_pos];\ if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\ COLLISION;\ while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ ptr = ptr->next;\ }\ ptr = ptr->next;\ }\ } while (0) FIND_ENTRY(table, ptr, hash_val, bin_pos);
- すると、以下のように解釈されるのか...。
do { bin_pos = hash_val%(table)->num_bins; ptr = (table)->bins[bin_pos]; if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) { COLLISION; while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) { ptr = ptr->next; } ptr = ptr->next; } } while (0);
- 複数の文・式から成るマクロ定義では、全体をdo{〜}while(0)で囲む。
- この方法は、マクロを安全に展開するための常套手段らしい。
- C言語のプリプロセスのメモ(Hishidama's C pre-process Memo)（大変参考になりました。感謝です！）
- また、while(0)の後に「;」を付けないのもポイントらしい。
- マクロを利用する時は FIND_ENTRY(); とするので、while(0); だと「;」が二重になってしまう...。
構造体メンバへのアクセス
- pがpoint型の変数であるなら、そのメンバには「.」で区切ってアクセスできる。
struct point{ float x; float y; }; struct point p; p.x = 100.0; p.y = 200.0;
- もし、pがポインタであるなら、「->」で区切ってアクセスする必要がある。
struct point *p; p->x = 100.0; /* (*p).xと同等 */ p->y = 200.0; /* (*p).yと同等 */
- 参考ページ（本文中以外にも、以下のページが参考になりました。感謝です！）
追記
- ハッシュオブジェクトの文字列キーから値へのインデックスを求める処理
/* ---------- ruby_1_8_7/string.c ---------- */ int rb_str_hash(str) VALUE str; { register long len = RSTRING(str)->len; register char *p = RSTRING(str)->ptr; register int key = 0; ...（中略）... #else while (len--) { key = key*65599 + *p; p++; } key = key + (key>>5); #endif return key; }
- その後、上記関数で返された値を、素数であるハッシュテーブルサイズで割った余りが、値へのインデックス
/* ---------- ruby_1_8_7/st.c ---------- */ #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ bin_pos = hash_val%(table)->num_bins; ptr = (table)->bins[bin_pos];\ ...（中略）...
- 一方、st_hash_typeの場合の、値へのインデックスを求める処理
static int
numhash(n)
long n;
{
return n;
}
- その後の処理は同様で、FIND_ENTRY(table, ptr, hash_val, bin_pos)が実行される。
- ハッシュのタイプによっては、元のキーをそのままハッシュテーブルサイズで割って、余りを利用することがあるのだ。
素数で割るのは、汎用的に利用する為、なのかな？
