Dieser Artikel vermittelt Ihnen relevantes Wissen über Javascript. Er stellt hauptsächlich die damit verbundenen Probleme zur Implementierung von Hash-Tabellen vor. Die gesamte Struktur des Arrays, in das die endgültigen Daten eingefügt werden, und das Ergebnis ist die Hash-Tabelle. hoffe es hilft allen.
Verwandte Empfehlungen: Javascript-Lerntutorial
Hash-Tabellen werden normalerweise basierend auf Arrays implementiert, aber im Vergleich zu Arrays hat es viele Vorteile:
- Es kann ein sehr schnelles Einfügen ermöglichen – Lösch-Suche Operationen
- Egal wie viele Daten vorhanden sind, das Einfügen und Löschen erfordert nahezu konstante Zeit: das heißt O(1)-Zeitniveau. Tatsächlich sind dafür nur wenige Maschinenanweisungen erforderlich.
- Hash-Tabellen sind schneller als Bäume, und Sie können die gewünschten Elemente grundsätzlich sofort finden.
- Hash-Tabellen sind viel einfacher zu programmieren als Bäume Die Hash-Tabelle ist nicht in Ordnung, daher können die Elemente nicht auf feste Weise durchlaufen werden
Normalerweise dürfen die Schlüssel in der Hash-Tabelle nicht wiederholt werden, und dieselben Schlüssel können nicht als Schlüssel platziert werden, der zum Speichern verschiedener Elemente verwendet wird
Die Speicherplatznutzung ist nicht hoch, die unterste Ebene verwendet Arrays und einige Zellen werden nicht verwendet
- Was ist eine Hash-Tabelle?
-
- Hash-Tabellen sind nicht leicht zu verstehen, im Gegensatz zu Arrays, verknüpften Listen und Bäumen, die ihre Struktur und Prinzipien in Form von Grafiken ausdrücken können.
Die Struktur der Hash-Tabelle ist
Array, aber ihre Magie liegt in einer Transformation des
Indexwerts. Diese Transformation kann als
Hash-Funktion- bezeichnet werden, die über die Hash-Funktion
HashCode- erhalten werden kann. Einige Konzepte von Hash-Tabellen
Hashifizierung:
Der Prozess der Umwandlung von
großen Zahlen in Indizes innerhalb des Array-Bereichs
wird
Hashing- genannt; ha Hash-Funktion: Wir konvertieren normalerweise Wörter in große Zahlen und fügen Sie die Code-Implementierung des
Hashing- großer Zahlen in eine Funktion ein, die Hash-Funktion genannt wird; Hash-Tabelle: Kapseln Sie die gesamte Struktur in das Array in die die endgültigen Daten eingefügt werden und das Ergebnis eine Hash-Tabelle
ist. -
Probleme, die noch gelöst werden müssen: Der gehashte Index ist immer noch möglich duplizieren
Wie kann dieses Problem gelöst werden? Diese Situation nennt man
Konflikt
, Konflikt ist unvermeidlich, wir können nur
den Konflikt lösen
. -
Methoden zur KonfliktlösungZwei gängige Lösungen zur Konfliktlösung:
Option 1:
Kettenadressenmethode
(
Zip-Methode
);
Wie in der Abbildung unten gezeigt, werden wir jede Nummer Die Restoperation wird für
10- ausgeführt und der Bereich des Restes 0~9 wird als Indexwert des Arrays verwendet. Darüber hinaus speichert die Position, die jedem Indexwert im Array entspricht, nicht mehr eine Zahl, sondern ein Array oder eine
verknüpfte Liste
bestehend aus Zahlen mit demselben Rest nach einer Restoperation.
Zusammenfassung: Die Möglichkeit, Konflikte mit der Kettenadressmethode zu lösen, besteht darin, dass jede Array-Einheit nicht mehr
einzelne Daten
speichert, sondern eine Kette
. Die häufig verwendete Datenstruktur für diese Kette ist
Array oder verknüpfte Liste, die beiden Datenstrukturen sind bei der Suche gleichermaßen effizient (da die Kette im Allgemeinen nicht zu viele Elemente enthält). Option 2: Methode der offenen Adresse; Die Hauptarbeitsmethode der Methode der offenen Adresse besteht darin, leere Zellen zu finden
, um
widersprüchliche - Datenelemente zu platzieren.
Entsprechend den verschiedenen Methoden zur Erkennung der Position leerer Zellen kann sie in drei Methoden unterteilt werden: Lineare Erkennung
Sekundäre Erkennung
- Rehash-Methode
- Du kannst siehe Mit zunehmendem Füllfaktor nimmt die durchschnittliche Erkennungslänge linear und sanft zu. Die Kettenadressmethode wird häufig in der Entwicklung verwendet. Beispielsweise wird die Kettenadressmethode in HashMap in Java verwendet.
- Ausgezeichnete Hash-FunktionDer Vorteil einer Hash-Tabelle ist ihre Geschwindigkeit, sodass die Hash-Funktion keine komplexen Algorithmen verwenden kann, die viel Leistung verbrauchen. Eine Möglichkeit, die Geschwindigkeit zu verbessern, besteht darin,
Multiplikationen und Divisionen
in der Hash-Funktion zu minimieren.
Eine leistungsstarke Hash-Funktion sollte die folgenden zwei Vorteile haben:
-
Schnelle Berechnung;
- Schnelle Berechnung
Horners Gesetz wird in China auch
Qin Jius Algorithmus genannt
Wann Um den Wert eines Polynoms zu ermitteln, berechnen Sie zunächst den Wert des linearen Polynoms in der innersten Klammer und berechnen Sie dann den Wert des linearen Polynoms Schicht für Schicht von innen nach außen. Dieser Algorithmus wandelt den Wert des Polynoms f(x) n-Grades in den Wert von Polynomen n-Grads um.
Vor der Transformation:
Anzahl der Multiplikationen: n (n+1)/2-mal;
Anzahl der Additionen: n-mal;
Nach der Transformation:
-
- Anzahl der Multiplikationen: n-mal ;
Anzahl der Additionen: n-mal;
Wenn großes O zur Darstellung der Zeitkomplexität verwendet wird, wird es direkt von
O(N2)
vor der Transformation auf - O(N)
reduziert. - Gleichmäßige Verteilung
Um sicherzustellen, dass die Daten gleichmäßig in der Hash-Tabelle verteilt sind, wenn wir Konstanten verwenden müssen, versuchen Sie,
Primzahlen
zu verwenden: die Länge der Hash-Tabelle; die Basis der N-ten Potenz usw.
HashMap in Java verwendet die Kettenadressmethode und die für das Hashing verwendete Formel lautet: index = HashCode (Schlüssel) & (Länge-1) Das heißt, die Daten werden für - und -Operationen in Binärdateien konvertiert. und es handelt sich nicht um eine Restoperation. Auf diese Weise verarbeitet der Computer direkt Binärdaten, was effizienter ist. Bei der Ausführung von
- und
-Operationen, die als Big Data bezeichnet werden, treten jedoch Probleme bei JavaScript auf, sodass die Restoperation weiterhin verwendet wird, wenn JavaScript zum Implementieren von Hashing verwendet wird. function HashTable() {
// 存放相关的元素
this.storage = [];
// 存了多少数据
this.count = 0;
// 用于标记数组中一共存放了多少个元素
this.limit = 7;
/*
设计哈希函数
①将字符串转成比较大的数字
②将大的数字hashCode压缩到数组范围之内
*/
HashTable.prototype.hashFunction = function (str, size) {
var hashCode = 0;
//秦九韶算法（霍纳算法）
// 哈希表的长度、N次幂的底数等尽量选取质数
for (var i = 0; i this.limit * 0.75) {
var newLimit = this.limit * 2;
var prime = this.getPrime(newLimit);
this.resize(prime);
}
};
// 获取
HashTable.prototype.get = function (key) {
var index = this.hashFunction(key, this.limit);
var bucket = this.storage[index];
if (bucket == null) return null;
for (var i = 0; i 7 && this.count 0 ? false : true;
};
// size
HashTable.prototype.size = function () {
return this.count;
};
// toString
HashTable.prototype.toString = function () {
var str = '';
for (var i = 0; i Nach dem Login kopieren
Verwandte Empfehlungen: Javascript-Lerntutorial
Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in die Implementierung von Hash-Tabellen durch JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
