0

整数がアプリに供給され、整​​数がハッシュされてから配列に配置される割り当てに取り組んでいます。配列内の各位置は、私が作成したリンク リストです。私の問題は、整数が配置される配列内の位置を指定できないように見えることです。現在、私の出力は、null である位置 10 を除く配列内のすべての場所に配置される最後の 5 つの整数です。どんな助けでも大歓迎です。ありがとうございました。

public class MyHashTab {
  private static MyList last;
  private static MyList first;

  public MyHashTab(int initialCapacity, MyList[] anArray) {

  }

  public static void insert(int searchKey, MyList[] anArray) {
    int hash = searchKey % anArray.length;
    MyList current = new MyList(searchKey);

    current.next = null;

    if (anArray[hash] == null) {
      current.next = null;
      first = current;
      last = current;
      anArray[hash] = current;
    } else {
      last.next = current;
      last = current;
    }
  }

  public static void printHash(MyList[] anArray) {
System.out.println("The generated hash table with separate chaining is: ");

    for (int i = 0; i < anArray.length; i++) {
      if (anArray[i] == null) {
        System.out.println("\nThe items for index[" + i + "]: ");
        i++;
      }

      System.out.print("\nThe items for index[" + i + "]: ");
      MyList temp = first;

      while (temp != null) {
        System.out.print(temp.iData + "\t");
        temp = temp.next;
      }
    }
  }
}

public class MyList {
  int iData; // This integer is used as a key value, and as a way to see the actual node instead of it's memory address.
  MyList next; // This is a pointer to a nodes right child. 

  public MyList(int searchKey) {
    this.iData = searchKey;
  }
}

問題は26行目から始まるelseステートメントにあると思います。新しい整数部分を作成するリンクリストを割り当てていません。正しい書き方はありますか？

anArray[hash].last.next = current;
anArray[hash].last = current;

if ステートメントと else ステートメントの両方に print ステートメントを追加し、両方を使用しています。ありがとうございました。

出力

The generated hash table with separate chaining is: 
The items for index[0]: 366 976 312 244 655
The items for index[1]: 366 976 312 244 655
The items for index[2]: 366 976 312 244 655
The items for index[3]: 366 976 312 244 655
The items for index[4]: 366 976 312 244 655
The items for index[5]: 366 976 312 244 655
The items for index[6]: 366 976 312 244 655
The items for index[7]: 366 976 312 244 655
The items for index[8]: 366 976 312 244 655
The items for index[9]: 366 976 312 244 655
The items for index[10]: 
The items for index[11]: 366    976 312 244 655

予想される出力は次のようになります。別々のチェーンで生成されたハッシュ テーブルは次のとおり
です。 インデックス [0] のアイテム: 36 60 108 312
インデックス [1] のアイテム: 85
インデックス [2] のアイテム: 290 422
インデックス [3] のアイテム: 99 135
索引 [4] の項目: 76 148 244 568 976
索引 [5]​​ の項目: 29 173 245
索引 [6] の項目: 366
索引 [7] の項目: 619 655 703
索引 [8] の項目]: 56
索引 [9] の項目: 345
索引 [10]
の項目: 索引 [11] の項目: 23 47

ハッシュされた後、適切な位置に配列リストに配置された各整数。

4

2 に答える 2

2

免責事項：私は少し怒鳴りました。関連するすべてのものを書き留めようとしています。ソリューションにのみ興味がある場合は、見出しを太字にした場所までスクロールします...

最初から、Nathaniel Ford が述べたように、HashTable 実装がどのように機能するかについて概念的な誤解があると思います。ロジックを分解することから始めましょう。

HashTable は、格納しているオブジェクトの一意の (またはほぼ一意の) ハッシュを計算することにより、オブジェクトを格納してすばやく取得するために使用される構造です。この一方向ハッシュを計算し、それを使用してオブジェクトをテーブルに格納すると、理想的なケースで O(1) ルックアップが可能になります。

完璧な世界では、すべての入力が一意にハッシュされ、衝突が発生することはありませんが、それが現実的でないことはわかっています。したがって、複数のオブジェクトがある場合は、複数のオブジェクトを同じハッシュ値に格納できるコレクションが必要です。LinkedList！_

ここで、12 個の値のセット配列を使用して、要素ごとに一意の LinkedList を用意する必要があります。書き出された場合の期待される出力は次のようになります。

hashTable[0] = LinkedList( Node(36)-> Node(60)-> Node(108)-> Node(312))
hashTable[1] = LinkedList( Node(85))
など...

現在、リンクされたリストのコレクションと一緒に単一のリンクされたリストのアイデアをマッシュアップしようとしています。この誤解は次のとおりです。

private static MyList last;
private static MyList first;

クラス変数として宣言することによりfirst、本質的に、各リストが個別に独自の最初/最後のポインターを持つ必要がある、リンクされたリストのコレクション全体に対して1 つlastだけの変数が存在するという信念を作成しています。コードの結果として作成されるのは、配列内のさまざまな位置に挿入されたノードがそれらとはまったく関係のない位置への参照を持つロジックです。firstlast

では、実際には、どこから修正を開始すればよいのでしょうか?

insert物事を一歩一歩進めるような方法でクリーンアップします。

1) 着信オブジェクトのハッシュを計算する
2) 配列でハッシュを検索する
3) 配列の場所が null の場合、新しいリンク リストを生成し、値を配列に挿入する
3b) 配列が null でない場合、新しいノードを作成するリストを作成し、既存のリストの最後のノードを新しいノードに
向ける 4) 完了

Nathaniel のコードはこのニーズに最適ですが、実装を使用する必要がある場合は、次のMyListように動作します。

int hash = searchKey % arr.length;
MyList newNode = new MyList(searchKey);
MyList arrIndex = arr[hash];

if (arrIndex == null) {
  arr[hash] = newNode;
} else {
  while (arrIndex.next != null) { 
    arrIndex = arrIndex.next;
  }
  arrIndex.next = newNode;
}

さらに、printHash2 つの問題により、メソッドを更新する必要があります。

i1) arr[i] が null のイベントで増加するためのロジックにより、範囲外になる可能性があります。配列の最後のインデックスが null の場合は、iチェックせずに増やします。次のようなチェックを行い、ループに任せたほうがよいでしょう:

if (anArray[i] == null) {
  continue;
}

またはコードをよりクリーンに保つ (プログラム フローにランダムなジャンプがない)

for (...) {
  if (anArray[i] != null) {
    //Code to print that array
  }
}

2) and を使用せずfirstにlast、各要素を反復するだけです

for (int i = 0; i < anArray.length; i++) {
  System.out.print("\nThe items for index[" + i + "]: ");

  if (anArray[i] != null) {
    MyList tmp = anArray[i];
    while ((tmp = tmp.next) != null) {
      System.out.print(tmp.iData + " ");
    }
  }
}
于 2013-04-10T19:14:31.737 に答える