Ein Leitfaden zur Falttechnik in Java

1. Einleitung

In diesem Tutorial betrachten wir Hashing-Techniken, die in verschiedenen Datenstrukturen verwendet werden und einen zeitlich konstanten Zugriff auf ihre Elemente ermöglichen.

Wir diskutieren detaillierter die sogenannte Falttechnik und geben eine kurze Einführung in die Mid-Square- und Binning-Techniken.

2. Übersicht

Wenn wir Datenstrukturen zum Speichern von Objekten auswählen, ist eine der Überlegungen, ob wir schnell darauf zugreifen müssen.

Das Java-Dienstprogramm bietet uns eine Vielzahl von Datenstrukturen zum Speichern unserer Objekte. Weitere Informationen zu Datenstrukturen finden Sie auf unserer Kompilierungsseite für Java-Sammlungen, die Anleitungen zu mehreren von ihnen enthält.

Wie wir wissen, können wir mit einigen dieser Datenstrukturen ihre Elemente in konstanter Zeit abrufen, unabhängig von der Anzahl der darin enthaltenen Elemente.

Das wahrscheinlich einfachste ist das Array. Tatsächlich greifen wir über ihren Index auf Elemente im Array zu. Die Zugriffszeit hängt natürlich nicht von der Größe des Arrays ab. Tatsächlich verwenden viele Datenstrukturen hinter den Kulissen stark Arrays.

Das Problem ist, dass die Array-Indizes numerisch sein müssen, während wir diese Datenstrukturen häufig lieber mit Objekten bearbeiten.

Um dieses Problem zu lösen, versuchen viele Datenstrukturen, Objekten einen numerischen Wert zuzuweisen, der als Array-Index dienen kann. Wir nennen diesen Wert einen Hash-Wert oder einfach einen Hash .

3. Hashing

Hashing ist eine Umwandlung eines Objekts in einen numerischen Wert . Funktionen, die diese Transformationen ausführen, werden als Hash-Funktionen bezeichnet .

Aus Gründen der Einfachheit, lassen Sie sich betrachten Hash - Funktionen , die Strings in Array - Indizes - Transformation, die in ganzen Zahlen aus dem Bereich [0, N] mit einer endlichen N .

Natürlich wird eine Hash-Funktion auf eine Vielzahl von Zeichenfolgen angewendet . Daher werden seine „globalen“ Eigenschaften wichtig.

Leider ist es nicht möglich, dass eine Hash-Funktion immer unterschiedliche Zeichenfolgen in unterschiedliche Zahlen umwandelt .

Wir können uns leicht davon überzeugen, dass die Anzahl der Zeichenfolgen viel größer ist als die Anzahl der Ganzzahlen in einem beliebigen Bereich [0, N] . Daher ist es unvermeidlich, dass es ein Paar ungleicher Zeichenfolgen gibt, für die eine Hash-Funktion gleiche Werte erzeugt. Dieses Phänomen nennt man Kollision .

Wir werden nicht auf die technischen Details hinter den Hash-Funktionen eingehen, aber es ist klar, dass eine gute Hash-Funktion versuchen sollte, die Zeichenfolgen, auf denen sie definiert ist, einheitlich in Zahlen abzubilden.

Eine weitere offensichtliche Anforderung ist, dass eine gute Hash-Funktion schnell sein sollte. Wenn die Berechnung eines Hashwerts zu lange dauert, können wir nicht schnell auf Elemente zugreifen.

In diesem Tutorial betrachten wir eine der Techniken, mit denen versucht wird, das Mapping zu vereinheitlichen und gleichzeitig schnell zu halten.

4. Falttechnik

Unser Ziel ist es, eine Funktion zu finden, die Zeichenfolgen in Array-Indizes umwandelt. Nehmen wir zur Veranschaulichung der Idee an, dass dieses Array die Kapazität für 105 Elemente haben soll, und verwenden wir als Beispiel die Java-Sprache für Zeichenfolgen .

4.1. Beschreibung

Beginnen wir mit der Umwandlung der Zeichen der Zeichenfolge in Zahlen. ASCII ist ein guter Kandidat für diese Operation:

