Was ist Javascript-Hash?

In JavaScript bezieht sich Hash auf eine Hash-Tabelle, bei der es sich um eine Datenstruktur handelt, die basierend auf Schlüsselwörtern direkt auf den Speicherort zugreift. Über die Hash-Tabelle wird eine bestimmte Beziehung zwischen dem Speicherort des Datenelements und dem Schlüsselwort hergestellt Das Datenelement ist eine entsprechende Beziehung und die Funktion, die diese entsprechende Beziehung herstellt, wird als Hash-Funktion bezeichnet.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, JavaScript-Version 1.8.5, Dell G3-Computer.

Grundkonzept von Javascript-Hash:

Hash-Tabelle (Hash-Tabelle) ist eine Datenstruktur, die anhand von Schlüsselwörtern, dem Speicherort der Datenelemente und dem Speicherort direkt auf den Speicherort zugreift der Datenelemente Es wird eine bestimmte Entsprechung zwischen Schlüsselwörtern hergestellt, und die Funktion, die diese Entsprechung herstellt, wird Hash-Funktion genannt.

So erstellen Sie eine Hash-Tabelle:

Nehmen Sie an, dass die Anzahl der zu speichernden Datenelemente n beträgt, legen Sie eine kontinuierliche Speichereinheit mit einer Länge von m (m > n) fest und verwenden Sie für jedes das Schlüsselwort Ki ( Datenelement) 0

Aus mathematischer Sicht handelt es sich bei der Hash-Funktion tatsächlich um eine Zuordnung von Schlüsselwörtern zu Speichereinheiten. Daher hoffen wir, dass die von der Hash-Funktion berechnete Huaxi-Adresse durch eine möglichst einfache Operation einem Ort zugeordnet werden kann In einer Reihe von Speichereinheiten gibt es drei Schlüsselpunkte beim Aufbau einer Hash-Funktion: (1) Der Operationsprozess sollte so einfach und effizient wie möglich sein, um die Einfügungs- und Abrufeffizienz der Hash-Tabelle zu verbessern Die Funktion sollte einen guten Hash-Typ haben. Um die Wahrscheinlichkeit einer Hash-Kollision zu verringern, sollte die Hash-Funktion drittens eine stärkere Komprimierung aufweisen, um Speicher zu sparen.

Häufig verwendete Methoden:

