概要
ここではDictionaryやSet内部で使われているハッシュテーブルの実装に関することを書いていきます
python内部でhashテーブルがどこで使われているか
https://github.com/python/cpython/blob/master/Objects/dictnotes.txt
ここを読むと概要がわかる
- キーワード引数
- クラスメソッド / インスタンスメソッド / クラス変数 / インスタンス変数の管理
- buildin functionの管理
- 重複した要素のない配列（？）の作成
など
hashテーブル
https://mail.python.org/pipermail/python-dev/2012-December/123028.html
上のURLを読むとわかる
資料を読んだ感想としては、ハッシュテーブルはハッシュ値が衝突しないようにサイズの大きい配列を用意するためにメモリをかなり使うのでメモリをどう削減するかがかなり焦点が当てられているように感じました。
ハッシュテーブルは主にindexesとentryという二つの要素に分けられています。
値の挿入と削除が行われる際、次のような挙動をします。
一つもキーとバリューが入っていない空のdictionaryがインスタンスが作成された場合、indexesは要素数が8の配列として作成されます。配列の中身も全て-1になります。entryも空の配列になります。
なので、indexesは次のようになります。
[-1, -1, -1, -1, -1, -1, -1, -1]
次にa["b"] = 1のようにキーの中に値が挿入された際の挙動を考えましょう。"b"のハッシュ値が2398580820136986479だと仮定すると、
hash("b") % indexes.len() = 2398580820136986479 % 8 = 7
entryの0番目の要素を[2398580820136986479, "b", 1]に書き換えます。entryの0番目に値が入っているので、indexesの7番目の要素を0に書き換えます。
なので、entryとindexはそれぞれ、
[-1, -1, -1, -1, -1, -1, -1, 0]
[[2398580820136986479, "b", 1]]
のような状態になっています。
次に、a["h"] = 100のようにまた別のキーに値が挿入されて、hash("h") = 5779689943249367370だったと仮定すると、indexesとentryがそれぞれ
[-1, -1, 1, -1, -1, -1, -1, 0]
[[2398580820136986479, "b", 1], [5779689943249367370, "h", 100]]
になるのがわかるでしょう。