4

だから私は衝突のないハッシュ関数 (非常に単純なもの) を持っていますが、なぜこのような衝突のないハッシュ関数が使用されないのか疑問に思っています。スペースを取りすぎているのが原因かと思いますが、本当の答えを知りたいです。

関数は次のとおりです。

n+1 文字 ß n ß n-1 ... ß 1 ß 0で構成される単語 w がある場合、ハッシュ関数を定義します。

H(w) = 26 n * ß n + 26 n-1 * ß n-1 + ... + 26 * ß 1 + ß 0 .

ここで、たとえば、a = 1、b = 2、c = 3、...、z = 26 です。

この関数は、文字列と整数の間の 1 対 1 のマッピングを定義するため、衝突はありません。

もちろん問題は、単語の長さが長くなると、ハッシュ コードが非常に大きくなることです。

これに対する可能な解決策は次のとおりです: 長い単語を分割し、各ハッシュ コードをベクトルにし、2 番目の要素が単語の残りの部分を指すようにします (2 つ以上に分割された場合、単語の別の部分を指すことができます)。一度）。

私の質問は、なぜこれが実装されていないのですか? メモリの余分なコストは、衝突を回避する価値がありませんでしたか? この方法は別の理由で不十分であることがわかりましたか?このようにしようと考えるのは私が最初ですか？（最後のものについては冗談です。）

4

4 に答える 4

4

ハッシュのポイントは、結果を配列インデックスにすばやくマップすることです。ハッシュが任意に大きい場合、ハッシュの目的が無効になります。

于 2013-08-03T23:57:57.850 に答える
1

HashCode は、HashMap、HashTable、および同様の構造のヘルパー フィールドにすぎません。

非衝突である必要はありません。並べ替えプロセスとルックアップを高速化するためにのみ使用されます。

完璧でありながら複雑なアルゴリズムを持つ必要はありません。複雑すぎると、プロセスが遅くなるだけです。言うまでもなく、巨大な数はこの目的には実用的ではありません。

ウィキペディアのページで詳しく説明されています。

于 2013-08-03T23:57:28.997 に答える