Algorithmuserklärung vom Array zur HashMap

1. Was ist ein Array?

Ich habe vergessen, in welchem ​​Buch ich einen Satz wie „Alle Datenstrukturen sind die Entwicklung von Arrays“ gesehen habe. Wenn man darüber nachdenkt, ergibt das tatsächlich Sinn, denn der Speicher des Computers ist eigentlich ein linearer Speicherplatz.

Java-Beispielcode: int[] array = new int[5]

Unter Berücksichtigung der Objekt-Header-Informationen und der Array-Längeninformationen weist die JVM bei der Ausführung 20 Byte Speicherplatz im Heap zu, was wie folgt aussieht:

​

Eine solche Datenstruktur kann leicht über Array-Indizes auf Daten zugreifen, erfordert jedoch beim Suchen das Durchlaufen des Arrays und die durchschnittliche Zeitkomplexität beträgt O (n/2).

Bei großen Datenmengen oder häufigen Suchvorgängen sind solche Durchlaufvorgänge nahezu inakzeptabel. Wie können wir also Daten schnell und in kürzerer Zeit finden?

2. Binäre Suche

Wenn die Elemente im Array sortiert sind, ist die Verwendung der binären Suche die natürliche Lösung.

Zum Beispiel gibt es ein ganzzahliges Array mit einer Länge von 1000. Die ganzen Zahlen im Array sind von klein nach groß angeordnet. Wenn ich wissen möchte, ob 6000 in diesem Array enthalten ist. Dann kann ich zunächst prüfen, ob die Zahl in Array[500] 6000 ist. Wenn die Zahl in Array[500] kleiner als 6000 ist, dann überprüfe die Zahl in Array[750]...und so weiter bis 10 Mal kann das Ergebnis ermittelt werden.

Die zeitliche Komplexität dieses Algorithmus beträgt O(logN).

In den meisten Fällen sind Array-Elemente jedoch ungeordnet, und die für die Sortierung erforderliche Zeitkomplexität O(NlogN) übersteigt in der Regel die für die Durchquerung erforderliche Zeit bei weitem.

Das Problem liegt also wieder bei seinem ursprünglichen Punkt. Wie findet man schnell Daten in ungeordneten Daten?

3. Ignorantes Denken

Ich erinnere mich noch daran, wie ich „Programming Pearls“ gesehen habe, als ich zum ersten Mal Programmieren lernte. Darin stand: In den 1970er Jahren baute Mike Lesk eine Telefonnummernsuchfunktion für die Telefongesellschaft ein. Geben Sie beispielsweise die entsprechende Zifferntaste 5375*6* ein an LESK*M*. Die richtige Telefonnummer oder optionale Liste kann mit einer falschen Übereinstimmungsrate von nur 0,2 % zurückgegeben werden.

Wie kann es gemacht werden?

Damals verstand ich Datenstrukturen und Algorithmen überhaupt nicht. Es ist immer noch sehr interessant, den Prozess meines wilden Denkens von damals wiederherzustellen.

㈠ Ergänzung

Addiert man alle Zahlen (die *-Taste ist 11), ergibt die Summe von 5375*6* 48. Die Summe der meisten Eingaben überschreitet 100 nicht, was bedeutet, dass Zehntausende von Telefonnummern an den ersten 100 Positionen des Arrays geclustert werden, sodass dies nicht möglich ist.

㈡ Multiplikation

Wenn alle Zahlen miteinander multipliziert werden, ist das Produkt 381150. Dies scheint machbar, aber es gibt ein Problem: Die Produkte von lesk, lsek, slke ... sind gleich und jeder Zahlenschlüssel entspricht auch 3 Buchstaben, was bedeutet, dass die Wahrscheinlichkeit einer Wiederholung sehr hoch ist.

㈢ Verbesserte Multiplikation

① Zeichenfolgen mit denselben Buchstaben, aber unterschiedlicher alphabetischer Reihenfolge können Konflikte auf diese Weise vermeiden: Jede Zahl wird zuerst mit der Seriennummer und dann mit anderen Werten multipliziert.

②Jede Zifferntaste entspricht 3 englischen Buchstaben. Wenn der Benutzer die Sequenznummer des Buchstabens nicht in die Zifferntaste eingibt, ist eine weitere genaue Berechnung nicht möglich. Die einzige Richtung, die in Betracht gezogen werden kann, besteht darin, Wahrscheinlichkeitsstatistiken basierend auf der gegebenen Wortliste zu erstellen, daher wird dies nicht berücksichtigt.

㈣ Standortkonflikt