Jetzt ordnen wir die Zahlen, die wir gerade erhalten haben, in Gruppen von einiger Größe an. Im Allgemeinen wählen wir den Gruppengrößenwert basierend auf der Größe unseres Arrays von 105. Da die Zahlen, in die wir die Zeichen transformiert haben, ohne Verlust der Allgemeinheit zwei bis drei Ziffern enthalten, können wir die Gruppengröße auf einstellen zwei:

Der nächste Schritt besteht darin, die Zahlen in jeder Gruppe so zu verketten, als wären sie Zeichenfolgen, und ihre Summe zu finden:

Jetzt müssen wir den letzten Schritt machen. Lassen Sie uns prüfen, ob die Zahl 348933 als Index für unser Array der Größe 105 dienen kann. Natürlich überschreitet sie den maximal zulässigen Wert 99999. Wir können dieses Problem leicht überwinden, indem wir den Modulo-Operator anwenden, um das Endergebnis zu finden:

348933 % 10000 = 48933

4.2. Schlussbemerkungen

Wir sehen, dass der Algorithmus keine zeitaufwändigen Operationen enthält und daher ziemlich schnell ist. Jedes Zeichen der Eingabezeichenfolge trägt zum Endergebnis bei. Diese Tatsache hilft definitiv dabei, Kollisionen zu reduzieren, aber nicht vollständig zu vermeiden.

Wenn wir beispielsweise die Faltung überspringen und den Modulo-Operator direkt auf die ASCII-transformierte Eingabezeichenfolge anwenden wollten (ohne das Überlaufproblem zu beachten)

749711897321089711010311797103101 % 100000 = 3101

Dann würde eine solche Hash-Funktion den gleichen Wert für alle Zeichenfolgen erzeugen, die dieselben letzten beiden Zeichen wie unsere Eingabezeichenfolge haben: a ge , p age , lar ge und so weiter.

Aus der Beschreibung des Algorithmus können wir leicht erkennen, dass er nicht frei von Kollisionen ist. Zum Beispiel erzeugt der Algorithmus den gleichen Hash - Wert für Java - Sprache und Vaja Sprache Strings .

5. Andere Techniken

Die Falttechnik ist weit verbreitet, aber nicht die einzige. Manchmal können auch die Binning- oder Mid-Square- Techniken nützlich sein.

Wir veranschaulichen ihre Idee, indem wir keine Zeichenfolgen, sondern Zahlen verwenden (nehmen wir an, wir haben die Zeichenfolgen bereits irgendwie in Zahlen umgewandelt). Wir werden ihre Vor- und Nachteile nicht diskutieren, aber Sie können sich eine Meinung bilden, nachdem Sie die Algorithmen gesehen haben.

5.1. Binning-Technik

Angenommen, wir haben 100 Ganzzahlen und möchten, dass unsere Hash-Funktion sie einem Array von 10 Elementen zuordnet. Dann können wir diese 100 Ganzzahlen einfach so in zehn Gruppen einordnen, dass die ersten zehn Ganzzahlen im ersten Fach, die zweiten zehn Ganzzahlen im zweiten Fach usw. enden.

5.2. Mid-Square-Technik

Dieser Algorithmus wurde von John von Neumann vorgeschlagen und ermöglicht es uns, Pseudozufallszahlen ausgehend von einer bestimmten Zahl zu generieren.

Lassen Sie es uns an einem konkreten Beispiel veranschaulichen. Angenommen, wir haben eine vierstellige Nummer 1111 . Nach dem Algorithmus quadrieren wir es und erhalten so 1234321 . Jetzt extrahieren wir vier Ziffern aus der Mitte, zum Beispiel 2343 . Der Algorithmus ermöglicht es uns, diesen Vorgang zu wiederholen, bis wir mit dem Ergebnis zufrieden sind.

6. Fazit

In diesem Tutorial haben wir verschiedene Hashing-Techniken betrachtet. Wir haben die Falttechnik ausführlich beschrieben und kurz beschrieben, wie Binning und Mid-Square erreicht werden können.

Wie immer finden wir möglicherweise die entsprechenden Codefragmente in unserem GitHub-Repository.