Gute Hash-Funktion für Permutationen?

Question

Ich habe Zahlen in einem bestimmten Bereich (normalerweise von 0 bis etwa 1000). Ein Algorithmus wählt einige Zahlen aus diesem Bereich aus (etwa 3 bis 10 Zahlen). Diese Auswahl wird sehr oft gemacht, und ich muss prüfen, ob eine Permutation der gewählten Zahlen bereits ausgewählt wurde.

z. B. ein Schritt wählt [1, 10, 3, 18] und ein anderer [10, 18, 3, 1] dann kann die zweite Auswahl verworfen werden, weil es eine Permutation ist.

Ich muss diese Überprüfung sehr schnell machen. Jetzt setze ich alle Arrays in eine Hashmap und benutze eine benutzerdefinierte Hash-Funktion: fasst einfach alle Elemente zusammen, also 1 + 10 + 3 + 18 = 32, und auch 10 + 18 + 3 + 1 = 32. Für equals verwende ich ein Bitset, um schnell zu prüfen, ob Elemente in beiden Mengen enthalten sind (ich brauche keine Sortierung bei Verwendung des Bitsets, aber es funktioniert nur, wenn der Zahlenbereich bekannt und nicht zu groß ist).

Das funktioniert zwar, kann aber viele Kollisionen erzeugen, daher wird die equals() -Methode oft aufgerufen. Ich habe mich gefragt, ob es einen schnelleren Weg gibt, nach Permutationen zu suchen?

Gibt es irgendwelche guten Hash-Funktionen für Permutationen?

UPDATE

Ich habe ein wenig Benchmark getan: alle Kombinationen von Zahlen im Bereich von 0 bis 6 und Feldlänge 1 bis 9. Bereich erzeugen sollte Es gibt 3003 mögliche Permutationen und eine gute Hash erzeugt schließen zu diesen vielen verschiedenen Hashes (I verwenden 32-Bit-Zahlen für die Hash):

• 41 verschiedene Hashes für gerade hinzufügen (so gibt es viele Kollisionen)
• 8 verschiedene Hashes für XOR-Verknüpfung Werte zusammen
• 286 verschiedene Hashes für
• 3003 unterschiedliche Hashes für (R + 2e) und Multiplikation als abc hat Multiplikation vorgeschlagen (mit 1779033703 für R)

So Hash-ABC kann sehr schnell berechnet werden und ist viel besser als der ganze Rest. Vielen Dank!

PS: Ich möchte die Werte nicht sortieren, wenn ich nicht muss, denn das würde zu langsam werden.

Answer 1

Ein potenzieller Kandidat könnte dies sein. Korrigieren Sie eine ungerade ganze Zahl R. Für jedes Element e, das Sie hashen möchten, berechnen Sie den Faktor (R + 2 * e). Dann berechnen Sie das Produkt all dieser Faktoren. Schließlich teilen Sie das Produkt durch 2, um den Hash zu erhalten.

Der Faktor 2 in (R + 2e) garantiert, dass alle Faktoren ungerade sind, daher zu vermeiden, dass das Produkt immer 0. Die Division durch 2 am Ende worden ist, weil das Produkt immer ungerade sein wird, damit die Division entfernt nur ein konstantes Bit.

z. Ich wähle R = 1779033703. Dies ist eine willkürliche Wahl, einige Experimente sollten zeigen, ob ein gegebenes R gut oder schlecht ist. Angenommen, Ihre Werte sind [1, 10, 3, 18]. Das Produkt (berechnet 32-Bit-Ints verwendet wird) ist

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311 

Daraus ergibt sich die Hash wäre

3376724311/2 = 1688362155.

Answer 2

Die Zusammenfassung der Elemente ist bereits eine der einfachsten Dinge, die Sie tun könnten. Aber ich denke nicht, dass es eine besonders gute Hash-Funktion w.r.t. Pseudozufälligkeit.

Wenn Sie sortieren Ihre Arrays vor dem Speichern von ihnen oder Computer-Hashes, jede gute Hash-Funktion wird ausreichen.

