0

割り当て用に独自の HashTable を実装しています。テキスト ファイルから読み取り、その内容を HashTable に追加する必要があります。私が遭遇したいくつかの問題があります、

1) 文字列の一部のハッシュ値が負の数値として出力されます。

2) 一部の単語が追加されていません。

ハッシュ関数のコードは次のとおりです。

   public int hash(String key) {
        int hashkey = key.hashCode();

        return hashkey % arraySize;
    } // END hash()

computerそれが整数を返す単語については、-97これを回避するために、整数が負の場合に正になるように if ステートメントを含めました。ただし、これでも単語computer, は index の HashTable に追加されません97。

追加されない他の単語は次のとおりtree, subtree, record, singleです。ファイル I/O 用の関数と HashTable への追加は次のとおりです。

public static void readParagraph() {
    BufferedReader reader;
    String inputLine;

    try {
        reader = new BufferedReader(new FileReader(".\\src\\paragraph.txt"));
        while((inputLine = reader.readLine()) != null) {
            String[] strings = inputLine.split("(\\s|\\p{Punct})+");
            insertParagraph(strings);
        }
    } catch (IOException e) {
        System.out.println("Error: " + e);
    }
} // END readParagraph()

private static void insertParagraph(String[] strings) {
    Link link;
    for (String string : strings) {
        if (!string.equals("")) {
            link = new Link(string.replaceAll("[^a-zA-Z'\\s]", "").toLowerCase());
            paragraph.insert(link);
        }
    }
} // END insertParagraph()

一部の単語が追加されていない理由について、何が間違っているのか誰か知っていますか? または、ハッシュ値に負の数が表示されるのはなぜですか?

編集: 詳細情報

public class A4Q3 {
    static HashTable dictionary = new HashTable(1009);
    static HashTable paragraph = new HashTable(164);
    public static void main(String[] args) {
        readParagraph();
        paragraph.displayTable();
        System.out.println();
        System.out.println(paragraph.wordCount);
    } // END main()

    public void insert(Link link) {
        String key = link.getKey();
        Link previous = null;
        Link current = first;

        while(current != null && key.compareTo(current.getKey()) > 0) {
            previous = current;
            current = current.getNext();
        }

        if(previous == null) {
            first = link;
        } else {
            previous.setNext(link);
            link.setNext(current);
        }
    } // END insert()

リンク クラス:

public class Link {
private String data;
private Link next;

public Link(String data) {
    this.data = data;
} // END Link()

public String getKey() {
    return data;
} // END getKey()

public void displayLink() {
    System.out.print(data + " ");
} // END displayLink()

public Link getNext() {
    return next;
} // END getNext()

public void setNext(Link next) {
    this.next = next;
} // END setNext()

} // リンク終了

4

1 に答える 1

2

負のハッシュ コードを適切に処理していません。

   public int hash(String key) 
   {
        int hashkey = key.hashCode();

        return hashkey % arraySize;
   }

あなたが言ったように、hashkeyマイナスなら問題があるので、できることはhash機能を変えることです。

ハッシュコードの修正:

   public int hash(String key) 
   {
        int hashkey = key.hashCode();

        return (hashkey & 0x7FFFFFFF) % arraySize;
   }

これは、31 個の 1 の16 進数であるbitwise andwith hashkeyandを実行します。つまり、次のようになります。0x7FFFFFFF

01111111 11111111 11111111 11111111

したがって、すべての入力が正の数に変換されます。これは、最上位の数字が 0 になることを除いて、すべての数字が 1 になるためです。Java はbitwise and2のand補数を使用するため、最上位の数字が使用されます。サインを示すこと。は 0 なので、この値は常に正になります。hashkeyand0 & 1

のハッシュ値が負の値になるのは、 forStringが原因です。hashCode()String

文字列の負のハッシュ値の理由:

public int  hashCode() 
{
        int h = hash;

        if (h == 0) 
        {
            int off = offset;
            char val[] = value;
            int len = count;

            for (int i = 0; i < len; i++) 
            {
                h = 31*h + val[off++];
            }

            hash = h;
        }

        return h;
    }

ソース コードは同じではない可能性がありますが、負の数の理由は同じではないことに注意してください。hが よりも大きくなるとInteger.MAX_VALUE、 にラップしますInteger.MIN_VALUE。つまり、次のようになります。

Integer.MAX_VALUE + 1 == Integer.MIN_VALUE
于 2013-07-15T17:06:45.990 に答える