Verstehen Sie den Hash-Algorithmus und Anwendungsszenarien in einem Artikel

1. Was ist ein Hashing-Algorithmus? Hash und Hashing stammen beide vom Wort Hash, ersteres ist eine Transliteration und letzteres ist eine freie Übersetzung. Es handelt sich um einen Algorithmus, der einen Binärwert beliebiger Länge in einen Binärwert fester Länge abbilden kann. Der abgebildete Binärwert fester Länge wird als Hash-Wert bezeichnet. Ein ausgezeichneter Hash-Algorithmus muss die folgenden Anforderungen erfüllen:

kann die Originaldaten nicht umgekehrt aus dem Hash-Wert ableiten;

reagiert sehr empfindlich auf die Eingabedaten, und ein anderes Bit führt dazu, dass der Hash-Wert sehr unterschiedlich ist; Die Wahrscheinlichkeit eines Hash-Konflikts muss sehr gering sein;

Der Berechnungsprozess des Hash-Algorithmus muss einfach und effizient genug sein, auch wenn die Originaldaten sehr lang sind, kann der Hash-Wert schnell ermittelt werden

2 der Hash-Algorithmus

2.1 Sichere Verschlüsselung

Die gebräuchlicheren Hash-Verschlüsselungsalgorithmen sind MD5 (MD5 Message-Digest Algorithm, MD5 Message Digest-Algorithmus) und SHA (Secure Hash Algorithm, sicherer Hash-Algorithmus).

Das Klartext-Passwort kann nicht aus dem Hash-Wert-Chiffretext abgeleitet werden und die Wahrscheinlichkeit eines Hash-Konflikts ist relativ gering. Diese beiden Punkte gewährleisten die Zuverlässigkeit des Hash-Algorithmus als sichere Verschlüsselungsmethode.

Warum können Hashing-Algorithmen Hash-Kollisionen nicht vollständig vermeiden, sondern nur minimieren?

Das Taubennest-Prinzip besagt, dass wenn 11 Tauben in 10 Taubenkäfige fliegen, dann müssen sich in einem Taubenkäfig 2 oder mehr Tauben befinden. Dann hat der Hash-Wert eine feste Länge, was bestimmt, dass der Hash-Wert ausgeschöpft werden kann, aber theoretisch sind die Originaldaten unendlich, sodass es zu einem Hash-Konflikt kommen kann.

Dieses Anwendungsszenario verwendet die Funktionen 1 und 3 des Hash-Algorithmus, von denen 3 dafür sorgen, dass das Passwort in Vorwärtsrichtung nur sehr schwer zu knacken ist (am Beispiel von MD5 beträgt die Länge des Hash-Werts 128 Bit, und das gibt es auch). 2^128 unterschiedlich Der Hashwert ist sehr schwer zu knacken.

Es gibt keine absolute Sicherheit im Sicherheitsbereich, es gibt jedoch immer noch Möglichkeiten, es zu knacken. Beispielsweise können gängige Passwörter leicht geknackt werden.

Also verwenden wir im Allgemeinen einen Salted-Hash-Algorithmus zur sicheren Verschlüsselung. Die Salting-Methode muss streng vertraulich behandelt werden, was die Schwierigkeit und die Kosten des Knackens erheblich erhöht.

2.2 Eindeutiges Flag

Wenn wir überprüfen, ob zwei Dateien gleich sind, können wir nicht einfach anhand des Dateinamens beurteilen. Weil es zu häufig vorkommt, dass Dateien mit demselben Namen vorhanden sind.

Wir können nach bestimmten Regeln einige Binärdaten aus einer großen Datei entnehmen und einen Hash-Algorithmus verwenden, um einen Hash-Wert als eindeutige Kennung der Datei zu erhalten. Auf diese Weise müssen dieselben Dateien denselben Hash-Wert haben, dh dieselbe eindeutige Kennung. Verschiedene Dateien haben mit hoher Wahrscheinlichkeit unterschiedliche eindeutige Kennungen von Hash-Werten Vergleichen Sie alle Binärdaten der beiden Dateien im Detail, um festzustellen, ob es sich um dieselbe Datei handelt. Die Wahrscheinlichkeit, dass dieses Ereignis eintritt, ist zu gering. Diese Lösung gewährleistet jedoch sowohl Effizienz als auch Zuverlässigkeit.

Dieses Anwendungsszenario nutzt die Features 2 und 3 des Hash-Algorithmus.

2.3 Datenüberprüfung

Im P2P-Download-Protokoll laden wir verschiedene Teile desselben Films von verschiedenen Computern herunter und stellen den Film dann auf unserem eigenen Computer zusammen. Wenn beim Herunterladen eines Teils des Films ein Fehler auftritt oder der Inhalt manipuliert wird, kann es zu Downloadfehlern oder Viren kommen.

