文字列の定数ハッシュ?

Question

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

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

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

このようなページが他にもいくつかあります (http://www.cse.yorku.ca/~oz/hash.html) いくつかのハッシュ アルゴリズムが表示されますが、それぞれの値が文字列の全長にわたって反復処理されて値が得られるようです。

このテーマに関する私の比較的限られた情報によると、文字列型の連想配列のほとんどは、内部で何らかのツリーを操作するハッシュ関数を使用して実際に作成されているようです。これは、キー/値ペア内の値要素の位置を指す AVL ツリーまたは赤/黒ツリーである可能性があります。

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

サフィックスツリー/配列とAho-Corasickにより、検索がtheta(m)まで下がり、メモリの消費が大きくなる可能性があることは承知していますが、特に尋ねているのは、任意の長さの文字列に対して定数時間のハッシュメソッドが存在するかどうかです。他のSOメンバーが主張しました。

ありがとう。

Answer 1

一般的に、私は、任意の文字列全体のハッシュは、文字列のすべての文字を使用する必要があり、したがって、n文字のために（n）をOとして成長する必要があるだろうと信じています。しかし、私は実用的な文字列を使用すると、簡単にO（1）することができおおよそのハッシュを使用することができハッシュと思います。

は常に標準ハッシュを計算するために、MIN（N、20）文字を使用する文字列のハッシュを考えてみましょう。これは明らかに、文字列のサイズをO（1）のように成長します。それは確実に動作しますか？それはあなたのドメインに依存して...

Answer 2

ハッシュ関数はする必要はありません（とすることはできません）すべての文字列のためのユニークな値を返します。

あなたは乱数ジェネレータを初期化して、文字列から100個のランダムな文字列を引き出し、それをハッシュするためにそれを使用するために最初の10個の文字を使用することができます。これは、一定の時間になります。

あなたはまた、単に1が厳密に一定の値を返すことができ、これは非常に便利な1枚の静止ハッシュ関数である、ではないが。

Answer 3

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

それは一定の時間であるためには、

、あなたは、文字列内の各文字にアクセスすることはできません。簡単な例として、我々は最初の6つの文字を取るとします。そして、誰かが来て、URLの配列をハッシュしようとします。持っている機能が表示されます「のhttp：/」。すべての単一の文字列の

同様のシナリオは、他の文字の選択スキームのために発生することがあります。あなたは、擬似ランダム前の文字の値に基づいて文字を選ぶことができますが、何らかの理由で文字列が同じハッシュ値を「間違っている」パターンと、多くのエンドアップを持っている場合、あなたはまだ見事に失敗のリスクを実行します。

Answer 4

あなたはできる 希望 を使用すると、線形ハッシュ時間よりも漸近的に短くなります ロープ 文字列の代わりに、一部の計算をスキップできる共有機能を備えています。しかし明らかに、ハッシュ関数は読み取っていない入力を分離できないため、「すべてを一定時間内にハッシュできる」ということをあまり真剣に受け止めたくありません。

ハッシュ関数の品質とそれにかかる計算量の間で妥協することは何でも可能ですが、長い文字列に対するハッシュ関数にはいずれにせよ衝突が発生する必要があります。

あなた ハッシュ関数がプレフィックスのみを調べる場合、アルゴリズム内で発生する可能性のある文字列が頻繁に衝突するかどうかを判断する必要があります。

Answer 5

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

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

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

Answer 6

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

Answer 7

あなたは、私が去年思い付いた以下の数学的結果に興味がある可能性があります。

キー、例えば、任意の長さと数の集合におけるすべての文字列の集合{1,2、...、B}としての無限の数をハッシングの問題を考えます。最初のH関数のファミリーでランダムハッシュ関数Hでピッキングによるランダムハッシュ進む。

私はすべてHの機能の上に衝突する確実なキーの無限の数が常にあることが示されます、つまり、彼らは常に、すべてのハッシュ関数に同じハッシュ値を持ってます。

任意のハッシュ関数Hを選び：集合A =そのような少なくとも1つのハッシュ値yがある{S：H（S）= Y}無限であるが、つまり、あなたが衝突無限に多くの文字列を有しています。無限である：セットA 『{（S）= Y '= H Sはである』}ように、「少なくとも1つのハッシュ値yがあり、セットAのキーをハッシュ」他のハッシュ関数Hを選択つまり、2つのハッシュ関数に衝突し、多くの文字列が無限にあります。あなたはこの引数を任意の回数繰り返すことができます。 H回それを繰り返します。そして、あなたはすべての文字列があなたのHのハッシュ関数のすべての上に衝突した文字列の無限集合を持っています。 CQFDます。

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