HashMap Трудности

Question

Это школьное задание. В целом это должно прочитать текстовый файл, добавить слова из него в хеш-таблицу. Я закодировал это, но я тестирую его, и это дает мне некоторые проблемы. Когда я пытаюсь найти индекс объекта, он всегда возвращает -1, то есть говорит, что слова не находятся в массиве, даже если они есть. Есть еще несколько проблем. Это дает мне головную боль.

import java.util.Iterator; 
import java.util.LinkedList; 


public class MyMap<K,V> implements Iterable<MyMap.MyEntry<K,V>> { 
     int collision; // maintain the current count of collisions here. 
     int slots = 0; 
     int key = 0; 
     MyEntry<K,V> tempPair; 
     LinkedList<MyEntry<K,V>> [] bucketArray; 
     int keyMod; 

    /** 
    * Create a MyMap instance with the specified number of 
    * buckets. 
    * 
    * @param buckets the number of buckets to make in this map 
    */ 
    public MyMap(int buckets) { 
     slots = buckets; 
     bucketArray = (LinkedList<MyEntry<K,V>> [])new LinkedList[buckets]; 

    } 

    /** 
    * Puts an entry into the map. If the key already exists, 
    * it's value is updated with the new value and the previous 
    * value is returned. 
    * 
    * @param key the object used as a key to retrieve the value 
    * @param value the object stored in association with the key 
    * 
    * @return the previously stored value or null if the key is new 
    */ 
    public V put(K key, V value) { 
      // don't forget hashcodes can be any integer value. You'll 
      // need to compress them to ensure they give you a valid bucket. 

     MyEntry<K,V> tempPair = new MyEntry<K,V>(key, value); 
     Word newWord = new Word((String)key); 
     keyMod = newWord.hashCode((String)key) % slots; 


     if ((bucketArray[keyMod]) == null){ 
      LinkedList<MyEntry<K,V>> firstList = new LinkedList<MyEntry<K,V>>(); 
      firstList.add(tempPair); 
      bucketArray[keyMod] = firstList; 
      return null; 
      } 

     else { 

      int indexNode = bucketArray[keyMod].indexOf(tempPair); 

      if (indexNode == -1) { 
       bucketArray[keyMod].add(tempPair); 
       collision += 1; 
       //System.out.println(indexNode); 
       return null; 
       } 
      else { 
       MyEntry<K,V> oldNode = bucketArray[keyMod].get(indexNode); 
       V oldValue = oldNode.value; 
       oldNode.value = tempPair.value; 
       //System.out.println(indexNode); 
       return oldValue; 
      } 
     } 

    } 

    /** 
    * Retrieves the value associated with the specified key. If 
    * it exists, the value stored with the key is returned, if no 
    * value has been associated with the key, null is returned. 
    * 
    * @param key the key object whose value we wish to retrieve 
    * @return the associated value, or null 
    */ 
    public V get(K key) { 
     //MyEntry<K,V> tempPair = new MyEntry<K,V>(key,value); 


     Word newWord = new Word((String)key); 
     int keyMod = newWord.hashCode((String)key) % slots; 

     if (bucketArray[keyMod] == null) { 
      return null; 
     } 

     else { 

      int temp = bucketArray[keyMod].indexOf(key); 
      if (temp == -1) { 
       return null; 
       } 

      else { 
       MyEntry<K,V> tempNode = bucketArray[keyMod].get(temp); 
       return tempNode.value; 
       } 
     } 

    } 

    /** 
    * 
    * I've implemented this method, however, you must correctly 
    * maintain the collisions member variable. 
    * 
    * @return the current count of collisions thus far. 
    */ 
    public int currentCollisions(K key) { 
     return collision; 
    } 
    /** 
    * Looks through the entire bucket where the specified key 
    * would be found and counts the number of keys in this bucket 
    * that are not equal to the current key, yet still have the 
    * same hash code. 
    * 
    * @param key 
    * @return a count of collisions 
    */ 
    public int countCollisions(K key) { 
     Word newKey = new Word((String) key); 
     int keyMod = newKey.hashCode((String) key) % slots; 
     if (bucketArray[keyMod].indexOf(key) == -1){ 
      return bucketArray[keyMod].size(); 
      } 
     return (bucketArray[keyMod].size()-1); 
    } 
    /** 
    * Removes the value associated with the specifed key, if it exists. 
    * @param key the key used to find the value to remove. 
    * @return the value if the key was found, or null otherwise. 
    */ 
    public V remove(K key) { 
     Word newWord = new Word((String)key); 
     //int keyMod = newWord.hashCode((String)key) % slots; 
     int tempNodeIndex = bucketArray[newWord.hashCode((String)key)].indexOf(key); 
     if (tempNodeIndex == -1) { 
      return null; 
      } 
     else{ 
     tempPair = bucketArray[key.hashCode()].get(tempNodeIndex); 
     V returnValue = tempPair.value; 
     tempPair.value = null; 
     return returnValue;} 
    } 
    /** 
    * Returns the number of entries in this map 
    * @return the number of entries. 
    */ 
    public int size() { 
     int size = 0; 
     for (int i =0; i< bucketArray.length; i++){ 
      size = bucketArray[i].size() + size; 
     } 
     return size; 
    } 

    /** 
    * Creates and returns a new Iterator object that 
    * iterates over the keys currently in the map. The iterator 
    * should fail fast, and does not need to implement the remove 
    * method. 
    * 
    * @return a new Iterator object 
    */ 
    public Iterator<MyEntry<K,V>> iterator() { 

     return null; 
    } 

    public static class MyEntry<K,V> { 
     K key; 
     V value; 

     public MyEntry(K k, V v) { 
      key = k; 
      value = v; 
     } 
    } 


} 

