1

我正在尝试使用哈希表实现字典（不使用 Java 提供的哈希表类，而是从头开始制作）。下面是insert()我的 Dictionary 类中的方法，用于将元素插入到包含在特定数组位置的链表中。

我正在运行一个提供的测试程序来确定我的 Dictionary 类是否有效，但是ArrayIndexOutOfBoundsException: -5980在达到某个点时我遇到了。下面包括特定的测试。为什么会出现这个异常？（如果需要，我可以提供更多代码！）

插入：

public int insert(DictEntry pair) throws DictionaryException {
    String entryConfig = pair.getConfig();
    int found = find(entryConfig);

    if (found != -1) {
        throw new DictionaryException("Pair already in dictionary.");
    }

    int entryPosition = hash(entryConfig);

    if (dict[entryPosition] == null) { //Dictionary.java:54
        LinkedList<DictEntry> list = new LinkedList<DictEntry>();
        dict[entryPosition] = list;
        list.add(pair);
        return 0;
    } else {
        LinkedList<DictEntry> list = dict[entryPosition];
        list.addLast(pair);
        return 1;
    }
}

考试：

    // Test 7: insert 10000 different values into the Dictionary
    // NOTE: Dictionary is of size 9901
    try {
        for (int i = 0; i < 10000; ++i) {
            s = (new Integer(i)).toString();
            for (int j = 0; j < 5; ++j) s += s;
            collisions += dict.insert(new DictEntry(s,i)); //TestDict.java:69
        }
        System.out.println("   Test 7 succeeded");
    } catch (DictionaryException e) {
        System.out.println("***Test 7 failed");
    }

异常堆栈跟踪：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -5980
    at Dictionary.insert(Dictionary.java:54)
    at TestDict.main(TestDict.java:69)

哈希函数：

private int hash(String config) {
int expBase = 41;
int exp;
int ASCIIChar;
int hashedConfig = 0;

    for (int i = 0; i < config.length(); i++) {
        ASCIIChar = (int)config.charAt(i);
        exp = (int)Math.pow(expBase, i);
        hashedConfig = hashedConfig + (ASCIIChar * exp);
    }

    hashedConfig = hashedConfig % dictSize;
    return hashedConfig;
}
4

2 回答 2

3

您的

exp = (int)Math.pow(expBase, i);
hashedConfig = hashedConfig + (ASCIIChar * exp);

将溢出整数范围，因此生成负数。Math.abs在返回 hashedConfig 之前添加一个。

您可能应该分析这如何影响散列函数的分布。

于 2012-10-16T07:28:50.437 回答
0

对 - 正如所怀疑的那样，问题出在hash(). 这：

hashedConfig = hashedConfig % dictSize;

...不保证它会是积极的。如果一开始是负数，你仍然会得到一个负数。你可以使用：

hashedConfig = Math.abs(hashedConfig % dictSize);

或者：

hashedConfig = hashedConfig % dictSize;
if (hashedConfig < 0) {
    hashedConfig += dictSize;
}

两者都会为您提供正确范围内的值，但您可能会发现后者更统一。

请注意，您的哈希代码也非常低效。根本不清楚你为什么不使用String.hashCode()开始。（您仍然需要将任意 32 位整数转换为数组元素范围内的值，但至少散列本身会更快。）

于 2012-10-16T07:25:34.247 回答