連鎖を使用したクイックハッシュテーブル

Question

ハッシュテーブルの連鎖をよりよく理解しようとしています。値をハッシュし、ハッシュ値に1つの整数のみを関連付ける単純なテーブルを求めます。問題の問題のサンプルコードは次のとおりです。

 /* hash string value return int */ 
     public int hashFunction(String D) { 
      char[] Thing = D.toCharArray(); 
      for(int i=0; i < Thing.length; i++){ 
      index += Thing[i]; } 
      return index % TABLE_SIZE;   
     } 

     /* hash string value return void */ 
     public void hashFunction(String D) { 
     char[] Thing = D.toCharArray(); 
     for(int i=0; i < Thing.length; i++){ 
     index += Thing[i];} 
     int hash = index % TABLE_SIZE; 
     if(table[hash] == null){ 
      table[hash] = new HashEntry(Level, Value); 
     }   
     else{ 
      table[hash].setNext(nd); 
     } 
     } 

     /* miscellaneous code snippet */ 
     if(table[hash] == null){ 
     table[hash] = new HashEntry(); 
     } 

     else if (Data.compareTo("VAR") == 0) { 
      Data = inFile.next(); 
      char[] Thing = Data.toCharArray(); 
      for(int i=0; i < Thing.length; i++){ 
      hash += Thing[i];} 
      hash = hash % TABLE_SIZE;   
      hm.setIntoHashTable(hash);  
       Data = inFile.next(); 
        if(Data.compareTo("=") == 0) { 
        Data = inFile.next(); 
        int value = Integer.parseInt(Data); 
        hm.getIntoHashTable(he.setValue(value)); 
       } 
     } 

Answer 1

インデックスが衝突したときに連鎖が発生します。

あなたは= 10

今、あなたはときつもりストア文字列cbaあなたは今4

としてハッシュを取得するので、あなたが同じハッシュ4

で終わる、店舗列 abcにTABLE_SIZEを持っていると仮定しましょう

cbaを同じインデックスに保存すると、インデックス4にリストが作成されて保存されます。

リストにはabcとbcaの両方が含まれます。このリストはchainと呼ばれ、同じハッシュに複数の値を格納するこのプロセスはChainingと呼ばれます。

擬似コードは次のようになります。あなたは配列やジェネリックがスムーズに行くいけないと警告を抑制するために必要がある場合があります

@SuppressWarnings("unchecked") 
List<HashEntry>[] table = new List[TABLE_SIZE]; 

：

if(table[hash] == null) 
    table[hash] = new ArrayList<HashEntry>();//APPEND ON TO THE LOCATION ALREADY THERE! 
table[hash].add(new HashEntry()); 

の表は、として宣言されます。