performance - OCaml の Hashtbl に最適なサイズはありますか?

Question

20 個のキー/値を保存する必要があるとします。2 の累乗、たとえば 32 を使用する方が効率的でしょうか? 著者が 251 のサイズを使用した論文を読みました (不明な数のキー/値に対して)、これは単なる乱数ですか、それとも何らかの理由がありますか?

について話してnいるHashtbl.create n。

Answer 1

あなたが何を求めているのかは完全には明らかではありません。名前で聞いているのでHashtbl、標準のハッシュ テーブル モジュールについて話していると思います。このモジュールは、常に 2 の累乗のサイズでテーブルを割り当てます。したがって、心配する必要はありません。

ハッシュ テーブルには 2 つの基本的な「非常に適切な」サイズがあります。ハッシュ バケットを見つけやすくするため、2 のべき乗が適しています。ハッシュ手順の最後のステップは、テーブルのサイズを法としてハッシュ値を取得することです。テーブル サイズが 2 の累乗である場合、このモジュロ演算はマスキング演算で非常に迅速に実行できます。ハッシュ関数自体の計算が非常に高速でない限り、これが今日の世界で問題になるかどうかはわかりません。

2 番目に適切な値は素数です。素数はテーブル全体に値を分散させる傾向があるため、適切です。ある数の倍数が優勢なハッシュ値がある場合、ハッシュ テーブルのサイズが優勢な数に対して相対的に素数でない限り、ハッシュ テーブルに密集したクラスターが発生します。大きな素数は事実上すべてのものに対して相対的に素であるため、クラスタリングを防ぎます。251は素数なのでいいです。