• Direkte Adressmethode: Verwenden Sie einen bestimmten linearen Funktionswert des Schlüsselworts als Hash-Adresse, der als Hash (K) = aK + C ausgedrückt werden kann. Der Vorteil besteht darin, dass es keinen Konflikt gibt , aber der Nachteil ist die räumliche Komplexität Kann höher sein, geeignet für Fälle mit weniger Elementen.
• Division mit Rest-Methode: Es handelt sich um die Hash-Adresse, die durch Division des Datenelementschlüsselworts durch eine bestimmte Konstante übrig bleibt. Diese Methode ist einfach zu berechnen und hat ein breites Anwendungsspektrum. Sie ist eine häufig verwendete Hash-Funktion und kann verwendet werden ausgedrückt als :
  hash(K=K mod C; Der Schlüssel zu dieser Methode ist die Auswahl der Konstante. Die allgemeine Anforderung besteht darin, dass sie nahe oder gleich der Länge der Hash-Tabelle selbst ist. Die Forschungstheorie zeigt, dass die Konstante Funktioniert am besten bei der Auswahl von Primzahlen
• Digitale Analysemethode: Bei dieser Methode werden einige Zahlen mit relativ einheitlichen Werten in den Schlüsselwörtern der Datenelemente als Hash-Adresse verwendet. Dadurch können Konflikte weitestgehend vermieden werden, diese Methode ist es jedoch Nur für Situationen geeignet, in denen alle Schlüsselwörter bekannt sind. Die allgemeinere Hash-Tabelle ist nicht anwendbar.
• Quadratsummenmethode: Konvertieren Sie die aktuelle Zeichenfolge in einen Unicode-Wert und ermitteln Sie das Quadrat dieses Werts Ziffern des quadrierten Werts sind die Hash-Werte der aktuellen Zahl. Konkret hängt die Anzahl der Bits von der Größe der aktuellen Hash-Tabelle ab.
• Segmentierte Summenmethode: Teilen Sie den einzufügenden Wert in mehrere Segmente auf Anzahl der Ziffern in der aktuellen Hash-Tabelle, addieren Sie die Segmente und verwerfen Sie das höchste Bit des Ergebnisses. Dies ist der Hash-Wert dieses Werts Problem: Für zwei verschiedene Schlüsselwörter wird die Hash-Adresse über unsere Hash-Funktion berechnet. Wenn dieselbe Hash-Adresse erhalten wird, nennen wir dieses Phänomen einen Hash-Konflikt ) Füllfaktor, der sich auf den Füllfaktor bezieht, der sich auf das Verhältnis der Anzahl der in der Hash-Tabelle gespeicherten Datenelemente zur Größe des Hash-Adressraums bezieht. Je kleiner a, desto geringer ist die Wahrscheinlichkeit eines Konflikts. Im Gegenteil, die Wahrscheinlichkeit eines Konflikts ist größer. Je kleiner die Raumnutzung, desto kleiner die Raumnutzung. Je größer a, desto höher ist die Raumnutzung normalerweise zwischen 0,6 und 0,9 gesteuert, während HashTable in .net direkt den Maximalwert von a als 0,72 definiert (Obwohl Microsofts offizielles MSDN angibt, dass der Standardfüllfaktor von HashTable 1,0 beträgt, handelt es sich tatsächlich um ein Vielfaches von 0,72)
(2) Es hängt mit der verwendeten Hash-Funktion zusammen. Sie können die Hash-Adressen so gleichmäßig wie möglich im Hash-Adressraum verteilen, wodurch das Auftreten von Konflikten verringert wird. Der Erwerb einer guten Hash-Funktion hängt jedoch weitgehend davon ab viel Übung

1) Offene Adressierungsmethode

Hi=(H(key) + di) MOD m i=1,2,…k(k Wobei H(key) der Hash ist Funktion; m ist die Länge der Hash-Tabelle; di ist eine inkrementelle Sequenz. Es gibt 3 inkrementelle Sequenzen:

①Lineare Erkennung und dann Hashing: di=1,2,3,…,m-1 ②Sekundäre Erkennung und dann Hashing: di=1
2,-1

2,-2

Wir können ein Phänomen beobachten: Wenn Datensätze bereits an den Positionen i, i+1 und i+2 in der Tabelle ausgefüllt sind, werden die Datensätze mit den nächsten Hash-Adressen von i, i+1, i+2 und i+ angezeigt 3 sind alle Die Position von i+3 wird ausgefüllt. Dieses Phänomen, bei dem zwei Datensätze mit unterschiedlichen ersten Hash-Adressen um dieselbe nachfolgende Hash-Adresse konkurrieren, das während der Konfliktverarbeitung auftritt, wird als „sekundäre Aggregation“ bezeichnet, d. h. bei der Verarbeitung von Synonymen In Dem Konfliktprozess kommen nicht-synonyme Konflikte hinzu. Andererseits kann durch die Verwendung linearer Erkennung und anschließendes Hashing zur Bewältigung von Konflikten sichergestellt werden, dass immer eine Adresse Hk gefunden werden kann, die keinen Konflikt verursacht, solange die Hash-Tabelle nicht voll ist. Eine sekundäre Erkennung und Wiederaufbereitung ist nur möglich, wenn die Hash-Tabellenlänge m eine Primzahl der Form 4j+3 ist (j ist eine ganze Zahl). Das heißt, die offene Adressierungsmethode führt zu einer sekundären Aggregation, was sich nachteilig auf die Suche auswirkt.

2) Re-Hash-Methode

