Golang-Map-Implementierungsprinzip

Beim Lernen von Golang ist Map eine Datenstruktur, die wir häufig verwenden und die zum Speichern von Schlüssel-Wert-Paaren verwendet werden kann. Aber haben Sie jemals darüber nachgedacht, wie die Karte implementiert wird? In diesem Artikel werden wir untersuchen, wie die Karte in Golang implementiert wird.

Einführung in das Implementierungsprinzip von Map

map ist eigentlich eine Hash-Tabelle, und ihr Implementierungsprinzip ist der Hash-Algorithmus. Eine Hash-Tabelle ist eine Datenstruktur, die basierend auf Schlüsseln direkt auf Speicherorte zugreift, d. h. sie bietet eine Möglichkeit, Schlüssel Speicheradressen zuzuordnen. In einer Hash-Tabelle werden Schlüsselwörter als „Schlüssel“ und die von der Hash-Funktion berechneten Speicheradressen als „Buckets“ bezeichnet. Die Buckets speichern Schlüssel-Wert-Paare.

In Golang wird die Zuordnung durch Speichern von Schlüssel-Wert-Paaren im Bucket-Speicherbereich implementiert. Jeder Bucket verfügt über eine Header-Struktur, die den Status des Buckets beschreibt. .

Bucket-Datenstruktur

Schauen wir uns zunächst die Bucket-Datenstruktur an:

type bmap struct {
    tophash [bucketCnt]uint8
    // data 的类型在 map 被分配空间的时候由 map 的 key 和 value 类型决定
    // 如果 key 类型和 value 类型都是未知类型，那么 data 的类型是 byte
    // 因为 byte 可以用于存储任何类型，也就是说 data 可以存储任何类型的 key 和 value
    // 在存储 key 和 value 的时候，需要将 key 和 value 转换成 uintptr，然后再转换成 byte 存储到 data 中
    // 读取 key 和 value 的时候反向操作即可
    // 因此，map 中的 key 和 value 一般都是需要转换成 uintptr 类型的
    // 这里我们可以简单地理解为 data 存储了键值对的二进制数据
    // 第一个 bucket 中如果存不下某个 key-value，还需要在第二个 bucket 中存储
    // 所以，data 的长度可以为 1 或 2
    // 当 data 的长度为 1 或 2 时，存储的键值对的个数分别为 1 或 2
    // 因此，bucket 中最多只能存储 8 个键值对
    // 否则，就需要将键值对存储在 overflow 中
    // overflow 是一个指向单链表头部的指针数组
    // 如果某个桶存储的键值对数量超过了 8，那么就将多余的键值对存储到 overflow 中
    // overflow 中的第一个 bucket 中也是能够存储 8 个键值对的，如果第一个 bucket 中存不下的话
    // 那么还需要在第二个 bucket 中继续存储
    // 所以，overflow 数组的长度也可以为 1 或 2
    // 当 overflow 数组长度为 1 或 2 时，最多存储 8 个键值对的 overflow
    // 当 overflow 数组长度为 3 时，最多存储 24 个键值对的 overflow
    // 也就是说，如果 map 中存储的键值对数量很多的话，那么可能会有很多个 overflow 桶
    // 而 overflow 数组是动态分配的，因此它的长度是不定的，只有在运行时才能确定
    data unsafe.Pointer
    // overflow 是一个指针数组，用于存储除当前桶以外的其它桶
    // 如果某个桶的键值对数量超过了 8，那么它会将多余的键值对存储到 overflow 中
    // overflow 数组中的每个元素都是一个 bucket 指针
    // 这些 bucket 指针构成了一个链表，也就是所谓的 overflow 链表
    overflow *[]*bmap
    // 这里存储的是这个 bucket 当前存储的键值对的个数
    count int16
    // flags 存储了 bucket 的标志
    // 一个 bucket 可能会有如下三种状态：
    // 1. empty，表示这个 bucket 没有存储任何键值对
    // 2. iterator，表示这个 bucket 正在被访问，不能再被其它操作使用
    // 3. deleted，表示这个 bucket 存储的键值对已经被删除了
    // 注意，该标志位只有在 GC 达到一定阈值后才会被置为 true，而且并不是立即删除键值对，而是在下一次 GC 的时候才会内存回收
    flags uint8
    // Bmap 的类型标记
    // Bmap 用来标识存储于上文中 data 指针中的数据类型
    // 如果 data 中存储的是 int，那么 Bmap 的值为 hmap.BmapInt
    // 如果 data 中存储的是 string，那么 Bmap 的值为 hmap.BmapString
    // 如果 data 中存储的是 interface{}，那么 Bmap 的值为 hmap.BmapInterface
    // 如果 data 中存储其他类型，那么 Bmap 的值为 hmap.BmapOther
    BmapType uint16
    // 与该 bucket 相关联的 key 的类型
    tophash0 uint8
}

