リンクリストの配列にアイテムを追加するのに助けが必要

Question

私はHashtableをゼロから作るはずです。リンクされたリストの配列になっているはずです。私は自分のリンクされたリストクラス（私のコードで）と、リスト（コード内のDataItem）内のアイテムのための自分のクラスを作らなければならなかった。

私は自分のadd（word）関数に助けが必要です。私は、私のハッシュ関数を使って見つけたインデックスでリンクリストの配列にDataItemを追加することになっています（私はインデックスをうまく取得できます）。

私のコードは以下の通りです。すべてがバグフリーで、addメソッドは "うまくいく"ですが、私が作ったLinked Listクラスを実装していません。各インデックスの配列にデータ項目を入れるだけでなく、リンクされたリストの最初のリンクを置いてそこにデータ項目を置くことになっています。私がcarkcelを追加したときのような衝突があるとき、私はそれをリンクされたリストの次のリンクに追加するつもりです。私はこれにいくつかの助けを得ることができますか？私はリンクされたリストを使う方法を全く知らない。私は私のテスターのプログラムを実行すると

import java.util.*; 

public class HashTable{ 

    private int tableSize = 97; 

    //the LinkedList class I made 
    public class LinkedList { 
     private LinkedList next; 
     private final DataItem word; 

     public LinkedList(DataItem word, LinkedList next) { 
     this.word = word; 
     this.next = next; 
     } 
    } 


    public class DataItem { 

     String word; 
     int count;  // occurrence count of this word 

     public DataItem(String word) { 
      this.word = word; 
      this.count = 1; 
     } 

    } 



    /*A constructor, which takes no parameters and creates an empty hash table.*/  
    DataItem[] table = new DataItem[97]; 


    //My hash function. 
    public int hash(String word){ 
    int index = 0; 
     for(int i = 0;i < word.length(); i++){ 
     index += word.charAt(i) - 'a' + 1;  
     } 
     index = (((17 + word.length()) + index) * 17) % tableSize; 
     return index; 
    } 



    /*This method must search for word in the hash table, if it finds word, 
    it must increment the word’s occurrence count; if it does not find the word, 
    it must insert it into the hash table, giving it an initial occurrence count of 1.*/ 

    public void add(String word){ 

     //convert word to all lowercase 
     word = word.toLowerCase(); 
     int index = hash(word); 
     System.out.println("adding " + word + " at index " + index); 
     DataItem newItem = new DataItem(word);  

     //search for the word at the index location's linked list. 


     //if we don't find the word, add it to the beginning of the linked list; 
     if(table[index] == null){ 
      table[index] = newItem; 
      System.out.println(table[index]); 
      return; 
     } 


     //if we find the word, increment the word's count. 
     if(table[index] != null){ 
      if(table[index].word == word){ 
       table[index].count += 1; 
       System.out.println(table[index]); 
       return; 
      } 


      //if the word at index is different, add the new word to the next link in the linked list 
      if(table[index].word != word){ 
       System.out.println("collision!"); 
       return; 
      }   

     } 

    } 

：

import java.util.*; 
public class test { 

    public static void main(String[] args) { 

     HashTable table = new HashTable(); 

     table.add("snap"); 
     table.add("crackle"); 
     table.add("pop"); 
     table.add("pop"); 
     table.add("carkcel"); 

    } 

} 

を私が取得：インデックス43でスナップを追加

は 'スナップ'、1

インデックス48 'クラックル' でクラックルを追加します、1

インデックスにpopを追加する 'pop'、1

インデックス72でポップを追加 'pop'、2

インデックス48の衝突でcarkcelを追加！

Answer 1

配列インデックスに値を代入しようとしていますが、その配列インデックスのリンクリストに値を追加しています：リンクリストを作成した場所はわかりませんが、テーブル配列。

 if(table[index] == null){ 
     table[index] = newItem; 
     System.out.println(table[index]); 
     return; 
     } 

あなたはこのようLinkedListの方法を追加呼び出す必要があります：

if(table[index].get() == null){ 
     table[index].add(newItem); 
     System.out.println(table[index]); 
     return; 
    } 

このアルゴリズムは、別々のチェーン接続と呼ばれています。あなたはそれがどのように動作するかをここに見つけることができますKevin Wayne & Robert Sedgewick.によって書かれた本あなたはまた、私はあなたをお勧めする理由ですyoutubeでそれについてのビデオを見つける。ここで

は、配列内のLinkedListを作成する方法です。この後

for(int i = 0; i < table.length;i++){ 
    table[i] = new LinkedList(null,null); 
    } 

あなたは追加のメソッドを呼び出すと、インデックスを使用することによって得ることができます。