Selbst wenn eine verbesserte Multiplikation verwendet wird, können sich die aus verschiedenen Namensbuchstaben berechneten Produkte immer noch wiederholen. Was ist also zu tun, wenn ein Konflikt auftritt?

Die Sequenz am nächsten leeren Ort speichern? Wenn ich darüber nachdenke, funktioniert das nicht. Wenn die nächste Leerstelle zufällig das Produkt einer anderen Buchstabengruppe ist, kommt es zu einem sekundären Konflikt.

Glücklicherweise gibt es Primzahlen.

Primzahlen können nur durch 1 und sich selbst teilbar sein, daher kann jedes durch die obige Multiplikation erhaltene Produkt keine Primzahl sein, sodass die Telefonnummer nicht an der Primzahlposition gespeichert wird.

Suchen Sie daher ausgehend vom aktuellen Produkt nach der nächsten Primzahl rechts davon. Wenn die Primzahlposition noch verwendet wird, dann fahren Sie mit der Suche nach der nächsten Primzahl fort...

An diesem Punkt scheint das Problem gelöst zu sein.

Der Benutzer gibt eine Zahlenfolge ein, das Produkt wird gemäß der Formel berechnet und die Telefonnummer an der tiefgestellten Position wird zurückgegeben. Wenn es falsch ist, werden die nachfolgenden Primzahlen sequentiell durchsucht, bis das von einer bestimmten Primzahl tiefgestellte Array-Element leer ist, und schließlich werden alle gefundenen Telefonnummern zurückgegeben. In den meisten Fällen kann die Telefonnummer in der Zeitkomplexität O(1) gefunden werden.

㈤ Das Array ist zu groß

Das einzige Problem besteht darin, dass das nach der obigen Idee erstellte Array wirklich zu groß ist. Ein Name hat 10 Buchstaben. Wenn die Zahl, die jedem Buchstaben entspricht, 9 ist, beträgt das Endprodukt ungefähr 9 hoch 17. Das bedeutet, ein Array der Größe 9^17 zu erstellen, was völlig unmöglich ist.

㈥Später

Selbst wenn der Faktor, dass das Array zu groß ist, nicht berücksichtigt wird, wäre ich angesichts meines damaligen Anfängerniveaus in der Programmierung nicht in der Lage gewesen, ein solches Programm zu schreiben.

Der Grund, warum ich diesen Denkprozess wiederhergestellt habe, ist, dass ich den Prozess des unabhängigen Denkens für sehr interessant und wertvoll halte. Denken Sie darüber nach, tatsächlich wurden die vorhandenen Algorithmen schließlich von diesen großen Leuten abgeleitet, die in tatsächlichen Projekten Schritt für Schritt nach Lösungen suchten.

Wenn Sie also in der Technik auf schwierige Probleme stoßen, können viele sogenannte Probleme gelöst werden, solange Sie bereit sind, über die Zerlegung des Problems nachzudenken und nach Lösungen für jedes kleine Problem zu suchen.

Später, nachdem ich „Datenstruktur- und Algorithmusanalyse. Beschreibung der Java-Sprache“ gelesen hatte, wurde mir klar, dass meine Idee tatsächlich offene Adressierung war.

HashMap von JDK verwendet eine separate Verkettung. Unterschied: Das Konzept der Buckets wird hinzugefügt, um widersprüchliche Daten zu speichern; die Restoperation wird durchgeführt, um die Array-Größe zu reduzieren.

Sprechen wir also über HashMap in Java.

4. Detaillierte Erläuterung der HashMap-Struktur und des Algorithmus

Das Wesentliche von HashMap ist immer noch ein Array, und es ist ein mehrdimensionales Array variabler Länge, ähnlich der folgenden Struktur:

㈠ Kurze Einführung

Das Array in HashMap speichert den Kopfknoten der verknüpften Liste.

Daten speichern:

Berechnen Sie den HashCode des Schlüssels und führen Sie dann eine Restoperation mit der Array-Länge durch, um den Array-Index (Kopfknoten der verknüpften Liste) zu erhalten.

Wenn die Position leer ist, generieren Sie einen neuen verknüpften Listenknoten und speichern Sie ihn im Array.

Wenn die Position nicht leer ist, wird jeder Knoten in der verknüpften Liste zyklisch verglichen: Es gibt bereits einen Knoten mit demselben Schlüssel, und der alte Knoten wird überschrieben, wenn kein Knoten mit demselben Schlüssel vorhanden ist der Endknoten der verknüpften Liste (Hinweis: Siehe JDK1.8-Quellcode; neue Knoten werden immer am Ende der verknüpften Liste hinzugefügt, anstatt wie bei JDK1.6 der Kopfknoten der verknüpften Liste zu sein).

