6

SO に関する別の質問では、一部の言語で、文字列をハッシュしてテーブル内で高速に検索できるようにする機能が取り上げられました。この 2 つの例は、.NET の Dictionary<> と Python の {} ストレージ構造です。他の言語は確かにそのようなメカニズムをサポートしています。C++ にはそのマップがあり、LISP にも同等のマップがあり、他のほとんどの最新の言語と同様です。

文字列のハッシュ アルゴリズムは一定時間内に実行できるという質問への回答で、プログラミングで 25 年の経験を持つ 1 人の SO メンバーが、あらゆるものを一定時間内にハッシュできると主張することで争われました。私の個人的な主張は、特定のアプリケーションが文字列の長さに境界を設定しない限り、これは正しくないということです。これは、定数 K によって文字列の最大長が決まることを意味します。

私は演算にハッシュ関数を使用する Rabin-Karp アルゴリズムに精通していますが、このアルゴリズムは使用する特定のハッシュ関数を指示しません。著者が提案したのは O(m) で、m は長さです。ハッシュされた文字列。

いくつかのハッシュ アルゴリズムを表示するこのページ ( http://www.cse.yorku.ca/~oz/hash.html )などの他のページをいくつか見ますが、それぞれが文字列の全長にわたって繰り返されるようです。その値に到達します。

この件に関する私の比較的限られた読書から、文字列型のほとんどの連想配列は、実際には、フードの下で何らかのツリーで動作するハッシュ関数を使用して作成されているようです。これは、キー/値ペアの値要素の場所を指す AVL ツリーまたは赤/黒ツリーの場合があります。

このツリー構造でも、n をツリーの要素数として theta(log(n)) のオーダーを維持するには、一定時間のハッシュ アルゴリズムが必要です。それ以外の場合は、文字列を反復処理するという追加のペナルティがあります。多くの文字列を含むインデックスの場合、theta(m) は theta(log(n)) によって隠されますが、検索対象のテキストが非常に大きくなるようなドメインにいる場合は無視できません。

接尾辞ツリー/配列と Aho-Corasick を使用すると、検索を theta(m) まで下げてメモリをより多く消費できることを認識していますが、任意の長さの文字列に対して一定時間のハッシュ メソッドが存在するかどうかを具体的に尋ねています。他の SO メンバーによって主張されました。

ありがとう。

4

7 に答える 7

3

ハッシュ衝突の重大なケースを危険にさらすことなく、文字列の一般的な一定時間ハッシュ アルゴリズムを簡単に実現することはできません。

一定時間にするために、文字列内のすべての文字にアクセスすることはできません。簡単な例として、最初の 6 文字を取り上げるとします。次に誰かが来て、URL の配列をハッシュしようとします。has 関数は、単一の文字列ごとに「http://」を表示します。

他の文字選択スキームでも同様のシナリオが発生する可能性があります。前の文字の値に基づいて疑似ランダムに文字を選択することもできますが、文字列が何らかの理由で「間違った」パターンを持ち、多くが同じハッシュ値で終わる場合、依然として見事に失敗するリスクがあります。

于 2009-12-07T18:50:24.260 に答える
1

確かに、ハッシュを必要とするものに渡す前に、すべての文字列が「インターン」されていることを確認する限り、これは実行可能です。インターンは、同じ値を持つすべてのインターンされた文字列が実際には同じオブジェクトになるように、文字列を文字列テーブルに挿入するプロセスです。次に、文字列自体をハッシュする代わりに、インターンされた文字列への (固定長の) ポインターを単純にハッシュすることができます。

于 2009-12-08T16:02:07.177 に答える
1

昨年私が思いついた次の数学的結果に興味があるかもしれません。

任意の長さのすべての文字列のセットなど、無限の数のキーを {1,2,…,b} の数値のセットにハッシュする問題を考えてみましょう。ランダムハッシュは、最初に H 関数のファミリ内のハッシュ関数 h をランダムに選択することによって進められます。

すべての H 関数で確実に衝突するキーが常に無限にあること、つまり、すべてのハッシュ関数に対して常に同じハッシュ値を持つことを示します。

任意のハッシュ関数 h を選択します。セット A={s:h(s)=y} が無限になるようなハッシュ値 y が少なくとも 1 つあります。つまり、無限に多くの文字列が衝突します。他のハッシュ関数 h' を選択し、セット A のキーをハッシュします。セット A'={s が A にある: h'(s)=y'} が無限であるようなハッシュ値 y' が少なくとも 1 つあります。つまり、2 つのハッシュ関数で衝突する文字列が無数にあります。この引数は何度でも繰り返すことができます。H回繰り返します。次に、すべての文字列がすべての H ハッシュ関数で衝突する文字列の無限のセットがあります。CQFD。

さらに読む：可変長文字列の賢明なハッシュ化は不可能です http://lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/

于 2010-12-10T14:45:35.250 に答える
1

無制限の長さの文字列に対して固定時間のハッシュ関数を想像することはできませんが、実際には必要ありません。

ハッシュ関数を使用する背後にある考え方は、検討中のドメインで多くの文字列が衝突する可能性を低くするハッシュ値の分布を生成することです。このキーを使用すると、データ ストアに直接アクセスできます。これら 2 つの組み合わせにより、平均して一定時間の検索が行われます。

このような衝突が発生した場合、ルックアップ アルゴリズムはより柔軟なルックアップ サブ戦略にフォールバックします。

于 2009-12-07T18:50:11.673 に答える