java - 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> .