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.abshashedConfigを返す前にを追加します。

おそらく、これがハッシュ関数の分布にどのように影響するかを分析する必要があります。

于 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 に答える