10

整数の順序が計算されたハッシュ値に影響を与えないように、一連の整数をハッシュしたいと考えています。すなわちH([32224,12232,564423]) == H([564423,32224,12232])。

ユニークなセットの数は、数百万の範囲になります。速度は非常に重要ですが、選択したアプローチとの衝突の上限を知る必要があります。

ウィキペディアにはベクトルのハッシュに関する優れたセクションがありますが、コードで自信を持って実装するための背後にある数学を理解していません。誰かがコードに関連する数学を説明できれば幸いです。理想的には、最終的なハッシュを 32 ビットにしたいと考えています。それが役に立ったら - 私はこれを Java で実装します。

更新：パフォーマンス上の理由から（そのようなセットを多数操作するため）、セット内の整数のソートを避けることを特に検討しています。

4

5 に答える 5

7

簡単なアプローチは、個々の整数のハッシュを一緒に xor または追加することです。xor と add は交換可能であるため、これは順序の独立性を満たします。

したがって：

int hc = 0;
for(int i = 0; i < n; i++) {
   hc += a[i];
}
return hc;

また

int hc = 0;
for(int i = 0; i < n; i++) {
   hc ^= a[i];
}
return hc;

とにかく、intのハッシュコードはその値だからです。

実際、これはまさにHashSet<Integer>.hashCode(uses add) が行うことです。整数が既にボックス化されている場合、またはボックス化を処理できる場合、それは組み込みのソリューションです。

于 2013-08-02T16:22:23.293 に答える
2

クラスのオーバーヘッドなしで速度が必要であると仮定すると、次のように*Set記述できます。H

/**
 * Hashes a set of integers.
 * 
 * @param list to hash
 * @return hash code
 */
public static int H(int list[]) {
    // XOR all the integers together.
    int hashcode = 0;
    for (int val : list) {
        hashcode ^= val;
    }
    return hashcode;
}

順番に関係なく同じで、比較的効率的です。

例えば：

public static void main(String[] args) {
    System.out.println(Integer.toHexString(H(new int[]{0xabcd,0x1234,0x1111})));
    System.out.println(Integer.toHexString(H(new int[]{0x1234,0x1111,0xabcd})));
}

表示:

a8e8
a8e8

これは、次のようにすることで、単なるints以外にも一般化できます。

/**
 * Hashes a set of objects.
 * 
 * @param list to hash
 * @return hash code
 */
public static int H(Object list[]) {
    // XOR all the hashes together.
    int hashcode = 0;
    for (Object val : list) {
        hashcode ^= val.hashCode();
    }
    return hashcode;
}

その場合、プログラムはプリミティブmainの代わりに の配列を使用する必要があります。 Integerint

数値の追加はほぼ同じ速度で行われ、32 ビット範囲でより適切な分布が得られる可能性があります。セットの要素が範囲全体にすでに均一に分布している場合は、xor の方が適している可能性があります。

ただし、どちらの方法でも、整数を使用して衝突を簡単に作成できます。たとえば、adding メソッドを使用します。

{1000, 1001, 1002}
{0, 1, 3002}

これらの配列はどちらも同じH()です。

XORメソッドを使用。

{0x1010, 0x0101}
{0x1111, 0x0000}

これらはどちらも同じH()です。

同様に、0リストはそれの有無にかかわらず同じハッシュを持つため、要素には問題があります。これは、反復ごとに定数値を追加することで軽減できます。例えば：

            ...
            hashcode += val.hashCode() + CONSTANT;
            ...

または、要素の数を初期ハッシュ コードとして含めることにより、次のようにします。

            ...
            // XOR all the hashes together.
            int hashcode = list.length;
            ...
于 2013-08-02T16:39:07.693 に答える
2

すべての整数を Java HashSet に入れて、その hashCode を使用できます。

一方、java.util.Set はドキュメントで次のように指定します。

このセットのハッシュ コード値を返します。セットのハッシュ コードは、セット内の要素のハッシュ コードの合計と定義されます。ここで、null 要素のハッシュ コードはゼロと定義されます。これにより、s1.equals(s2) は、Object.hashCode() の一般的な規約で要求されるように、任意の 2 つのセット s1 および s2 に対して s1.hashCode()==s2.hashCode() を暗示します。

そして Integer.hashCode() は

この Integer オブジェクトによって表されるプリミティブ int 値と等しい、このオブジェクトのハッシュ コード値。

i1, i2, ... i_nしたがって、 Java 標準ライブラリの整数セットの hashCodeは ですi1 + i2 + ... + i_n。

数値がかなり小さい場合は、各要素に適切なサイズの素数を掛けることもできます。Knuth は 2654435761 を使用しましたが、これは Java int には大きすぎますが、その 2 の補数である -1640531527 を使用できます。したがって、C = -1640531527 とすると、コードはC*i1 + C*i2 + ... C*i_n.

private static final int C = -1640531527;

public static int calculateHash(int[] set) {
    int code = 0;
    for (int e: set) {
        code += C * e;
    }

    return code;
}

しかし、この考え方には明らかな欠陥が 1 つあります。hashCode を使用するには、2 つのセットが実際に等しいことを証明できる必要があります。したがって、いずれにせよ、証明する最も簡単な方法は、要素をソートすることです。もちろん、セットの数が数百万よりも大幅に少ない場合は、衝突もそれほど多くありません。

于 2013-08-02T16:15:05.667 に答える