コンテナのハッシュコードを効率よく計算する

Question

コンテナのハッシュコードを計算するために私が知っているアルゴリズムは、その中のすべての要素のハッシュを再帰的に組み合わせることで機能します。ハッシュがどのように組み合わされているかは、私の質問とは無関係です。しかしアルゴリズムが再帰するので、計算が非常に高価になる可能性があります。 O（n）、ここでnは到達可能な要素の総数です。

私の質問は、それを行うための効率的な方法がある場合ですか？たとえば、100k要素の配列を持っている場合、含まれている要素の100個のみのハッシュを組み合わせてハッシュを計算できます。それは計算を1000倍速くしますが、それでも良いハッシュ関数ではないでしょうか？

あなたが選んだ100要素は、上記の例では最初の100個または1000番目のものになり、他の決定論的な式を使用して選択されます。

だから、私の質問に答えることができます いずれか私の考えは私のアイデアがすでに検討されてきたところ またはが私に教えて働くことができない理由を教えてください。同様に私は提案しているように、 "sub O（n）sequence hashing"を実装したプログラミング言語を持っていますか？

Answer 1

一般的に、適切なハッシュ関数を設計するには、計算時間と品質をトレードオフする必要があります。これは、非常に大きなオブジェクトの場合に特に当てはまります。

大きなオブジェクトの固定サイズのサブセットのみをハッシュすることは有効な戦略です（たとえば、Luaは大きな文字列をハッシュするためにこの戦略を使用します）が、ハッシュされたオブジェクトにはほとんど違いがなく、その違いがハッシュされたサブセットにないことを示します。これは、サービス拒否攻撃（または同じ問題を誤って引き起こす入力）の可能性を開きます。したがって、制御されていない入力をハッシュしているのであれば、一般的には良い考えではありません。 （そして、あなたが暗号演習の一部としてハッシュを使用している場合、オブジェクトの一部を省略することは些細なことですので、それは本当に悪い考えです）。

ハッシュを部分的に使用していると仮定しますデータベース索引付け戦略（つまりハッシュ・テーブル）を使用する場合は、最後に、検索された値とテーブル内の一致する可能性のある値を比較する必要があります。これらの比較は必然的にO（n）です（ほとんどすべてのルックアップが失敗すると思わない限り）。それぞれの偽陽性は追加の比較を必要とするため、品質と計算時間のトレードオフが間違った経済になる可能性があります。

しかし、結局のところ、決定的な答えはありません。ハッシュを使用しているもの、データの分布（またはそうである可能性が高い）などを考慮した正確なユースケースに基づいて決定する必要があります。