Hi = RHi (Schlüssel), i=1,2,...k RHi sind alle verschiedene Hash-Funktionen, das heißt, wenn Synonyme Adresskonflikte verursachen, wird die Adresse eines anderen Hashs verwendet Die Funktion wird berechnet, bis keine Konflikte mehr auftreten. Diese Methode ist weniger anfällig für Aggregation, erhöht jedoch die Berechnungszeit.

Nachteile: Erhöhte Berechnungszeit.

3) Kettenadressmethode (Zipper-Methode)

Speichert alle Datensätze, deren Schlüsselwörter Synonyme sind, in derselben linear verknüpften Liste.

Vorteile:

①Die Zipper-Methode ist einfach mit Konflikten umzugehen und weist kein Akkumulationsphänomen auf, d Die Reißverschlussmethode wird dynamisch angewendet und eignet sich daher besser für Situationen, in denen die Tabellenlänge vor dem Erstellen der Tabelle nicht bestimmt werden kann.
③ Um Konflikte zu reduzieren, erfordert die offene Adressierungsmethode einen kleinen Füllfaktor α Wenn die Größe groß ist, wird viel Platz verschwendet. Bei der Zipper-Methode ist α ≥ 1 akzeptabel, und wenn der Knoten groß ist, ist die in der Zipper-Methode hinzugefügte Zeigerdomäne vernachlässigbar, wodurch Platz gespart wird
④ In einer mit der Zipper-Methode erstellten Hash-Tabelle wird der Vorgang zum Löschen von Knoten ausgeführt ist einfach umzusetzen. Löschen Sie einfach den entsprechenden Knoten in der verknüpften Liste. Bei der mit der offenen Adressmethode erstellten Hash-Tabelle kann beim Löschen eines Knotens der Speicherplatz des gelöschten Knotens nicht einfach leer bleiben, da sonst der Suchpfad des Synonymknotens, der in die Hash-Tabelle eingefügt wird, abgeschnitten wird. Dies liegt daran, dass bei verschiedenen offenen Adressmethoden leere Adresseinheiten (d. h. offene Adressen) Bedingungen für einen Suchfehler sind. Wenn daher ein Löschvorgang für eine Hash-Tabelle ausgeführt wird, der die offene Adressmethode zur Konfliktbehandlung verwendet, kann der gelöschte Knoten nur zum Löschen markiert, der Knoten jedoch nicht tatsächlich gelöscht werden.

class Hash {
  constructor() {
    this.table = new Array(1024);
  }
  hash(data) {
    //就将字符串中的每个字符的ASCLL码值相加起来，再对数组的长度取余
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    console.log("Hash Value: " + data + " -> " + total);
    return total % this.table.length;
  }
  insert(key, val) {
    var pos = this.hash(key);
    this.table[pos] = val;
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

verwendet die quadratische Mid-Step-Methode zum Erstellen der Hash-Funktion und die lineare Erkennungsmethode der offenen Adressmethode zur Lösung von Konflikten.

class Hash {
  constructor() {
    this.table = new Array(1000);
  }
  hash(data) {
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    //把字符串转化为字符用来求和之后进行平方运算
    var s = total * total + ""
    //保留中间2位
    var index = s.charAt(s.length / 2 - 1) * 10 + s.charAt(s.length / 2) * 1
    console.log("Hash Value: " + data + " -> " + index);
    return index;
  }
  solveClash(index, value) {
    var table = this.table
    //进行线性开放地址法解决冲突
    for (var i = 0; index + i < 1000; i++) {
      if (table[index + i] == null) {
        table[index + i] = value;
        break;
      }
    }
  }
  insert(key, val) {
    var index = this.hash(key);
    //把取中当做哈希表中索引
    if (this.table[index] == null) {
      this.table[index] = val;
    } else {
      this.solveClash(index, val);
    }
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

Javascript-Tutorial für Fortgeschrittene】

Das obige ist der detaillierte Inhalt vonWas ist Javascript-Hash?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!