Java Hash符号表的实现

Question

我使用一个数组列表构建了一个符号表，其中填充了一个对象“对”，它们是单链接链，包含一个单词和它在文本文件中出现的次数。我需要在FrequencyCounter程序中使用它来计算文件中的字数。由于某些原因，我在使用HashST运行FrequencyCounter时出现以下错误：

Processed 1215985 words (19 sec; 19710 msec
Exception in thread "main" java.lang.NullPointerException

at HashST.hashIndex(HashST.java:60)
at HashST.get(HashST.java:105)
at FrequencyCounter.main(FrequencyCounter.java:112)

我有一个想法，我的HashST出了点问题，它没有像我想要的那样把配对放到ArrayList中。任何关于实现错误的建议都将不胜感激。

下面是我的代码和FrequencyCounter的代码：

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

public class HashST<Key extends Comparable<Key>, Value> implements Iterable<Key> {
private ArrayList<Pair> chains;
private int numKeys;
private int numChains;


public class Pair
{
    Key key;
    Value value;
    Pair(Key k, Value v)
    {
        key = k;
        value = v;
    }
    Pair()
    {}

    Pair next;
}

    /**
 * Initialize an empty HashSt with a default of 64 empty chains.
 */
    public HashST()
    {
        this(64);

    }

/**
 * Initialize an empty HashST with numChains emptychains.
 * 387911 is a prime number about twice the number of distinct
 * words in the leipzig1M.txt file.
 */
public HashST(int numChains)
{
    this.numChains = numChains;
    chains = new ArrayList<Pair>();

    for(int i = 0; i < numChains; i++)
    {
        Pair p = new Pair(null, null);
        chains.add(p);

    }
}

/**
 * compute the hash index for a key k if the number of
 * chains is N
 */
private int hashIndex(Key k, int N)
{
    return (k.hashCode() & 0x7fffffff) % N;

}
/**
 * insert the Pair (k,v) into the appropriate chain and increment 
 * the number of keys counter or 
 * update the value for k if k is already in the hash table.
 *
 */
public void put(Key k, Value v) {

    int i = hashIndex(k, numChains);
    Pair tmp = chains.get(i);
    if(contains(k))
    {
        while(tmp.next != null)
        {
            if(tmp.key == k)
            {
                tmp.value = v;
                return;
            }

            tmp = tmp.next;
        }
    }
    else
    {
        Pair p = new Pair(k, v);
        tmp.next = p;
        numKeys ++;

    }




}

/**
 * return the value for key k if it is in the hash table
 * or else return null if it is not.
 */
public Value get(Key k) {

    int i = hashIndex(k, numChains);
    Pair tmp = chains.get(i);
        while(tmp.next != null)
        {
            if(tmp.key == k)
            {
                return tmp.value;

            }

            tmp = tmp.next;
        }


    return null;

}

/**
 * remove the pair with key k if it is in the hash table
 * otherwise no change.
 */
public void delete(Key k) {

    if(contains(k))
    {
        return;


    }

}

/**
 * return true if the hash table contains a pair with key 
 * equal to k else return false
 */
public boolean contains(Key k) {

    return (get(k) != null) ? true : false;

}

/**
 * return the number of keys in the hash table
 */
public int size() {

    return numKeys;

}

/**
 * return a LinkedList<Key> containing the keys in the
 * hash table
 */
public Iterable<Key> keys() {

    LinkedList<Key> l = new LinkedList<Key>();
    for(Pair p : chains)
    {
        while(p.next != null)
        {
            l.add(p.key);
            p = p.next;
        }

    }


    return l;
}

/**
 * return an Iterator<Key> for the keys in the hash table
 */ 
public Iterator<Key> iterator() {
    return keys().iterator();
}

}

下面是频率计数器：http://algs4.cs.princeton.edu/31elementary/FrequencyCounter.java.html

Answer 1

根据您的堆栈跟踪，这似乎是抛出空指针的行：

return (k.hashCode() & 0x7fffffff) % N;

所以我们有一个对象引用k，一个整数常量和一个原语N，常量和原语都不能为空，这里唯一被取消引用的是k，所以看起来有人试图得到一个空k的值！