Aus der obigen Definition können wir sehen, dass der Bucket-Speicher wie folgt ist Informationen werden abgerufen:

• tophash: wird verwendet, um nicht übereinstimmende Schlüssel schnell herauszufiltern;
• Daten: Daten, die Schlüssel-Wert-Paare speichern; 🎜#overflow: Ein Zeiger-Array, das die überlaufverknüpfte Liste speichert;
• count: Speichert die Anzahl der im aktuellen Bucket gespeicherten Schlüssel-Wert-Paare, bis zu 8; Flags: Speichert einige Statusinformationen des Buckets;
• BmapType: speichert den Typ der in data gespeicherten Daten;
• Implementierungsprinzip
• Da es sich bei den in der Karte gespeicherten Daten um Schlüssel-Wert-Paare handelt und die Schlüsselwerte der Schlüssel-Wert-Paare nicht wiederholbar sind und kann verglichen werden. Wir können eine Hash-Funktion verwenden, um den Schlüsselwert in einen eindeutigen Hash-Wert umzuwandeln, dann den Hash-Wert als Index verwenden, der dem Schlüsselwert entspricht, und den Wertwert in diesem Index speichern.
• In Golang verfügt jede Karte über eine Hash-Tabelle. Diese Hash-Tabelle ist tatsächlich ein kontinuierlicher Speicherplatz, der mehrere Buckets speichern kann.

Wie wird also die Größe der Hash-Tabelle bestimmt? Beim Erstellen der Karte wird der Speicher dynamisch zugewiesen, und die Standardgröße, die bei der ersten Speicherplatzzuweisung verwendet wird, beträgt 8 Buckets. Wenn beim erstmaligen Hinzufügen von Elementen die Anzahl der Buckets nicht ausreicht, wird die Größe der Hash-Tabelle erweitert und die Indexposition jedes Elements in der Hash-Tabelle neu berechnet.

In Golang besteht die Hauptfunktion der Hash-Funktion darin, den Schlüsselwert zu hashen, was das Auffinden eines Buckets in der Hash-Tabelle erleichtert und dadurch die Suche nach dem dem Schlüssel entsprechenden Wert beschleunigt Wert. . In Golang wird die Hash-Funktion mithilfe des MurmurHash3-Algorithmus implementiert.

Da die Hash-Funktion den Schlüssel einer Ganzzahl zuordnet, können unterschiedliche Schlüsselwerte demselben Index zugeordnet werden. Diese Situation wird als Hash-Kollision bezeichnet. Wenn ein Hash-Konflikt auftritt, verwendet Golang die Methode der verknüpften Liste, um ihn zu lösen, und speichert die Schlüssel-Wert-Paare im selben Index in der verknüpften Liste des Index. Diese Schlüssel-Wert-Paare werden als Überlauf bezeichnet.

Zusammenfassung

Golangs Kartenimplementierungsprinzip basiert hauptsächlich auf Hash-Tabellen und Hash-Funktionen. Eine Hash-Funktion wird verwendet, um den Schlüsselwert zu hashen und ihn einem Bucket in einer Hash-Tabelle zuzuordnen, wodurch die Suche nach dem Wert beschleunigt wird. Die Hash-Tabelle besteht aus mehreren Buckets. Jeder Bucket wird durch eine Bucket-Typ-Struktur dargestellt, in der Informationen zu Schlüssel-Wert-Paaren gespeichert sind. Wenn sich an derselben Indexposition in der Hash-Tabelle mehrere Schlüssel-Wert-Paare befinden, wird die Methode der verknüpften Liste zum Speichern des Überlaufs verwendet. Die Karte in Golang ist eigentlich eine dynamische Hash-Tabelle, die die Größe der Hash-Tabelle dynamisch anpassen kann. Bei der Verwendung von Karten muss darauf geachtet werden, Hash-Kollisionen zu vermeiden und Typen mit unvergleichlicher Größe als Schlüssel einzubeziehen.

Das obige ist der detaillierte Inhalt vonGolang-Map-Implementierungsprinzip. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!