2016-06-19 16 views
2

私は記事"Rationale for Adding Hash Tables to the C++ Standard Template Library"を読んでいる、と私は、この一見単純な文で理解していない:ハッシュテーブルで役割ハッシュ・テーブル・エントリのスペースの消費量を計算

、余分なメモリの量を必要なのは、表の の構成と負荷係数(その組織の意向も )によって異なります。最も簡単なケースは、組織 と呼ばれるオープンアドレッシングで、すべてのエントリが単一の ランダムアクセステーブルに格納されています。 [...]この場合、エントリあたりのメモリ使用量はM /αです。

* Mは、キーと関連する値に必要なバイト数です.αは負荷係数です。

なぜM /αですか?なぜ単純にM +(各バケットの総メモリ量*バケット総数)ではないのですか?

答えて

1

オープンアドレッシングでは、要素が配信される固定サイズのスロットがあります。これは、エレメントのためのスペースと(オプションで)スロットがいっぱいで空であることを示すためにスローされた制御ビットを持つ単純な配列です。

たとえば、s個のスロットを持つテーブルがあり、n個の要素をテーブルに配布したいとします。つまり、α = n/sで、要素数をスロット数で割ったものです。テーブル全体のスペース使用量はsMである。なぜなら、s個のスロットがあり、各スロットはMバイトを使用するからである。したがって、要素ごとに使用されるメモリを計算する場合は、sM/n = M /(n/s)= M/αを計算する必要があります。直観的には、これは理にかなっています。テーブルに1つの要素がある場合、負荷係数は1/sであり、合計メモリ(Ms)を要素数(1)で割ったものがMsです。一方、テーブルが完全にロードされているn = s)の場合、α = 1であり、合計メモリ(Ms)を要素数で割ったものがMに等しくなります。

あなたの計算では、バケットあたりのメモリを計算し、バケット数で乗算します。要素あたりのサイズをM、スロット数をsとすると、合計スペース使用量はMになります(M項を追加する必要はありません。実際にはM "要素あたりのバイト"単位を持ち、Msには単位 "バイト"があるので、一緒に追加すべきではありません。

関連する問題