1

取り組んでいる課題があり、何かを明確にするために教授と連絡を取ることができません。アイデアは、線形、バイナリ、およびハッシュの 3 つの異なる辞書クラスに格納する、与えられた一連の単語を使用してアナグラム ソルバーを作成するというものです。

したがって、テキストファイルから単語を読み取り、最初の 2 つの辞書オブジェクト (線形およびバイナリ) について、単語を ArrayList として保存します...簡単です。

しかし、HashDictionary については、単語を HashTable に格納するように求めています。HashTableの値がどうなるか、またはなぜそうするのかわからないだけです。指示では、すばやく検索できるように単語を Hashtable に保存すると書かれていますが、その意味がわかりません。単語を配列リストに格納するのは理にかなっていますが、キーと値のペアリングが辞書でどのように役立つかはわかりません。

多分私は十分な詳細を提供していませんが、誰かがこのようなものを見たことがあるのではないかと思いました。

各クラスには、渡された単語が辞書にあるかどうかを表すブール値を返すcontainsメソッドがあります。したがって、線形は配列リストの線形検索を実行し、バイナリは配列リストの二分検索を実行し、I'ハッシュがわからない....

4

3 に答える 3

7

違いは速度です。どちらの方法も機能しますが、ハッシュ テーブルは高速です。

ArrayList、または何らかの種類のを使用しListて要素を見つける場合、目的の単語が見つかるまで、各リスト項目を 1 つずつ検査する必要があります。単語がそこにない場合は、リスト全体をループしました。

を使用するHashTableと、検索している単語に対して、単語のハッシュの計算として知られる「魔法」を実行します。値のリストをループする代わりに、そのハッシュ値を使用して、単語がどこにあるかをすぐに推測できます。または、単語がハッシュに存在しない場合は、単語が存在しないと推測できます。

ここでは単純化しすぎましたが、それが一般的な考え方です。ハッシュテーブルがどのように機能するかについてのさまざまな説明とともに、ここで別の質問を見つけることができます。

を利用した小さなコード スニペットを次に示しますHashMap。

// We will map our words to their definitions; word is the key, definition is the value
Map<String, String> dictionary = new HashMap<String, String>();
map.put("hello","A common salutation");
map.put("chicken","A delightful vessel for protein");

// Later ...
map.get("chicken"); // Returns "A delightful vessel for protein";

あなたが説明する問題は、次HashMapの 3 つの要件を満たす辞書の基礎として aを使用することを求めています。

  • 辞書に単語を追加する
  • 辞書から単語を削除する
  • 単語が辞書にあるかどうかを確認する

キーと値を格納するマップを使用するのは直観に反するように思えます。実際に必要なのはキー (または値) だけであるためです。ただし、上で説明したように、 aHashMapを使用すると、キーに関連付けられた値を非常に迅速に見つけることができます。HashMap同様に、がキーについて知っているかどうかを非常に迅速に確認できます。辞書の各単語を キーとして に格納し、HashMapそれを (気にしないため) などのガベージ値に関連付けることで、この品質を活用できnullます。

次のように、3 つの要件を満たす方法を確認できます。

Map<String, Object> map = new HashMap<String, Object>();
// Add a word
map.put('word', null);

// Remove a word
map.remove('word');

// Check for the presence of a word
map.containsKey('word');

情報を詰め込みすぎたくはありませんが、ここでの要件は、Set. Java では、一般的に使用されるSetは ですHashSet。これは、宿題のこのビットで実装しているものとほとんど同じです。(実際、これが を使用するよう明示的に指示する宿題ではない場合は、HashMap代わりに を使用することをお勧めしますHashSet。)

于 2012-09-07T00:39:07.683 に答える
2

配列は中のものを見つけるのが難しいです.私があなたに与えた場合array[0] = "cat"; array[1] = "dog"; array[2] = "pikachu";、jigglypuffが単語かどうかを知るためだけに各要素をチェックする必要があります. 私があなたhash["cat"] = 1; hash["dog"] = 1; hash["pikachu"] = 1;"にこれをすぐに行うように与えた場合、あなたはそれを直接調べるだけです. この特定のケースでは、値 1 は重要ではありませんが、単語を検索した回数などの有用な情報をそこに入れることができます。または、1 は実際の単語を意味し、2 はポケモンの名前を意味するか、または文の長さの定義を含むことができる実際の辞書。関連性が低い。

于 2012-09-07T00:42:16.650 に答える
1

それでは、ハッシュテーブルを本当に理解していないようです。ウィキペディアでさえ、このデータ構造について適切に説明しています。

ハッシュ テーブルは文字列の大きな配列になります (最初はすべて空です)。単語内の文字を使用してハッシュ値を計算し、テーブル内のその位置に単語を挿入します。

2 つの単語のハッシュ値が同じ場合、問題が発生します。そして、いくつかの解決策があります。1 つは、配列の各位置にリストを格納し、単語をそのリストに押し込むことです。もう 1 つは、空いているポジションが見つかるまで、既知の量だけテーブルをステップスルーすることです。もう 1 つは、別のアルゴリズムを使用して 2 次ハッシュを計算することです。

これのポイントは、ハッシュ ルックアップが高速であることです。ハッシュ値を計算するのは非常に簡単で、後はその配列位置に単語が存在すること (および検索単語と一致すること) を確認するだけです。挿入に使用したのと同じハッシュ値の衝突 (この場合は不一致) のルールに従います。

テーブルのサイズを、格納する要素の数よりも大きい素数にする必要があります。また、データが (1 つのリージョンに大量にクラスター化されるのではなく) ハッシュ テーブルを介して広く分散される可能性が高くなるように、迅速に発散するハッシュ関数も必要です。

これが助けになり、正しい方向に向けられることを願っています。

于 2012-09-07T00:40:58.540 に答える