HashTable ne pas sortir les données correctes

Question

Je rencontre des problèmes avec mon HashTable. Alors que le code compile et fonctionne très bien, je ne reçois pas la sortie que je désire.

Le final HashTable doit avoir une taille de table 10; Sue (453) et Bobby (170) devraient être dans l'index 1, Robert (348) dans l'index 2, Mark (231) dans 3 et George (15) dans 6. Au lieu de courir mon programme, mon HashTable semble complètement différent il a une taille de 22 et Bobby a deux valeurs (une devrait avoir été enlevée) donc je ne suis pas sûr de ce que j'ai fait de mal. Je soupçonne que j'ai foiré dans la méthode "put", mais je ne peux pas comprendre ce qui pourrait être le problème ici et pourquoi la comparaison échoue en essayant de supprimer la première valeur de Bobby au lieu de l'ajouter en plus de l'ancienne valeur.

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

À travers votre code. Le problème semble être avec vous la méthode Rehash. quand vous appelez mettre à nouveau dans rehash() .. la méthode put ne sait pas si l'invocation provient de l'utilisateur en tant qu'insert ou rehash. la variable count sera incrémentée même si le rehashing est invoqué, ce qui n'est pas correct.

Kindle utilise un débogueur pour vous aider avec d'autres problèmes. une recherche rapide google sur le débogage d'un programme aidera.

EDIT: Méthode de mise à l'intérieur current.key.equals (current.hash) ne devrait-elle pas ressembler plus à current.key.equals (keyIn) .. l'original ne sera probablement jamais vrai et c'est pourquoi le remplacer ne fonctionne pas.

Espérons que cela aide