Hashtables bieten eine nützliche Möglichkeit, die Anwendungsleistung zu optimieren.
Hashtables sind kein neues Konzept im Computerbereich. Sie wurden entwickelt, um die Computerverarbeitung zu beschleunigen, die nach heutigen Maßstäben sehr langsam ist, und ermöglichen es Ihnen, bei der Abfrage vieler Dateneinträge schnell einen bestimmten Eintrag zu finden. Obwohl moderne Maschinen tausende Male schneller sind, sind Hashtabellen immer noch ein nützliches Werkzeug, um die beste Leistung aus Ihren Anwendungen herauszuholen.
Stellen Sie sich vor, Sie haben eine Datendatei mit etwa tausend Datensätzen – beispielsweise Kundendaten eines Kleinunternehmens – und ein Programm, das die Datensätze zur Verarbeitung in den Speicher einliest. Jeder Datensatz enthält eine eindeutige fünfstellige Kunden-ID-Nummer, Kundennamen, Adresse, Kontostand usw. Gehen Sie davon aus, dass die Datensätze nicht nach Kunden-ID-Nummer sortiert sind. Wenn das Programm daher die Kundennummer als „Schlüssel“ zum Auffinden eines bestimmten Kundendatensatzes verwenden möchte, besteht die einzige Möglichkeit, ihn zu finden, darin, jeden Datensatz nacheinander zu durchsuchen. Manchmal findet es den benötigten Datensatz schnell; manchmal hat das Programm jedoch schon fast nach dem letzten Datensatz gesucht, bevor er den benötigten Datensatz findet. Wenn Sie 1.000 Datensätze durchsuchen möchten, muss das Programm zum Finden eines Datensatzes durchschnittlich 500,5 ((1000 + 1)/2) Datensätze überprüfen. Wenn Sie häufig Daten nachschlagen müssen, benötigen Sie möglicherweise eine schnellere Möglichkeit, einen Datensatz zu finden.
Eine Möglichkeit, Ihre Suche zu beschleunigen, besteht darin, die Datensätze in Teile aufzuteilen, sodass Sie statt einer großen Liste mehrere kurze Listen durchsuchen. Für unsere numerischen Kunden-ID-Nummern können Sie 10 Listen erstellen – eine Liste für ID-Nummern, die mit 0 beginnen, eine Liste für ID-Nummern, die mit 1 beginnen, und so weiter. Um die Kunden-ID-Nummer 38016 zu finden, müssen Sie also nur die Liste beginnend mit 3 durchsuchen. Wenn 1.000 Datensätze vorhanden sind und die durchschnittliche Länge jeder Liste 100 beträgt (1.000 Datensätze aufgeteilt in 10 Listen), sinkt die durchschnittliche Anzahl der Vergleiche zur Suche nach einem Datensatz auf etwa 50 (siehe Abbildung 1).
Wenn etwa jede zehnte Kundennummer mit einer 0 beginnt, ein weiteres Zehntel mit einer 1 usw., dann würde dieser Ansatz natürlich gut funktionieren. Wenn 90 % der Kundennummern mit 0 beginnen würden, hätte diese Liste 900 Datensätze, was durchschnittlich 450 Vergleiche pro Suche erfordern würde. Darüber hinaus beziehen sich 90 % der Suchvorgänge, die das Programm durchführen muss, auf Zahlen, die mit 0 beginnen. Daher liegt die durchschnittliche Vergleichszahl weit außerhalb des Rahmens einfacher mathematischer Operationen.
Es wäre besser, wenn wir die Datensätze in unseren Listen so verteilen könnten, dass jede Liste ungefähr die gleichen Einträge hat, unabhängig von der Zahlenverteilung in den Schlüsselwerten. Wir brauchen eine Möglichkeit, die Kundenzahlen zusammenzuführen und die Ergebnisse besser zu verteilen. Beispielsweise könnten wir jede Ziffer der Zahl nehmen, sie mit einer großen Zahl multiplizieren (die je nach Position der Ziffer variiert), die Ergebnisse addieren, um eine Summe zu erhalten, diese Zahl durch 10 dividieren und den Rest als Index angeben Wert (Index). Wenn ein Datensatz eingelesen wird, führt das Programm diese Hash-Funktion für die Kundennummer aus, um festzustellen, zu welcher Liste der Datensatz gehört. Wenn der Benutzer eine Abfrage durchführen muss, wird dieselbe Hash-Funktion als „Schlüssel“ für die Kundennummer verwendet, damit die richtige Liste durchsucht werden kann. Eine solche Datenstruktur wird als Hashtabelle bezeichnet.
Hashtables in Java
Java enthält zwei Klassen, java.util.Hashtable und java.util.HashMap , die einen vielseitigen Hashtable-Mechanismus bereitstellen. Die beiden Klassen sind sehr ähnlich und stellen im Allgemeinen dieselbe öffentliche Schnittstelle bereit. Sie weisen jedoch einige wichtige Unterschiede auf, auf die ich später eingehen werde.
Mit den Objekten Hashtable und HashMap können Sie einen Schlüssel und einen Wert kombinieren und das Schlüssel/Wert-Paar mithilfe der Methode put () in die Tabelle eingeben. Anschließend können Sie den Wert abrufen, indem Sie die Methode get() aufrufen und den Schlüssel als Parameter übergeben. Schlüssel und Wert können beliebige Objekte sein, solange sie zwei Grundanforderungen erfüllen. Beachten Sie, dass primitive Typen mithilfe von Methoden wie Integer (int) in Objekte konvertiert werden müssen, da Schlüssel und Werte Objekte sein müssen.
Um ein Objekt einer bestimmten Klasse als Schlüssel zu verwenden, muss die Klasse zwei Methoden bereitstellen: equal() und hashCode(). Diese beiden Methoden sind in java.lang.Object enthalten, sodass alle Klassen diese beiden Methoden erben können. Die Implementierung dieser beiden Methoden in der Object-Klasse ist jedoch im Allgemeinen nutzlos, sodass Sie diese beiden Methoden normalerweise selbst überladen müssen.
Die Equals()-Methode vergleicht ihr Objekt mit einem anderen Objekt und gibt true zurück, wenn die beiden Objekte dieselben Informationen darstellen. Diese Methode stellt außerdem sicher, dass beide Objekte derselben Klasse angehören. Object.equals() gibt true zurück, wenn die beiden Referenzobjekte identische Objekte sind, was erklärt, warum diese Methode im Allgemeinen nicht gut passt. In den meisten Fällen benötigen Sie eine Möglichkeit, Feld für Feld zu vergleichen, daher betrachten wir verschiedene Objekte, die dieselben Daten darstellen, als gleich.
Die HashCode()-Methode generiert einen int-Wert, indem sie eine Hash-Funktion unter Verwendung des Objektinhalts ausführt. Hashtable und HashMap verwenden diesen Wert, um herauszufinden, in welchem Bucket (oder welcher Liste) sich ein Schlüssel/Wert-Paar befindet.
Als Beispiel können wir uns die String-Klasse ansehen, da sie über eigene Methoden verfügt, die diese beiden Methoden implementieren. String.equals() vergleicht zwei String-Objekte Zeichen für Zeichen und gibt true zurück, wenn die Strings gleich sind:
Kopieren Sie den Codecode wie folgt:
String myName = "Einstein";
// Der folgende Test ist
// immer wahr
if ( myName.equals("Einstein") )
{ ...
String.hashCode() führt eine Hash-Funktion für einen String aus. Der numerische Code jedes Zeichens in der Zeichenfolge wird mit 31 multipliziert und das Ergebnis hängt von der Position des Zeichens in der Zeichenfolge ab. Die Ergebnisse dieser Berechnungen werden dann zu einer Gesamtsumme addiert. Dieser Prozess mag kompliziert erscheinen, sorgt aber für eine bessere Werteverteilung. Es zeigt auch, wie weit Sie bei der Entwicklung Ihrer eigenen hashCode()-Methode gehen können, in der Gewissheit, dass das Ergebnis einzigartig ist.
Angenommen, ich möchte eine Hashtabelle verwenden, um einen Buchkatalog zu implementieren, und die ISBN-Nummer des Buchs als Suchschlüssel für die Suche verwenden. Ich kann die String-Klasse verwenden, um die Details zu übertragen und die Methoden equal() und hashCode() bereitzuhalten (siehe Listing 1). Mit der put ()-Methode können wir Schlüssel/Wert-Paare zur Hashtabelle hinzufügen (siehe Listing 2).
Die Put ()-Methode akzeptiert zwei Parameter, die beide vom Typ Object sind. Der erste Parameter ist der Schlüssel; der zweite Parameter ist der Wert. Die Put ()-Methode ruft die hashCode()-Methode des Schlüssels auf und dividiert das Ergebnis durch die Anzahl der Listen in der Tabelle. Verwenden Sie den Rest als Indexwert, um zu bestimmen, zu welcher Liste der Datensatz hinzugefügt wird. Beachten Sie, dass der Schlüssel in der Tabelle eindeutig ist. Wenn Sie put () mit einem vorhandenen Schlüssel aufrufen, wird der übereinstimmende Eintrag so geändert, dass er auf einen neuen Wert verweist, und der alte Wert wird zurückgegeben (Wenn der Schlüssel nicht in der Tabelle vorhanden ist , put () gibt einen Nullwert zurück).
Um einen Wert aus der Tabelle zu lesen, verwenden wir den Suchschlüssel mit der Methode get(). Es gibt eine Objektreferenz zurück, die in den richtigen Typ konvertiert wurde:
Kopieren Sie den Codecode wie folgt:
BookRecord br =
(BookRecord)isbnTable.get(
„0-345-40946-9“);
System.out.println(
"Autor: " + Br.Autor
+ " Titel: " + br.title);
Eine weitere nützliche Methode ist „remove()“, die fast genauso verwendet wird wie „get()“. Sie entfernt den Eintrag aus der Tabelle und gibt ihn an das aufrufende Programm zurück.
Deine eigene Klasse
Wenn Sie einen primitiven Typ als Schlüssel verwenden möchten, müssen Sie ein Objekt desselben Typs erstellen. Wenn Sie beispielsweise einen Ganzzahlschlüssel verwenden möchten, sollten Sie den Konstruktor Integer(int) verwenden, um ein Objekt aus einer Ganzzahl zu generieren. Alle Wrapper-Klassen wie Integer, Float und Boolean behandeln primitive Werte als Objekte und überladen die Methoden equal() und hashCode(), sodass sie als Schlüssel verwendet werden können. Viele andere im JDK bereitgestellte Klassen sind so (sogar die Klassen Hashtable und HashMap implementieren ihre eigenen Methoden equal() und hashCode()), aber Sie sollten die Dokumentation überprüfen, bevor Sie Objekte einer Klasse als Hashtable-Schlüssel verwenden. Es ist auch notwendig, die Quelle der Klasse zu überprüfen, um zu sehen, wie equal() und hashCode() implementiert sind. Beispielsweise geben „Byte“, „Zeichen“, „Kurz“ und „Ganzzahl“ alle den dargestellten Ganzzahlwert als Hash-Code zurück. Dies kann Ihren Anforderungen entsprechen oder auch nicht.
Verwendung von Hashtables in Java
Wenn Sie eine Hashtabelle erstellen möchten, die Objekte einer von Ihnen definierten Klasse als Schlüssel verwendet, sollten Sie sicherstellen, dass die Methoden equal() und hashCode() dieser Klasse nützliche Werte liefern. Schauen Sie sich zunächst die Klasse an, die Sie erweitern, um festzustellen, ob ihre Implementierung Ihren Anforderungen entspricht. Wenn nicht, sollten Sie die Methode überladen.
Die grundlegende Designbeschränkung jeder equal()-Methode besteht darin, dass sie true zurückgeben sollte, wenn das an sie übergebene Objekt zur selben Klasse gehört und ihre Datenfelder auf Werte gesetzt sind, die dieselben Daten darstellen. Sie sollten außerdem sicherstellen, dass Ihr Code zurückkehrt, wenn Sie der Methode ein leeres Argument übergeben
Kopieren Sie den Codecode wie folgt:
false:öffentlicher boolescher Wert gleicht (Objekt o)
{
if ( (o == null)
||. !(o Instanz von myClass))
{
return false;
}
// Jetzt Datenfelder vergleichen...
Darüber hinaus gibt es einige Regeln, die Sie beim Entwerfen einer hashCode()-Methode beachten sollten. Erstens muss die Methode denselben Wert für ein bestimmtes Objekt zurückgeben, unabhängig davon, wie oft die Methode aufgerufen wird (natürlich solange sich der Inhalt des Objekts zwischen den Aufrufen nicht ändert). Wenn ein Objekt als Hashtabellenschlüssel verwendet wird, sollte dies der Fall sein vermieden werden). Zweitens: Wenn zwei durch Ihre Methode equal() definierte Objekte gleich sind, müssen sie auch denselben Hash-Code generieren. Drittens, und das ist eher eine Richtlinie als ein Prinzip, sollten Sie versuchen, Ihre Methode so zu gestalten, dass sie für verschiedene Objektinhalte unterschiedliche Ergebnisse liefert. Es spielt keine Rolle, wenn gelegentlich verschiedene Objekte denselben Hash-Code generieren. Wenn die Methode jedoch nur Werte im Bereich von 1 bis 10 zurückgeben kann, dann können nur 10 Listen verwendet werden, unabhängig davon, wie viele Listen in der Hashtabelle enthalten sind.
Ein weiterer Faktor, den Sie beim Entwerfen von equal() und hashCode() berücksichtigen sollten, ist die Leistung. Bei jedem Aufruf von put () oder get() wird hashCode() aufgerufen, um die richtige Liste zu finden. Wenn get() die Liste nach dem Schlüssel durchsucht, ruft es equal() für jedes Element in der Liste auf. Implementieren Sie diese Methoden so, dass sie so schnell und effizient wie möglich ausgeführt werden, insbesondere wenn Sie planen, Ihre Klasse öffentlich verfügbar zu machen, da andere Benutzer Ihre Klasse möglicherweise in einer Hochleistungsanwendung verwenden möchten, bei der die Ausführungsgeschwindigkeit wichtig ist.
Hashtable-Leistung
Der Hauptfaktor, der die Effizienz von Hashtable beeinflusst, ist die durchschnittliche Länge der Listen in der Tabelle, da die durchschnittliche Suchzeit direkt mit dieser durchschnittlichen Länge zusammenhängt. Um die durchschnittliche Länge zu reduzieren, müssen Sie natürlich die Anzahl der Listen in der Hashtabelle erhöhen. Die beste Sucheffizienz erzielen Sie, wenn die Anzahl der Listen so groß ist, dass die meisten oder alle Listen nur einen Datensatz enthalten. Dies geht jedoch möglicherweise zu weit. Wenn Ihre Hashtabelle weitaus mehr Listen als Dateneinträge enthält, müssen Sie keinen solchen Speicheraufwand verursachen, und in manchen Fällen ist es für die Leute unmöglich, diesen Ansatz zu akzeptieren.
In unserem vorherigen Beispiel wussten wir im Voraus, wie viele Datensätze wir hatten, 1.000. Mit diesem Wissen können wir entscheiden, wie viele Listen unsere Hashtabelle enthalten soll, um den besten Kompromiss zwischen Suchgeschwindigkeit und Speichernutzungseffizienz zu erzielen. In vielen Fällen wissen Sie jedoch nicht im Voraus, wie viele Datensätze Sie verarbeiten werden; die Datei, aus der die Daten gelesen werden, kann kontinuierlich wachsen oder die Anzahl der Datensätze kann sich von Tag zu Tag erheblich ändern.
Die Klassen Hashtable und HashMap lösen dieses Problem, indem sie die Tabelle beim Hinzufügen von Einträgen dynamisch erweitern. Beide Klassen verfügen über Konstruktoren, die die anfängliche Anzahl von Listen in der Tabelle und einen Ladefaktor als Parameter akzeptieren:
öffentliche Hashtabelle(
int initialCapacity,
float LoadFactor)
öffentliche HashMap(
int initialCapacity,
float LoadFactor)
Multiplizieren Sie diese beiden Zahlen, um einen kritischen Wert zu berechnen. Jedes Mal, wenn ein neuer Eintrag zur Hash-Tabelle hinzugefügt wird, wird die Zählung aktualisiert, und wenn die Zählung einen kritischen Wert überschreitet, wird die Tabelle zurückgesetzt (Rehash). (Die Listengröße wird auf das Doppelte der vorherigen Größe plus 1 erhöht und alle Einträge werden in die richtige Liste verschoben.) Der Standardkonstruktor legt die Anfangskapazität auf 11 und den Auslastungsfaktor auf 0,75 fest, sodass der kritische Wert 8 ist. Wenn der Tabelle der neunte Datensatz hinzugefügt wird, wird die Hash-Tabelle neu skaliert, sodass sie 23 Listen enthält und der neue kritische Wert 17 ist (der ganzzahlige Teil von 23*0,75). Sie können sehen, dass der Auslastungsfaktor eine Obergrenze für die durchschnittliche Anzahl von Listen in einer Hash-Tabelle darstellt, was bedeutet, dass eine Hash-Tabelle standardmäßig selten viele Listen enthält, die mehr als einen Datensatz enthalten. Vergleichen Sie unser ursprüngliches Beispiel, in dem wir 1.000 Datensätze auf 10 Listen verteilt hatten. Wenn wir die Standardwerte verwenden, wird diese Tabelle erweitert und enthält mehr als 1.500 Listen. Aber Sie können das kontrollieren. Wenn die Anzahl der Listen multipliziert mit dem Auslastungsfaktor größer ist als die Anzahl der von Ihnen verarbeiteten Einträge, wird die Tabelle nie neu erstellt, sodass wir dem folgenden Beispiel folgen können:
Kopieren Sie den Codecode wie folgt:
// Die Tabelle wird erst erneut aufgewärmt
// hat 1.100 Einträge (10*110):
Hashtable myHashTable =
neue Hashtable(10, 110.0F);
Sie möchten dies wahrscheinlich nicht tun, es sei denn, Sie möchten keinen Speicher für leere Listen sparen und haben nichts gegen die zusätzliche Suchzeit, was in eingebetteten Systemen der Fall sein kann. Dieser Ansatz kann jedoch nützlich sein, da das Zurücksetzen rechenintensiv ist und dieser Ansatz gewährleistet, dass es nie zu einem Zurücksetzen kommt.
Beachten Sie, dass der Aufruf von put () zwar dazu führen kann, dass die Tabelle wächst (die Anzahl der Listen erhöht), der Aufruf von remove() jedoch nicht den gegenteiligen Effekt hat. Wenn Sie also eine große Tabelle haben und die meisten Einträge daraus löschen, erhalten Sie am Ende eine große, aber größtenteils leere Tabelle.
Hashtable und HashMap
Es gibt drei wichtige Unterschiede zwischen den Klassen Hashtable und HashMap. Der erste Unterschied ist hauptsächlich auf historische Gründe zurückzuführen. Hashtable basiert auf der alten Dictionary-Klasse und HashMap ist eine Implementierung der in Java 1.2 eingeführten Map- Schnittstelle.
Der vielleicht wichtigste Unterschied besteht darin, dass die Methoden von Hashtable synchron sind, die Methoden von HashMap hingegen nicht. Dies bedeutet, dass Sie, obwohl Sie eine Hashtable in einer Multithread-Anwendung verwenden können, ohne besondere Maßnahmen ergreifen zu müssen, in ähnlicher Weise eine externe Synchronisierung für eine HashMap bereitstellen müssen. Eine praktische Methode ist die Verwendung der statischen synchronisiertMap()-Methode der Collections-Klasse, die ein threadsicheres Map- Objekt erstellt und es als gekapseltes Objekt zurückgibt. Mit den Methoden dieses Objekts können Sie synchron auf die zugrunde liegende HashMap zugreifen. Dies hat zur Folge, dass Sie die Synchronisierung in der Hashtable nicht abbrechen können, wenn Sie sie nicht benötigen (z. B. in einer Single-Thread-Anwendung) und die Synchronisierung einen hohen Verarbeitungsaufwand verursacht.
Der dritte Unterschied besteht darin, dass Sie nur mit HashMap Nullwerte als Schlüssel oder Wert eines Tabelleneintrags verwenden können. Nur ein Datensatz in einer HashMap kann ein leerer Schlüssel sein, aber eine beliebige Anzahl von Einträgen kann ein leerer Wert sein. Dies bedeutet, dass get() null zurückgibt, wenn der Suchschlüssel nicht in der Tabelle gefunden wird oder wenn der Suchschlüssel gefunden wird, aber ein Nullwert ist. Verwenden Sie bei Bedarf die Methode „containKey()“, um zwischen den beiden Situationen zu unterscheiden.
Einige Informationen deuten darauf hin, dass Hashtable verwendet werden sollte, wenn eine Synchronisierung erforderlich ist, andernfalls HashMap. Da HashMap jedoch bei Bedarf synchronisiert werden kann, HashMap mehr Funktionen als Hashtable hat und nicht auf einer alten Klasse basiert, denken einige Leute, dass HashMap in verschiedenen Situationen HashMap vorgezogen wird.
Über Immobilien
Manchmal möchten Sie möglicherweise eine Hashtabelle verwenden, um Schlüsselzeichenfolgen Wertzeichenfolgen zuzuordnen. Es gibt einige Beispiele für Umgebungszeichenfolgen in DOS, Windows und Unix. Beispielsweise wird die Schlüsselzeichenfolge PATH der Wertezeichenfolge C:/WINDOWS;C:/WINDOWS/SYSTEM zugeordnet. Hashtables sind eine einfache Möglichkeit, diese darzustellen, aber Java bietet eine andere Möglichkeit.
Die Java- Klasse .util.Properties ist eine Unterklasse von Hashtable, die für die Verwendung mit String-Schlüsseln und -Werten entwickelt wurde. Die Verwendung des Properties-Objekts ähnelt der Verwendung von Hashtable, die Klasse fügt jedoch zwei zeitsparende Methoden hinzu, die Sie kennen sollten.
Die Store()-Methode speichert den Inhalt eines Properties-Objekts in lesbarer Form in einer Datei. Die Load()-Methode ist genau das Gegenteil. Sie wird verwendet, um die Datei zu lesen und das Properties-Objekt so festzulegen, dass es Schlüssel und Werte enthält.
Beachten Sie, dass Sie, da Properties Hashtable erweitert, die put ()-Methode der Oberklasse verwenden können, um Schlüssel und Werte hinzuzufügen, die keine String-Objekte sind. Dies ist nicht ratsam. Wenn Sie außerdem store() mit einem Properties-Objekt verwenden, das kein String-Objekt enthält, schlägt store() fehl. Als Alternative zu put () und get() sollten Sie setProperty() und getProperty() verwenden, die String-Parameter verwenden.
Okay, ich hoffe, Sie wissen jetzt, wie Sie Hashtabellen verwenden, um Ihre Verarbeitung zu beschleunigen