st.c のソースコードを読もうと思った経緯
CRuby Quest を読んでいて以下の説明を見かけました。
st_table はオープンアドレッシングという方法で衝突を回避します。 ... st_tabel ではオープンアドレッシングを採用することによって bins がシンプルな配列で実現することが出来ています。
ちょうど前回のブログ記事でコンピューターサイエンス基礎のデータ構造＆アルゴリズムあたりに取り組んでいました。
「ハッシュ」「オープンアドレッシング」あたりのキーワードが自分の中でホットだったのと、理論だけではなく実装にも触れるいい機会なのではないかということで、興味の赴くままに CRuby のソースコードを読むことにしました。
ちなみにこのブログ記事は 柏.rb #26 もくもく会の時間を使って文章を書いています。
ハッシュの基礎知識
概要の説明は wikipedia に委ねます。
ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。
Rubyで言うと組み込みライブラリの Hashクラス がそれで、ハッシュ式 が言語仕様に組み込まれていますね。
{ a:"A", b:"B", c:"C" }
:a , :b , :c がそれぞれ「キー」、"A" , "B" , "C" がそれぞれ「値」、キー :a に紐づいている値が "A" でそのペアが「エントリ」と言うことですね。
そんなハッシュも内部の基本的なデータ構造は配列です。キーを元に生成された「ハッシュ値」を添字にして値を管理します。イメージは以下の通り。
hash(a) = 2 hash(b) = 5 hash(c) = 8 +---+ 0 | | +---+ 1 | | +---+ 2 |"A"| +---+ 3 | | +---+ 4 | | +---+ 5 |"B"| +---+ 6 | | +---+ 7 | | +---+ 8 |"C"| +---+ 9 | | +---+
このキーからハッシュ値を生成する関数（上記だと hash(x)）が「ハッシュ関数」というものです。最もシンプルなハッシュ関数だと値の整数値を配列サイズで除算した余り（剰余、mod ）をハッシュ値とする「除算法」があったりします。
さて、一般的にキーが取りうる値範囲よりも内部の配列サイズの方が小さいことが一般的です。なので異なるキーから同じハッシュ値になることももちろんあります。それが「衝突」です。
hash(d) = 2 +---+ 0 | | +---+ 1 | | +---+ 2 |"A"| +---+ 3 | | +---+ 4 | | +---+ 5 |"B"| +---+ 6 | | +---+ 7 | | +---+ 8 |"C"| +---+ 9 | | +---+ "D"はどこに格納する？？？
この衝突を解決するための方法がいくつかあって、その一つが「オープンアドレッシング」ということになります。
いくつかの衝突解決手法
- 直接連鎖法
- 分離連鎖法
- オープンアドレス法
- 線形探針法 (Linear Probing)
- 2乗探針法 (Quadratic Probing)
- 二重ハッシュ法 (Double Hashing)
ここで言いたいことはCRubyはオープンアドレス法を使っているということ。
いくつかのハッシュ関数
キーワードだけ列挙。
- 除算法
- 乗算法
- 多項式ローリングハッシュ
- FNV Hash
- Murmur Hash
- xxHash
- SipHash
- 意図的にハッシュの衝突を起こすようなDoS攻撃に対する手法
CRubyはSipHashを採用しているらしい。
やっとソースコードを読む
hash.c という「いかにも」というソースファイルを見つけたのでそれから読み始めます。
https://github.com/ruby/ruby/blob/v4.0.0/hash.c
CRubyの予備知識がないので1mmも分からないのですが、53行目〜68行目のコメントを読みます。
/* Flags of RHash * * 1: RHASH_PASS_AS_KEYWORDS * The hash is flagged as Ruby 2 keywords hash. * 2: RHASH_PROC_DEFAULT * The hash has a default proc (rather than a default value). * 3: RHASH_ST_TABLE_FLAG * The hash uses a ST table (rather than an AR table). * 4-7: RHASH_AR_TABLE_SIZE_MASK * The size of the AR table. * 8-11: RHASH_AR_TABLE_BOUND_MASK * The bounds of the AR table. * 13-19: RHASH_LEV_MASK * The iterational level of the hash. Used to prevent modifications * to the hash during iteration. */
ST_TABLE と AR_TABLE という語彙が気になりますね。さっそくLLMに聞いてしまいましょう。
Q. crubyのhash実装みてたらst_tableとar_tableというものが出てきたけど、これらは何？
- ar_table (Array Representation): 小さいHash向けの軽量実装 - st_table (Symbol Tableのstが由来): 通常のハッシュテーブル実装 st_table は st.c に実装されている、CRuby全体で使われる汎用ハッシュテーブルです。
なるほど st.c !
https://github.com/ruby/ruby/blob/v4.0.0/st.c
ヘッダーのコメントに内部実装に関する説明が書かれてそうですね。
/* The original package implemented classic bucket-based hash tables
with entries doubly linked for an access by their insertion order.
To decrease pointer chasing and as a consequence to improve a data
locality the current implementation is based on storing entries in
an array and using hash tables with open addressing. The current
entries are more compact in comparison with the original ones and
this also improves the data locality.
The hash table has two arrays called *bins* and *entries*.
bins:
-------
| | entries array:
|-------| --------------------------------
| index | | | entry: | | |
|-------| | | | | |
| ... | | ... | hash | ... | ... |
|-------| | | key | | |
| empty | | | record | | |
|-------| --------------------------------
| ... | ^ ^
|-------| |_ entries start |_ entries bound
|deleted|
-------
挿入順を保持する（Hashのドキュメントにも「ハッシュに含まれる要素の順序が保持される」とありますしね）ためと、最適化のため、現在の内部データ構造としては「配列」と「オープンアドレッシングのハッシュ表」の2つがベースになっていると言及がありますね。アスキーアートによる説明も分かりやすくてイメージをつけやすいですね。
柏.rb のもくもくタイムの作業としてはここまでで時間切れになってしまいました。ブログ記事としては一旦ここで区切ります。