Wenn es um Geschwindigkeit geht: Haben Sie gemessen, wo der Engpass ist? Wenn Ihre Hash-Funktion viele Kollisionen verursacht und Sie die meiste Zeit damit verbringen müssen, die Arrays Bit für Bit zu vergleichen, ist die Hash-Funktion offensichtlich nicht gut in dem, was sie tun soll. Sorting + Better Hash könnte die Lösung sein.

Answer 3

abhängig davon, ob Sie viele Kollisionen haben (also den gleichen Hash, aber keine Permutation), könnten Sie die Arrays vorsortieren, während Sie sie hashen. In diesem Fall können Sie eine aggressivere Art von Hashing durchführen, bei der Sie nicht nur die Zahlen addieren, sondern auch etwas Bitmagick hinzufügen, um ganz unterschiedliche Hashes zu erhalten.

Dies ist nur nützlich, wenn Sie viele unerwünschte Kollisionen bekommen, weil der Hash, den Sie gerade machen, zu arm ist.Wenn Sie kaum Kollisionen bekommen, scheint die Methode, die Sie verwenden, gut zu sein

Answer 4

Ich mag die Verwendung von String-Standard-Hash-Code (Java, C# nicht sicher über andere Sprachen), es generiert ziemlich eindeutige Hash-Codes. so, wenn Sie zuerst das Array sortieren und generiert dann eine eindeutige Zeichenfolge mit einem Begrenzer.

so können Sie die folgende (Java) tun:

int[] arr = selectRandomNumbers(); 
    Arrays.sort(arr); 
    int hash = (arr[0] + "," + arr[1] + "," + arr[2] + "," + arr[3]).hashCode(); 

wenn Leistung ein Problem ist, können Sie die vorgeschlagene ineffiziente String-Verkettung ändern String oder String.format

String.format("{0},{1},{2},{3}", arr[0],arr[1],arr[2],arr[3]); 

String zu verwenden, Hash-Code garantiert natürlich nicht, dass zwei verschiedene Strings unterschiedliche Hash-Werte haben, aber angesichts dieser vorgeschlagenen Formatierung sollten Kollisionen extrem selten sein.

Answer 5

Ich würde dies vorschlagen: 1. Überprüfen Sie, ob die Längen von Permutationen gleich sind (wenn nicht - sie nicht gleich sind)

1. Sortieren nur 1-Array. Anstatt ein weiteres Array zu sortieren, iteriere durch die Elemente des ersten Arrays und suche nach dem Vorhandensein jedes einzelnen im zweiten Array (vergleiche nur, während die Elemente im zweiten Array kleiner sind - iteriere nicht durch das gesamte Array).

Hinweis: Wenn Sie in Ihren Permutationen die gleichen Zahlen haben können (zB [1,2,2,10]), müssen Sie Elemente aus dem zweiten Array entfernen, wenn es einem Mitglied aus dem ersten entspricht .

Pseudo-Code:

if length(arr1) <> length(arr2) return false; 
sort(arr2); 
for i=1 to length(arr1) { 
elem=arr1[i]; 
j=1; 
while (j<=length(arr2) and elem<arr2[j]) j=j+1; 
if elem <> arr2[j] return false; 
} 
return true; 

die Idee ist, dass stattdessen eine andere Anordnung von Sortier wir können nur versuchen, alle Elemente im sortierten Feld übereinstimmen.

Answer 6

Sie können die Kollisionen wahrscheinlich erheblich reduzieren, indem Sie das Produkt sowie die Summe der Begriffe verwenden.

1 * 10 * 3 * 18 = 540 und 10 * 18 * 3 * 1 = 540

so die Summe-Produkt-Hash wäre [32540]

Sie noch etwas über Kollisionen tun müssen wenn sie doch passieren

Answer 7

Wenn ich Ihre Frage richtig verstanden habe Sie wollen um die Gleichheit zwischen Mengen zu testen, in denen die Artikel nicht geordnet sind. Genau das wird ein Bloom-Filter für Sie tun. Auf Kosten einer kleinen Anzahl falsch positiver Ergebnisse (in diesem Fall müssen Sie einen Brute-Force-Set-Vergleich durchführen) können Sie solche Sets vergleichen, indem Sie prüfen, ob der Bloom-Filter-Hashwert gleich ist.

Der algebraische Grund, warum dies gilt, ist, dass die OR-Operation kommutativ ist. Dies gilt auch für andere Halbringe.