Generieren einer hash-Summe für mehrere Ganzzahlen

Angesichts der Eingänge a, b, c, und d, jeweils zwischen in-Wert von 0 bis 30 (5 bits), wird Folgendes erzeugt eine Zahl im Bereich von 0 bis 255 (8 bits).

bucket = ((a & 0x18) << 3) | ((b & 0x18) << 1) | ((c & 0x18) >> 1) | ((d & 0x18) >> 3)

Ob der Allgemeine Ansatz geeignet ist, hängt davon ab, wie die Frage interpretiert wird. Die 3 am wenigsten signifikante bits werden gelöscht, Gruppierung 0-7 in dem gleichen Satz, 8-15 in der nächsten, und so weiter.

0-7,0-7,0-7,0-7 -> bucket 0
0-7,0-7,0-7,8-15 -> bucket 1
0-7,0-7,0-7,16-23 -> bucket 2
...
24-30,24-30,24-30,24-30 -> bucket 255

Trivial getestet mit:

for (int a = 0; a <= 30; a++)
    for (int b = 0; b <= 30; b++)
        for (int c = 0; c <= 30; c++)
            for (int d = 0; d <= 30; d++) {
                int bucket = ((a & 0x18) << 3) |
                             ((b & 0x18) << 1) |
                             ((c & 0x18) >> 1) |
                             ((d & 0x18) >> 3);
                printf("%d, %d, %d, %d -> %d\n",
                         a,  b,  c,  d,   bucket);
            }

Möchten Sie eine hash-Funktion, die abhängig von der Reihenfolge der Eingänge und wo ähnliche Sätze von zahlen generieren, die denselben hash? Das heißt, Sie wollen 50 5 5 10 und 5 5 10 50 zu generieren unterschiedliche Werte, aber Sie wollen 52 7 4 12 zu erzeugen, die denselben hash-50 5 5 10? Eine einfache Möglichkeit, so etwas zu tun ist:

long hash = 13;
for (int i = 0; i < array.length; i++) {
    hash = hash * 37 + array[i] /5;
}

Dies ist nicht perfekt, aber sollte Ihnen eine Idee, eine Möglichkeit zu implementieren, was Sie wollen. Es wird die Behandlung der Werte 50 - 54 als den gleichen Wert, aber Sie behandeln wird, 49 und 50 verschiedene Werte.

Wenn Sie möchten, dass die hash-unabhängig von der Reihenfolge der Eingabe (also der hash-Wert von 5 10 20 und 20 10 5 sind die gleichen), dann ein Weg dies zu tun ist zu Sortieren das array von Integer-zahlen in aufsteigender Reihenfolge vor der Anwendung des hash. Ein anderer Weg wäre, Sie zu ersetzen

    hash = hash * 37 + array[i] /5;

mit

    hash += array[i] /5;

EDIT: Unter Berücksichtigung Ihrer Kommentare in der Antwort auf diese Antwort, es klingt wie mein Versuch oben dienen können, die Ihre Bedürfnisse gut genug. Es ist nicht ideal, noch ideal. Wenn Sie eine hohe Leistung, die Sie haben einige der Forschung und des Experimentierens zu tun.

Zusammenzufassen, die Reihenfolge ist wichtig, so 5 10 20 unterscheidet sich von 20 10 5. Außerdem würden Sie im Idealfall die Speicherung der einzelnen "Vektor" getrennt in Ihrem hash-Tabelle, sondern Griff Raum Einschränkungen, die Sie speichern möchten einige Gruppen von Werten in einer Tabelle Eintrag.

Einer idealen hash-Funktion zurückgeben würde, eine Anzahl gleichmäßig über die möglichen Werte basierend auf Ihrem Tisch Größe. Doing dieses Recht hängt von der erwarteten Größe der Tabelle und der Anzahl und erwarteter maximaler Wert von der Eingabe-Vektor-Werte. Wenn Sie können negative Werte haben, als "Koordinate" Werte, dann kann dies beeinflussen, wie Sie berechnen Ihren hash. Wenn Ihre Palette von input-Werte und die hash-Funktion ausgewählt, beträgt die maximale hash-Wert ist kleiner als Ihre hash-Tabelle der Größe, dann müssen Sie ändern Sie den hash-Funktion zu erzeugen, die eine größere hash-Wert.

Würden Sie brauchen, um zu definieren, was du meinst mit "ähnlich". Hashes sind in der Regel entwickelt, um erstellen Sie einzigartige Ergebnisse, die aus einmaligen Eingabe.

Ein Ansatz wäre es, normalisieren Sie Ihre Eingabe und generieren einen hash aus den Ergebnissen.

Sie wollen,geometrische hashing. Im "standard" - hashing-Sie wollen

1. eine kurze Schlüssel
2. inverse Widerstand
3. Kollision Widerstand

Mit geometrischen hashing Sie susbtitute Nummer 3 mit etwas whihch ist fast gegenüber, nämlich in der Nähe initial-Werte in der Nähe der hash-Werte.