hash - 完璧なハッシュ関数？

Question

ウィキペディアで鳩の巣原理を読んでいると、「ハッシュテーブルでは、可能なキーの数が配列内のインデックスの数を超えるため、衝突は避けられません。どんなに巧妙であっても、これらの衝突を回避できるハッシュアルゴリズムはありません」。しかし、gperfはこれを正確に行っていませんか？

啓発してください。

Answer 1

gperf事前定義された文字列のリストに基づいて、ハッシュ関数とハッシュテーブルを作成します。

したがって、gperf十分な可能性があるように、ハッシュを十分に長く作成するように見えます。
これは、考えられるすべてのキーを事前に知っている場合にのみ実行できることです。これは、明らかに「非定数」ハッシュテーブルに関連しているウィキペディアのエントリの説明には当てはまらない仮定です。

Answer 2

gperfのWebサイトから：「文字列の特定のリストに対して、ハッシュ関数とハッシュテーブルを生成します...」-つまり、関数を準備するために、衝突なしで機能するすべての文字列を事前に知っている必要があります。

一般的なプログラミング言語で使用している通常のハッシュ関数は、任意の文字列を次々に入力として処理できるため（リストは一度に指定されません）、衝突を引き起こす可能性があります。