讓我的哈希算法工作出現問題

Question

問題已解決（目前無法接受答案，我改變了我的while循環，現在它可以工作，我在下面爲任何未來的觀衆回答了這個問題）：我的哈希算法algortihm讓我頭痛。我從鑰匙的文件讀取輸入，並使用少量的鑰匙，我的代碼工作，一旦我使它成爲300字，我有問題。哈希函數位於底部，while循環位於主函數的主體中，用java編寫。哈希函數運行良好，身體也一樣，直到我愚蠢地改變了身體並丟失了原始代碼。我想我涵蓋了溢出問題，但任何幫助將不勝感激，謝謝！

t大小是如何計算的：

//Calcking tSize 
tSize = (int)(items*tSizeFactor); 

//Making tSize prime 
while(!isPrime((int)tSize)) 
    tSize++; 

While循環，當我從文件中讀取：

while(line != null) { 
       //Getting the address to place the value in 
       position = hash(line.toCharArray(), (int)tSize); 

       //If there is something there we enter the if statement 
       if(hashTable[position][0] != null) { 
        //while we haven't found a spot and i < tableSize we update the last position we were at and move through the array 
        for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) { 
         //prevPosition is used to update the link in the spot just before our final destination, allows wrap around in the array 
         prevPosition = position; 
         //we add +i to the original position and modulo the table size allowing wrap around in the array 
         position = (position+i)%(int)tSize; 
        } 
        //finally when we found a spot we update the previous position to link to the new item 
        hashTable[prevPosition][1] = Integer.toString(position); 
       } 

       //Adding the values to the hash table and setting the link to -1 
       hashTable[position][0] = new String(line); 
       hashTable[position][1] = new String(Integer.toString(-1)); 

       line = reader.readLine(); 
      } 

public static int hash(char ch[],final int TSIZE) { 
     int sum = 7; 
     for(int i = 0; i < ch.length; i++) { 
      sum = sum*31+ch[i]; 
      sum <<= 3; 
     } 

     if(sum < 0) 
      sum *= -1; 

     return sum%TSIZE; 
    } 

Answer 1

我的改變而循環這解決了這個問題：

while(line != null) { 
        //Getting the address to place the value in 
        position = hash(line.toCharArray(), (int)tSize); 

        //If there is something there we enter the if statement 
        if(hashTable[position][0] != null) { 

         //Go to the end of the chain 
         while(hashTable[position][1].compareTo("-1") != 0) 
          position = Integer.parseInt(hashTable[position][1]); 

         //Save the position of the end of the chain 
         prevPosition = position; 

         //while we haven't found a spot and i < tableSize we update the last position we were at and move through the array 
         for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) { 
          //we add +i to the original position and modulo the table size allowing wrap around in the array 
          position = (position+i)%(int)tSize; 
          System.out.println("Position: " + position); 
         } 

         //finally when we found a spot we update the previous position to link to the new item 
         hashTable[prevPosition][1] = Integer.toString(position); 
        } 

        //Adding the values to the hash table and setting the link to -1 
        hashTable[position][0] = new String(line); 
        hashTable[position][1] = new String(Integer.toString(-1)); 

        line = reader.readLine(); 
       } 

Answer 2

1. 新的字符串（行）是沒用的。

2. 對（INT I = 1;！我<（int）的t大小& & hashTable中[位置] [0] = NULL;我++）

   位置0不用於？

3. prevPosition可以是本地的if(hashTable[position][0] != null) {塊。

4. 存儲上一個哈希表的位置看起來沒用。

   UPD

5. 位置=（位置+ⅰ）％（INT）t大小;

試試這個 http://en.wikipedia.org/wiki/Quadratic_probing

Answer 3

首先一個問題，爲什麼不使用內置的哈希表？

通過閱讀您的代碼，我發現了一些問題。它們可能不正確，因爲無法從您當前的代碼中知道更多信息。例如tSize。

• 你有一個tSize，我認爲這是散列表的容量。但是我沒有看到你何時增加它。這將是問題，至少是性能問題。但在你的暗示中，這是功能性問題。例如，如果你的tSize是100，那麼你的散列表中可以有最多100個元素。

• 採取循環看看這個：

  for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) { 
      prevPosition = position; 
      position = (hash(line.toCharArray(), (int)tSize)+i)%((int)tSize); 
  } 
  

當碰撞發生時，這將被執行（我不明白，你爲什麼再次調用散列函數你可以循環來。找一個空閒位置。）你想保留原來的key，並讓它參考一個空閒的位置。但是，如果情況更糟，在您再次調用散列函數後，新的position仍然被佔用（再次發生衝突），那麼您將覆蓋prePosition，以便您丟失原始的key。當你從哈希表中獲取數據時，這會是個問題。

• 由於上述兩點。當你的哈希表已滿時，你的代碼只是覆蓋最後一個元素。