Also hashen wir zuerst alle Teile und speichern sie in der Seed-Datei. Nachdem alle Teile heruntergeladen wurden, hashen wir alle Teile, um den Hash-Wert zu erhalten, und vergleichen ihn dann mit dem in der Seed-Datei, um zu überprüfen, ob die Datei vollständig ist.

Dieses Anwendungsszenario nutzt die Features 2 und 4 des Hash-Algorithmus.

2.4 Hash-Funktion

Dieses Szenario wurde bereits vorgestellt, als wir über Hash-Tabellen sprachen. In diesem Szenario sind die Anforderungen an Feature 1 nicht sehr hoch. Die Anforderung an Feature 2 besteht darin, dass die Hashwerte möglichst gleichmäßig verteilt sein sollten. Feature 3 kann bis zu einem gewissen Grad auch Konflikte akzeptieren, die durch gelöst werden können Die Verwendung der offenen Adressierungsmethode und der Zipper-Methode ist anspruchsvoller und erfordert mehr Leistung.

2.5 Lastausgleich

Es gibt viele Lastausgleichsalgorithmen, z. B. Abfragen, zufällige, gewichtete Abfragen usw., aber das Ziel besteht darin, einen sitzungsgebundenen Lastausgleichsalgorithmus zu implementieren, dh alle Lastausgleichsalgorithmen sind gleich Client während einer Sitzung. Anfragen werden alle an denselben Server weitergeleitet.

Wir können die IP-Adresse oder Sitzungs-ID des Clients hashen und den erhaltenen Hash-Wert mit der Anzahl der Server modulieren. Der endgültige Wert ist der Server, der weitergeleitet werden muss, damit der Zweck der Sitzungsbindung erreicht werden kann.

2.6 Daten-Sharding

Wenn wir riesige Datenmengen verarbeiten müssen, kann ein einzelner Server eine so große Datenmenge nicht laden und berechnen. Dann müssen wir die riesigen Datenmengen gleichmäßig auf N Server verteilen, um sie parallel zu verarbeiten Wie wäre es mit einer gleichmäßigen Aufteilung auf N Server?

Wir führen eine Hash-Berechnung der Daten durch und verwenden den erhaltenen Hash-Wert modulo zur Anzahl der Server N. Daten mit demselben Ergebnis werden demselben Server zugewiesen und diesem Server zur Verarbeitung übergeben. N Server verarbeiten riesige Datenmengen parallel und führen die Ergebnisse schließlich zusammen.

2.7 Verteilter Speicher

Speichern Sie große Datenmengen in einem verteilten Cache oder einer verteilten Datenbank. Die Idee des Ausleihens ähnelt dem oben genannten Daten-Sharding. Was ist jedoch zu tun, wenn die Anzahl der ursprünglich eingestellten Server nicht ausreicht?

Es kann nicht durch einfaches Hinzufügen einiger Maschinen gelöst werden. Dies zerstört die Modulo-Operation des Hash-Werts, führt zu einer Cache-Penetration und verursacht einen Lawineneffekt. Ebenso kann das gleiche Problem auftreten, wenn ein Maschinenfehler behoben wird. Zu diesem Zeitpunkt müssen wir einen konsistenten Hash-Algorithmus verwenden, um dieses Problem zu lösen.

Der konsistente Hashing-Algorithmus erstellt einfach einen Hash-Ring mit 2^32 Knoten und hasht die Server-IP und Dateien auf die entsprechenden Knoten. Der erste Server, auf den alle Dateien im Uhrzeigersinn treffen, ist der Server, auf dem sie gespeichert sind. Auf diese Weise kann beim Hinzufügen oder Löschen eines Servers die Anzahl der betroffenen Dateien kontrolliert werden und es kommt nicht zu einer globalen Lawine.

Hash-Ring

Wenn jedoch die Server-IP dem Hash-Ring zugeordnet wird, entsteht mit einer gewissen Wahrscheinlichkeit ein Hash Das Problem des Ringversatzes wird zu einer extrem ungleichmäßigen Verteilung der Dateien auf dem Server führen und zu einem Szenario ausarten, das beim Hinzufügen oder Löschen von Servern zu Beginn leicht einen Lawineneffekt verursacht.

Verzerrung des Hash-Rings

Wir können diesen Servern künstlich eine Reihe virtueller Knoten hinzufügen, sodass alle Serverknoten vorhanden sind in Gleichmäßig auf dem Hash-Ring verteilt.

Hash-Ring mit virtuellen Knoten

3. Zusammenfassung

Verwendungsszenarien des Hash-Algorithmus Far Darüber hinaus gibt es auch CRC-Prüfungen.

Das obige ist der detaillierte Inhalt vonVerstehen Sie den Hash-Algorithmus und Anwendungsszenarien in einem Artikel. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!