0

独自のハッシュ関数を実装しようとしています。Javaを使用して、各文字列のASCII番号を合計します。ハッシュテーブルのサイズと合計のmodを見つけることで、ハッシュコードを見つけます。サイズ％sum。文字列を検索するときに、同じプロセスを使用して衝突を減らす方法があるかどうか疑問に思いましたか？

前もって感謝します。

4

2 に答える 2

6

Java String.hashcode（）は、本当に優れたハッシュ関数であることと、可能な限り効率的であることの間のトレードオフを行います。文字列内の文字値を単純に合計することは、信頼できるハッシュ関数ではありません。

たとえば、2つの文字列dogとgod。どちらにも「d」、「g」、「o」が含まれているため、加算のみを含むメソッドで異なるハッシュコードが生成されることはありません。

Javaの大部分を実装したJoshuaBlochは、彼の著書「 Effective Java」でString.hashCode（）メソッドについて説明し、1.3より前のバージョンのJavaでは、String.hashCode（）関数が16文字のみを考慮していた方法について説明しています。与えられた文字列で。これは現在の実装よりもいくらか速く実行されましたが、特定の状況では驚くほどパフォーマンスが低下します。

一般に、特定のデータセットが非常に明確に定義されていて、そのデータセットの一意性を利用できる場合は、より優れたハッシュ関数を作成できる可能性があります。汎用ストリングの場合、頑張ってください。

于 2012-12-11T17:57:02.947 に答える
6

%StringとHashMapのコードを見ると、衝突率が低く、負の数を使用および処理しないためです。

文字列のソースから

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

HashMapのソースから

/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
final int hash(Object k) {
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

HashMapは常に2の累乗であるため、使用できます

        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);

と

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

長さが正であるため、使用&はよりもはるかに高速で%、正の数のみを返します。

于 2012-12-11T18:05:36.693 に答える