java - HashTable 没有输出正确的数据

Question

我的 HashTable 有问题。虽然代码可以正常编译和运行，但我没有得到我想要的输出。

final HashTable 的表大小应该为 10； Sue(453) 和 Bobby(170) 应该在索引 1 中，Robert(348) 在索引 2 中，Mark(231) 在 3 中，George(15) 在 6 中。相反，当我运行我的程序时，我的 HashTable 看起来完全不同，因为它的大小为 22，而 Bobby 有两个值(一个应该被删除)所以我不确定我做错了什么。

我怀疑我在 "put" 方法中搞砸了，但我无法理解那里可能存在的问题以及为什么在尝试删除时比较失败第一个 Bobby 值，而不是将其添加到旧值之上。

public class HashTable <K, V>
{
   private HashItem[] table;
   private int count;
   private double loadFactor;

   private static final int DEFAULT_CAPACITY = 5;
   private static final double DEFAULT_LOAD_FACTOR = 0.75;

private class HashItem <K, V>
{
   private int hash;
   private K key;
   private V value;
   private HashItem <K, V> next;

   public HashItem(int hashIn, K keyIn, V valueIn, HashItem<K, V> nextIn)
   {
    hash = hashIn;
    key = keyIn;
    value = valueIn;
    next = nextIn;
    }
}

public HashTable(int initialCapacity, double loadFactorIn)
{
   if(initialCapacity <= 0)
   {
   throw new  
            IllegalArgumentException("Capacity must be > 0.");
   }
   if(loadFactorIn < 0)
   {
   throw new IllegalArgumentException("Load factor must be > 0.");
   }
   loadFactor = loadFactorIn;
   table = new HashItem[initialCapacity];
}

public HashTable()
{
   this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public int size()
{
   return count;
}

private void rehash()
{
   HashItem[] oldTable = table;

   //create new table
   int capacity = oldTable.length * 2 + 1;
   table = new HashItem[capacity];

   //get elements at each old table index
   for(int i = 0; i< oldTable.length; i++)
   {
      HashItem<K, V> item = oldTable[i];
      //add the element from old table and its linked elements
      while(item != null)
      {
      put(item.key, item.value);
      item = item.next;
      }
   }
}

public V put(K keyIn, V valueIn)
{
   if (valueIn == null)
   {
   throw new IllegalArgumentException("Value cannot be null");
   }

   int hash = Math.abs(keyIn.hashCode());
   int index = hash % table.length;

   // get hash item at target location(if any)
   HashItem<K , V> current = table[index];
   // iterate through linked nodes at the location (if any)
   while(current != null)
   {
      //if an item with the same hash & key is there, replace
      if(hash == current.hash && current.key.equals(current.hash))
      {
       V oldItem = current.value;
       current.value = valueIn;
       return oldItem;
      }
     current = current.next;
   }      

   int threshold = (int) (table.length * loadFactor);
   if(size() >= threshold)
   {
      rehash();
      index = hash % table.length;
   }

   current = table[index];
   table[index] = new HashItem <K, V>(hash, keyIn, valueIn, current);
   count++;

   return valueIn;
}

public V get(Object keyIn)
{
   int hash = Math.abs(keyIn.hashCode());
   int index = hash % table.length;

   HashItem<K, V> item = table[index];
   while(item != null)
   {
      if(hash == item.hash && item.key.equals(keyIn))
      {
         return item.value;
      }
      item = item.next;
   }   
return null;
}

public boolean remove(Object keyIn)
 {
   int hash = Math.abs(keyIn.hashCode());
   int index = hash % table.length;

   HashItem<K, V> item = table[index];
   HashItem<K, V> previous = null;
   while(item != null)
   {
      if(item.key.equals(keyIn))
      {
      //if it is not in root node, replace links
         if(previous != null)
         {
            previous.next = item.next;
         }  
      //if it was the root, move next item in the chain down
      else{
            table[index] = item.next;
          }
      count--;
      return true;
   }        
   previous = item;
   item = item.next;
   } 
  return false;
 }

 public void makeEmpty()
   {
      table = new HashItem[table.length];
      count = 0;
   }  

public static void main(String [] args)
 {
   HashTable<String, Integer> purchases = new HashTable <String, Integer>();

   String names[] = {"Yuan", "Bobby", "Kevin"};

   purchases.put(names[0], 654);
   purchases.put(names[1], 341);
   purchases.put(names[2], 70);

   purchases.put(names[1], 170);

   System.out.println("Yuan: " + purchases.get(names[0]));
   System.out.println("Bobby: " + purchases.get(names[1]));
   System.out.println("Kevin: " + purchases.get(names[2]));

   purchases.remove(names[0]);
   purchases.remove(names[2]);

   purchases.put("Robert" , 348);
   purchases.put("Sue", 453);
   purchases.put("Mark", 231);
   purchases.put("George", 15);
 }    
}

Answer 1

浏览了您的代码。问题似乎出在你的 Rehash 方法上。当您在 rehash().. 中再次调用 put 时，put 方法不知道调用是来自用户的插入还是重新散列。即使调用重新散列，计数变量也会增加，这是不正确的。

Kindle 使用调试器来帮助自己解决其他问题。在谷歌上快速搜索调试程序会有所帮助。

编辑:内部 put 方法 current.key.equals(current.hash) 不应该更像这种比较current.key.equals(keyIn).. 原来的可能永远不会是真的，这就是替换不起作用的原因。

希望对你有帮助