hash - ハッシュ テーブルに対する反復の疑似ランダム性

Question

試行に関するウィキペディアの記事には、次のように書かれています。

Tries support ordered iteration, whereas iteration over a hash table will result in a pseudorandom order given by the hash function.

ハッシュテーブルの文脈における疑似乱数とはどういう意味ですか?

Answer 1

実際のランダム性はありませんが、反復が各オブジェクトをどの順序で訪問するかを予測するのは難しいことを意味します。ハッシュ テーブルは通常、これらの反復間で変更が行われていなければ、各オブジェクトを同じ順序で反復しますが、別のオブジェクトを追加するような単純なことでも、コンテナー全体の反復の順序が変わる可能性があります。

これは、ハッシュ テーブルがオブジェクトを格納する場所が、ハッシュ関数とハッシュ テーブル内のバケットの数に基づいているためです。実装によっては、ハッシュ テーブルにコンテンツを追加し、含まれているオブジェクトを移動して新しいバケットのセットに一致させ、反復の順序を変更すると、ハッシュ テーブルのバケット数が増える場合があります。