Suchdaten:

Berechnen Sie den HashCode des Schlüssels und führen Sie dann eine Restoperation mit der Array-Länge durch, um den Array-Index (Kopfknoten der verknüpften Liste) zu erhalten. Wenn die verknüpfte Liste nicht leer ist, vergleichen Sie zuerst den ersten Knoten. Wenn der erste Knotenschlüssel gleich ist (hashCode ist gleich und gleich ist wahr), wird der Wert des ersten Knotens direkt zurückgegeben , werden die anderen Knoten in der verknüpften Liste nacheinander durchlaufen und verglichen, und der Wert mit demselben Schlüssel wird zurückgegeben. Der Wert des Knotens (null wird zurückgegeben, wenn kein Knoten mit demselben Schlüssel gefunden wird).

Der Zweck der Einführung verknüpfter Listen durch HashMap besteht darin, das im vorherigen Abschnitt besprochene Problem des doppelten Konflikts zu lösen.

Hinweis:

Wenn der Hashcode aller Schlüssel gleich ist, vorausgesetzt, sie sind alle 0, dann 0%4 = 0, werden alle Elemente in der verknüpften Liste 0 gespeichert, und das Speichern und Suchen nach den einzelnen Daten erfordert das Durchlaufen der verknüpften Liste 0. Dann ist die HashMap zu diesem Zeitpunkt im Wesentlichen zu einer verknüpften Liste verkommen, und auch die zeitliche Komplexität ist vom entworfenen O(1) auf O(n/2) gestiegen.

Um die zeitliche Komplexität der HashMap-Suche und -Speicherung bei O(1) so gering wie möglich zu halten, müssen die Elemente in jeder verknüpften Liste gleichmäßig verteilt sein, d. h. jede verknüpfte Liste speichert nur ein Element.

​Was sind also die Einflussfaktoren?

Erstens kann der Hashcode des Schlüssels nicht wiederholt werden, es wird definitiv eine verknüpfte Liste geben, um mindestens 2 Elemente zu speichern Das zweite ist das Design der Hash-Funktion. Wenn es sich nur um einen einfachen Rest handelt, wird der Rest häufig wiederholt Das dritte ist die Kapazität des Arrays. Wenn 100 Elemente in einem Array mit einer Länge von 10 verteilt werden sollen, gibt es unabhängig von der Berechnung eine verknüpfte Liste zum Speichern mehrerer Elemente Liste speichert 10;

Das Algorithmusdesign dieser drei Faktoren wird im Folgenden ausführlich vorgestellt.

㈡ Hashcode-Generierung

Dies ist der HashCode-Generierungscode der String-Klasse.

Der Wert der String-Klasse ist char[], und char kann in UTF-8-Codierung konvertiert werden. Die UTF-8-Kodierungen von „a“, „b“ und „c“ sind beispielsweise 97, 98 bzw. 99; „abc“ wird in eine Formel umgewandelt, die auf dem obigen Code basiert:

h = 31 * 0 + 97 = 97;

　　public int hashCode() {
　　　　int h = hash;
　　　　if (h == 0 && value.length > 0) {
　　　　　　char val[] = value;
　　　　　　for (int i = 0; i < value.length; i++) {
　　　　　　　　h = 31 * h + val[i];
　　　　　　}
　　　　　　hash = h;
　　　　}
　　　　return h;
　　}

h = 31 * 97 + 98 = 3105;

h = 31 * 3105 + 99 = 96354;

31 wird als Multiplikatorfaktor verwendet, da es sich um eine relativ geeignete Größe der Primzahl handelt: Wenn der Wert zu klein ist, ist das Produkt zu klein, wenn die Anzahl der an der Berechnung des Hashcodes beteiligten Elemente gering ist; Dies entspricht einer Linksverschiebung. Bei der Multiplikation führt ein Überlauf zu einem regelmäßigen Bitinformationsverlust. Beides führt zu einer erhöhten Wiederholungsrate.

Wenn 32 als Multiplikatorfaktor verwendet wird (entspricht << 5), lauten am Beispiel der Zeichenfolge „abcabcabcabcabc“ die Berechnungsergebnisse jedes Schritts ihres Hashcodes wie folgt:

​

Wie in der Abbildung oben gezeigt, generieren alle 3 Buchstaben am Ende der Zeichenfolge einen wiederholten Hashcode. Dies ist kein Zufall. Selbst wenn Sie zu anderen englischen Buchstaben wechseln, ist es leicht, sie zu wiederholen, und die Verwendung von Primzahlen verringert die Wahrscheinlichkeit einer Wiederholung erheblich. Wenn Sie interessiert sind, können Sie sich auf das Bild oben beziehen, um den Linksverschiebungsvorgang durchzuführen, und Sie werden feststellen, dass dies kein Zufall ist.

