Googleが提供している学習用教材Google Tech Dev Guideについて学習した内容のメモ。
今回取り組んだのは以下：
■タイトル
Implementing a key value store in a hash table
■リンク
http://codecapsule.com/2013/05/13/implementing-a-key-value-store-part-5-hash-table-implementations/
素人なので英語で読みながら理解するのはきついので和訳メモ。
リンク先の和訳
ハッシュテーブルの実装
この記事ではボトルネックとなるのはどこなのか理解するため、C++での実際のハッシュテーブルの実装について調査する。ハッシュはCPU-intensiveであり、それに最適化されている必要がある。しかし、ほとんどのハッシュテーブルの内部メカニズムは効率的なメモリとI/Oアクセスに関するものであり、その点がこの記事のメインポイントとなる。この記事では3つのC++でのハッシュテーブルの実装について、メモリ内部およびディスク上での動作について調査し、データがどのように構造化されアクセスされるか見ていく。この記事の内容は以下：
- Hash tables
- Quick introduction to hash tables
- Hash functions
- Implementations
2. unordered_map from TR1
2. dense_hash_map from SparseHash
2. HashDB from Kyoto Cabinet - Conclusion
- References
1.Hash tables
1.1 Quick introduction to hash tables
ハッシュテーブルにより連続的なデータに効率的にアクセスできる。各エントリはkeyとvalueのペアであり、keyがわかってさえいれば素早く読出しと割り当てができる。この機能の実現のためkeyはハッシュ関数を用いて元の値から整数にハッシュ変換される。次にこの整数は元の値にアクセスできるバケット配列のバケットを特定するインデックスとして使われる。たくさんのkeyが同じ値にハッシュ変換される可能性があり、その場合これらのkeyはバケット配列内で衝突(collision)する。この衝突を解決するために分離連鎖法、連結リスト、自己平衡木、または一次か二次探索の開番地法などの方法を適用することができる。
以降ハッシュテーブルが何かを理解している物として進める。もう少し理解が必要と考えるならWikipediaのハッシュテーブルのページ[1]、“Introduction to Algorithms” by Cormen et. al [2]のハッシュテーブルの章を参照するとよい。
1.2 Hash functions
ハッシュ関数の選択は非常に重要である。よいハッシュ関数の基本的な要件はそのハッシュ値が一様に分布する事である。こうすることで衝突するバケットへのエントリの数の平均値とともに衝突する可能性が抑えられる。
多くのハッシュ関数があり、データがどのようになるかわからない限りは平均してランダムなデータを一様に出力し、可能であればアバランシェ効果に対応できるものを選択することだ[3]。何人かの人が既にハッシュ関数の比較に取り組んでおり[4][5][6][7]、彼らの結論からMurmurHash3[8]とCityHashが[9]現時点でハッシュテーブルに最適であることは明らかだ。
2. Implementations
ハッシュ関数の比較と同様に、すでにC++メモリ内ハッシュテーブルライブラリの性能を比較しているブログ記事がいくつかある。遭遇した中で最も注目したのは“Hash Table Benchmarks” by Nick Welch [10] と “Hash Table Performance Tests” by Jeff Preshing [11]だが、他にもいくつか注目すべき記事があった[12][13][14]。