Вот Слово класса

/* The reason you can't extend String Class is because String is a final class and you can not have 
* a subclass that might alter components of a final class. Since the word class would extend the 
* String class, it would have the capability to change variables within the String Final Class. 
*/ 

public class Word { 

    String word; 

    /** 
    * Creates a Word object representing the specified String 
    * 
    * @param w the String version of this word. 
    */ 
    public Word(String w) { 
     word = w; 

    } 

    /** 
    * Returns a hashcode for this Word -- an integer whose value is based on the 
    * word's instance data. Words that are .equals() *must* have the same hashcode. 
    * However, the converse need not hold -- that is, it *is* acceptable for 
    * two words that are not .equals() to have the same hashcode. 
    */ 
    public int hashCode(String word) { 
     int code = 0; 
     for (int i =0; i<word.length(); i++){ 
      code = word.charAt(i) + code; 
     } 

     return code; //word.hashCode(); 

     //int hashCode = 0; 
     //for (int i = 0; i<word.length(); i++) { 
      //hashCode = Math.abs(hashCode*13 + word.charAt(i)); 
     //} 
     //System.out.println(hashCode); 
     //return hashCode; 
    } 

    /** 
    * Returns true if and only if this Word object represents the same 
    * sequence of characters as the specified object. Here, you can assume 
    * that the object being passed in will be a Word. 
    */ 
    public boolean equals(Object o) { 
     String passedIn = o.toString(); 
     boolean returnValue = word.equals(passedIn); 

     return returnValue; 
    } 

    /** 
    * This method returns the string representation of the object. 
    * A correct implementation will return the String representation of the 
    * word that is actually being stored. ie., if you had a word object representing 
    * 'hi', it should return 'hi' 
    */ 
    public String toString() { 
     String thisString = word; 
     return thisString; 
    } 
} 

Вот начала моего тестера:

import java.io.*; 
import java.util.*; 


public class Tester<K,V> { 

    public static void main(String [] args) throws FileNotFoundException { 

     MyMap<String, Integer> pain = new MyMap<String, Integer>(3000); 

     Scanner s = new Scanner (new File("pg4.txt")); 

     while (s.hasNext()) { 
      String word = s.next(); 
      Integer value = (Integer) pain.get(word); 

      if (value == null) { 
       pain.put(word, 1); 
      } 
      else { 
       value +=1; 
       pain.put(word, value); 
       } 
      } 
     s.close(); 
     pain.put("the",1); 
     pain.put("the",5); 
     pain.get("the"); 
     System.out.println("'the' gives this many collisions: " + pain.get("the")); 
     pain.remove("the"); 
     System.out.println("'the' gives this many collisions: " + pain.get("the")); 


    } 
} 

Answer 1

1. indexOf использует equals для сравнения, так что ваши звонки на indexOf не Работа. Вам необходимо реализовать equals для MyEntry.

   public static class MyEntry<K,V> { 
       K key; 
       V value; 
   
       public MyEntry(K k, V v) { 
        key = k; 
        value = v; 
       } 
   
       @Override 
       public int hashCode() { 
        // (overriding hashCode 
        // just because we are overriding equals) 
        return (key == null ? 0 : key.hashCode()); 
       } 
   
       @Override 
       public boolean equals(Object o) { 
        if(!(o instanceof MyEntry<?, ?>)) 
         return false; 
        MyEntry<?, ?> that = (MyEntry<?, ?>)o; 
        return(this.key == null ? 
         that.key == null : this.key.equals(that.key) 
        ); 
       } 
   } 
   

   Если вы не сделаете этого, то вам нужно создать свой собственный indexOf метод, где вы цикл через LinkedList себя.

2. Ваш метод remove фактически не выполняет удаление, просто установите значение в значение null.

   tempPair = bucketArray[key.hashCode()].get(tempNodeIndex); 
   V returnValue = tempPair.value; 
   tempPair.value = null; 
   

   Правильнее было бы:

   tempPair = bucketArray[key.hashCode()].remove(tempNodeIndex); 
   return tempPair.value; 
   

3. Насколько я могу сказать, что вам не нужно в Word класс вообще. Ваше литье до String делает предположения о том, что такое тип K, что сомнительно для универсального класса. (Что делать, если у меня есть MyMap<Long, Double>?)

   Вы только использовать его, чтобы получить hashCode, который ваш K уже есть (потому что hashCode объявлен на java.lang.Object).

   Вы можете использовать hashCode от температуры MyEntry, как я определено выше, или вызвать непосредственно:

   int keyMod = (key == null ? 0 : key.hashCode()) % slots; 
   

4. Чтобы получить Word класса работать, вам нужно правильно переопределить hashCode:

   // now you can call hashCode() on a Word 
   // when a Word is passed in to MyMap as a key 
   @Override 
   public int hashCode() { 
       int code = 0; 
       // 'word' now refers to the instance variable 
       for (int i =0; i<word.length(); i++){ 
        code = word.charAt(i) + code; 
       } 
   
       return code; 
   } 
   
   // also implementing equals correctly, but your 
   // implementation in the question probably did 
   // not cause an error 
   @Override 
   public boolean equals(Object o) { 
       if(!(o instanceof Word)) 
        return false; 
       String passedIn = ((Word)o).word; 
       boolean returnValue = word.equals(passedIn); 
       return returnValue; 
   } 
   

   Тогда вы сможете использовать MyMap<Word, Integer>.

Answer 2

Я нашел несколько проблем в своем классе MyMap, где я неправильно строил. Я нашел ошибку и исправил ее. Мои тесты также вызывают ошибки. Я исправил их. В моем классе слов не было никаких проблем. Как только я исправил их, карта построена правильно, все методы сработали.