　　《Effective Java》一书中详细描述了hashcode的生成规则和注意事项，有兴趣的可以去看看。

　　从源代码的hashCode()方法可知，String类对象保存了已经计算好的hashCode，如果已经调用过hashCode()方法，那么第二次调用时不会再重新生成，而是直接返回已经计算好的hashCode。

　　String对象总是会存放到String类私有维护的常量池中，不显式使用new关键字时，如果常量池中已经有value相同的对象，那么总是会返回已有对象的引用。因此，很多情况下生成hashCode这种比较昂贵的操作实际上并不需要执行。

　　㈢ 哈希函数设计

　　现在，已经得到了重复率很低的hashCode，还有什么美中不足的地方吗？

　　⑴ 扰动函数

　　static final int hash(Object key) {
　　　　　　int h;
　　　　　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
　　}

　　下图还是以字符串“abcabcabcabcabc”为例，使用上面方法得到的运算过程和结果。

　　

　　为什么要先无符号右位移16位，然后再执行异或运算？看看下图的二进制的与运算，你就会明白。

　　

　　你会发现只要二进制数后4位不变，前面的二进制位无论如何变化都会出现相同的结果。为了防止出现这种高位变化而低位不变导致的运算结果相同的情况，因此需要将高位的变化也加入进来，而将整数的二进制位上半部与下半部进行异或操作就可以得到这个效果。

　　为什么要使用与运算？

　　因为哈希函数的计算公式就是hashCode % tableSize，当tableSize是2的n次方(n≥1)的时候，等价于hashCode & (tableSize - 1)。

　　扰动函数优化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0

　　扰动函数优化后：1955003654 % 16 = 1955003654 & (16 - 1) = 6

　　这就是为什么需要增加扰动函数的原因。

　　⑵ 源代码详解

　　代码解释之前需要补充说明一下，jdk1.8引入了红黑树来解决大量冲突时的查找效率，所以当一个链表中的数据大到一定规模的时候，链表会转换成红黑树。因此在jdk1.8中，HashMap的查找和保存数据的最大时间复杂度实际上就是红黑树的时间复杂度O(logN)。

　　以下是HashMap中的保存数据的方法源代码，相信经过以上的描述，已经非常容易看懂这一段代码。

　　final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
　　　　Node<K,V>[] tab;　　　　//HashMap数组
　　　　Node<K,V> p;　　　　　　//初始化需要保存的数据
　　　　int n;　　　　　　　　　//数组容量
　　　　int i;　　　　　　　　　//数组下标

　　　　/* 如果数组为空或0，初始化容量为16 */
　　　　if ((tab = table) == null || (n = tab.length) == 0){
　　　　　　n = (tab = resize()).length;
　　　　}

　　　　/* 使用哈希函数获取数组位置(如果为空，保存新节点到数组) */
　　　　if ((p = tab[i = (n - 1) & hash]) == null){
　　　　　　tab[i] = newNode(hash, key, value, null);
　　　　}

　　　　/* 如果数组位置已经有值，则使用下列方式保存数据 */
　　　　else {
　　　　　　Node<K,V> e;　　　　//临时节点保存新值
　　　　　　K k;　　　　　　　　//临时变量用于比较key

　　　　　　//如果头节点与新节点的key的hash值相同 且 key的值相等，e赋值为旧节点
　　　　　　if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
　　　　　　　　e = p;
　　　　　　}

　　　　　　//如果头节点是一个红黑树节点，那么e将保存为树节点
　　　　　　else if (p instanceof TreeNode){
　　　　　　	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
　　　　　　}

　　　　　　//如果头节点与新节点不同，且头节点不是红黑树节点，循环比对链表的所有节点
　　　　　　else {
　　　　　　　　for (int binCount = 0; ; ++binCount) {
　　　　　　　　　　if ((e = p.next) == null) {
　　　　　　　　　　　　//如果直到链表尾未找到相同key的节点，将新结点作为最后一个节点加入到链表
　　　　　　　　　　　　p.next = newNode(hash, key, value, null);

　　　　　　　　　　　　//如果链表节点数大于等于8-1，转换成红黑树；转换成红黑树的最小节点数是8
　　　　　　　　　　　　if (binCount >= TREEIFY_THRESHOLD - 1){
　　　　　　　　　　　　　　treeifyBin(tab, hash);
　　　　　　　　　　　　}
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　　　//如果循环过程中发现新旧key的值相同，跳转：是否覆盖旧值
　　　　　　　　　　if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　　　p = e;
　　　　　　　　}
　　　　　　}

　　　　　　//是否覆盖旧值
　　　　　　if (e != null) {
　　　　　　　　V oldValue = e.value;
　　　　　　　　//如果新值不为空且（允许修改旧值 或 旧值为空），覆盖旧节点的值
　　　　　　　　if (!onlyIfAbsent || oldValue == null){
　　　　　　　　　　e.value = value; 	
　　　　　　　　}
　　　　　　　　afterNodeAccess(e);　　//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
　　　　　　　　return oldValue;　　　　//返回旧值
　　　　　　}
　　　　}

