7

どの言語でも（問題ではありません）、文字列の配列をキーとして使用するハッシュ関数を持つことは可能ですか？

私はこのようなものを意味します：

hash(["word1", "word2", ...]) = "element"

古典的なものの代わりに：

hash("word") = "element"

キーとして使用したい各単語が関数の出力要素を変更する可能性があるため、このようなものが必要です。単語のシーケンスがあり、そのシーケンスの特定の出力が必要です（順序によって結果が変わる場合もあります）。

4

2 に答える 2

4

もちろん。すべてのデータ構造をハッシュできます。平等の厳密な定義を考え出すだけで、A == Bの場合はhash（A）== hash（B）であることを確認する必要があります。定義が[s1、s2、...、sm]==であるとします。 [t1、t2、...、tn] m==nおよびsi==ti for i = 1..mであり、さらに文字列s == tである場合に限り、| s | == |t|である場合に限ります。0 <= i <|s|の場合はs[i]==t[i]。ハッシュはさまざまな方法で作成できます。

  • リスト内のすべての文字列を連結し、任意の文字列ハッシュ関数を使用して結果をハッシュします。
  • 同じようにして、コンマ（、）などの区切り文字を追加します
  • 各文字列を個別にハッシュし、結果を排他的論理和します。
  • eash文字列を個別にハッシュし、前のハッシュ値をシフトし、新しい値をハッシュにxorします。
  • 無限に多くの可能性...

平等の厳密な定義は重要です。たとえば、リスト内で順序が重要でない場合、または文字列の比較で大文字と小文字が区別されない場合でも、A == Bの場合にhash（A）== hash（B）を保証するようにハッシュ関数を設計する必要があります。これを間違えると、ルックアップが失敗します。

Javaは、任意のデータ型のハッシュ関数を定義できる1つの言語です。実際、文字列のライブラリリストは、デフォルトのハッシュ関数を使用したキーとして問題なく機能します。

HashMap<ArrayList<String>, String> map = new HashMap<ArrayList<String>, String>();

ArrayList<String> key = new ArrayList<String>();
key.add("Hello");
key.add("World");

map.put(key, "It's me.");
// map now contains mapping ["Hello", "World"] -> "It's me."
于 2012-10-12T20:06:57.180 に答える
1

はい、可能ですが、ほとんどの場合、配列をハッシュキーに変換する独自のハッシュ関数を定義する必要があります。たとえば、Javaでは、array.hashCode（）は、オブジェクトのコンテンツではなく、参照自体に基づくObject.hashCode（）関数に基づいています。

配列の上に構築されたハッシュ関数の実装に興味がある場合は、JavaのArrays.deepHashCode（）関数も参照してください。

于 2012-10-12T20:00:22.883 に答える