　　　　//用于比较判断是否在遍历集合过程中有其它线程修改集合，详情请网上搜索fail-fast快速失败机制
　　　　++modCount;

　　　　//当key数量大于允许容量时进行扩容。允许容量在HashMap中是数组长度 * 装填因子(默认0.75)
　　　　if (++size > threshold){
　　　　	resize();
　　　　}

　　　　//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
　　　　afterNodeInsertion(evict);
　　　　return null;
　　}

　　⑶ 简化后的伪代码

　　putval(key, value){
　　　　index = key.hashcode % tablesize;
　　　　if(null == table[index]){
　　　　　　table[index] = new node(key, value);
　　　　}else{
　　　　　　firstNode = table[index];
　　　　　　nextNode = firstNode.next;
　　　　　　while(nextNode.hasNextNode()){
　　　　　　　　//如果找到相同key的旧节点，覆盖旧节点
　　　　　　　　if(key == nextNode.key){
　　　　　　　　　　nextNode = new node(key, value);　　
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　//如果到队列末尾依然没有找到相同key的旧节点，将新结点加入到最后一个节点的末尾
　　　　　　　　if(nextNode.next == null){
　　　　　　　　　　nextNode.next = new node(key, value);
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　nextNode = nextNode.next;
　　　　　　}
　　　　}
　　}

　　⑷ 数组大小设计

　　代码注释中已经稍有提及，这里再分别展开讨论。

　　①数组容量选择

　　HashMap的初始容量是 1 << 4，也就是16。以后每次扩容都是size << 1，也就是扩容成原来容量的2倍。如此设计是因为 2^n-1(n≥1)的二进制表示总是为重复的1，方便进行求余运算。

　　《数据结构与算法分析.Java语言描述》一书中的建议是容量最好是质数，有助于降低冲突，但没有给出证明或实验数据。

　　质数虽然是神奇的数字，但个人感觉在这里并没有特别的用处。

　　根据公式index = hashCode % size可知，无论size是质数还是非质数，index的值区间都是0至(size-1)之间，似乎真正起决定作用的是hashCode的随机性要好。

　　这里先不下结论，待以后再写一个随机函数比较下质数和非质数重复率。

　　②装填因子

　　装填因子默认是0.75，也就是说如果数组容量为16，那么当key的数量大于12时，HashMap会进行扩容。

　　装填因子设计成0.75的目的是为了平衡时间和空间性能。过小会导致数组太过于稀疏，空间利用率不高；过大会导致冲突增大，时间复杂度会上升。

　　㈣ 关于其它

　　红黑树是在JDK 1.8中引入的，想用简单的语言来讲清楚红黑树的数据结构、增删改查操作及时间复杂度分析，这是一个复杂且艰难的任务，更适合单独来描述，因此留待以后吧。

　五　最小完美哈希函数(Minimal Perfect Hash Function, MPHF)

　　Jdk中的HashMap解决了任意数据集的时间复杂度问题，所设计的哈希函数在未知数据集的情况下有良好的表现。

　　但如果有一个已知数据集(如Java关键字集合)，如何设计一个哈希函数才能同时满足以下两方面的要求：

　　⑴ 容器容量与数据集合的大小完全一致；

⑵ Es liegt kein Konflikt vor.

Mit anderen Worten: Wenn bei einem bestimmten Datensatz eine Hash-Funktion zulässt, dass jeder Knoten des Containers genau ein Datenelement hat, wird eine solche Hash-Funktion als minimal perfekte Hash-Funktion bezeichnet.

Kürzlich habe ich die Prinzipien der Kompilierung studiert und erwähnt, wie das O(1)-Zeitkomplexitätssuchproblem von Schlüsselwortsätzen gelöst werden kann, und erwähnt, dass die minimale perfekte Hash-Funktion verwendet werden kann. Wenn ich so einen Begriff sehe, fühle ich mich sofort sehr gut und edel.

Das obige ist der detaillierte Inhalt vonAlgorithmuserklärung vom Array zur HashMap. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!