Pass auf, verliere dich nicht in Trockenware👆
Einführung
Dieser Artikel lernt und versteht hauptsächlich die Eigenschaften von Karten, indem er die Datenstruktur und die Quellcodeimplementierung von Karten in Golang untersucht, einschließlich Modellerkundung, Zugriff und Erweiterung der Karte. Willkommen, um gemeinsam zu diskutieren.
Das zugrunde liegende Speichermodell der Karte
Im Quellcode von golang ist die zugrunde liegende Struktur, die map darstellt, hmap, was die Abkürzung von hashmap ist
type hmap struct {
// map中存入元素的个数， golang中调用len(map)的时候直接返回该字段
count int
// 状态标记位，通过与定义的枚举值进行&操作可以判断当前是否处于这种状态
flags uint8
B uint8 // 2^B 表示bucket的数量， B 表示取hash后多少位来做bucket的分组
noverflow uint16 // overflow bucket 的数量的近似数
hash0 uint32 // hash seed （hash 种子） 一般是一个素数
buckets unsafe.Pointer // 共有2^B个 bucket ，但是如果没有元素存入，这个字段可能为nil
oldbuckets unsafe.Pointer // 在扩容期间，将旧的bucket数组放在这里， 新buckets会是这个的两倍大
nevacuate uintptr // 表示已经完成扩容迁移的bucket的指针， 地址小于当前指针的bucket已经迁移完成
extra *mapextra // optional fields
}
B ist der Logarithmus der Länge des Bucket-Arrays, d. h. die Länge des Bucket-Arrays ist 2^B. Der Bucket ist im Wesentlichen ein Zeiger, der auf einen Speicherplatz zeigt, und die Struktur, auf die er zeigt, ist wie folgt:
// A bucket for a Go map.
type bmap struct {
tophash [bucketCnt]uint8
}
Aber das ist nur die Struktur der Oberfläche (src/runtime/hashmap.go), die beim Kompilieren gefüttert wird und dynamisch eine neue Struktur erzeugt:
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr // 内存对齐使用，可能不需要
overflow uintptr // 当bucket 的8个key 存满了之后
}
bmap ist die zugrunde liegende Datenstruktur dessen, was wir oft "Buckets" nennen. Ein Bucket kann bis zu 8 Schlüssel/Werte speichern. Map verwendet die Hash-Funktion, um den Hash-Wert zu erhalten, um zu entscheiden, welchem Bucket zugewiesen werden soll, und dann entsprechend dem oberen 8 Bit des Hash-Werts Finden, wo es in den Bucket gelegt werden soll Die
Zusammensetzung der spezifischen Karte ist in der folgenden Abbildung dargestellt:
Speichern und Abrufen von Karten
In der Karte erledigen das Speichern und Abrufen im Wesentlichen eine Aufgabe, nämlich:
-
Abfrage, wo das aktuelle k/v gespeichert werden soll. -
Zuweisung/Wert, also verstehen wir die Positionierung des Schlüssels in der Karte und wir verstehen den Zugriff.
Low-Level-Code
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
// map 为空，或者元素数为 0，直接返回未找到
if h == nil || h.count == 0 {
return unsafe.Pointer(&zeroVal[0]), false
}
// 不支持并发读写
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
// 根据hash 函数算出hash值，注意key的类型不同可能使用的hash函数也不同
hash := t.hasher(key, uintptr(h.hash0))
// 如果 B = 5，那么结果用二进制表示就是 11111 ， 返回的是B位全1的值
m := bucketMask(h.B)
// 根据hash的后B位，定位在bucket数组中的位置
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
// 当 h.oldbuckets 非空时，说明 map 发生了扩容
// 这时候，新的 buckets 里可能还没有老的内容
// 所以一定要在老的里面找，否则有可能发生“消失”的诡异现象
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// 说明之前只有一半的 bucket，需要除 2
m >>= 1
}
oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
// tophash 取其高 8bit 的值
top := tophash(hash)
// 一个 bucket 在存储满 8 个元素后，就再也放不下了，这时候会创建新的 bucket，挂在原来的 bucket 的 overflow 指针成员上
// 遍历当前bucket的所有链式bucket
for ; b != nil; b = b.overflow(t) {
// 在bucket的8个位置上查询
for i := uintptr(0); i < bucketCnt; i++ {
// 如果找到了相等的 tophash，那说明就是这个 bucket 了
if b.tophash[i] != top {
continue
}
// 根据内存结构定位key的位置
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey {
k = *((*unsafe.Pointer)(k))
}
// 校验找到的key是否匹配
if t.key.equal(key, k) {
// 定位v的位置
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue {
v = *((*unsafe.Pointer)(v))
}
return v, true
}
}
}
// 所有 bucket 都没有找到，返回零值和 false
return unsafe.Pointer(&zeroVal[0]), false
}
Adressierungsprozess
Erweiterung der Karte
In Golang gelten Map und Slice zunächst für einen kleinen Speicherplatz während der Initialisierung und erweitern die Kapazität dynamisch im Prozess der kontinuierlichen Speicherung der Map. Es gibt zwei Arten der Erweiterung, die inkrementelle Erweiterung und die gleiche Erweiterung (Speicher neu anordnen und zuweisen). Schauen wir uns an, wie die Erweiterung ausgelöst wird:
-
Der Lastfaktor überschreitet den Schwellenwert, und der im Quellcode definierte Schwellenwert beträgt 6,5. (Inkrementelle Erweiterung auslösen) -
Zu viele Überlauf-Buckets: wenn B kleiner als 15 ist, d. h. die Gesamtzahl der Buckets 2^B kleiner als 2^15 ist, wenn die Anzahl der Überlauf-Buckets 2^B überschreitet; wenn B >= 15, d. h. Die Gesamtzahl der Buckets 2^B ist größer oder gleich 2^15, wenn die Überlauf-Bucket-Nummer 2^15 überschreitet. (gleiche Expansion auslösen)
erster Fall
zweiter Fall
Bestellung von Karten
objMap := make(map[string]int)
for i := 0; i < 5; i++ {
objMap[strconv.Itoa(i)] = i
}
for i := 0 ; i < 5; i ++ {
var valStr1, valStr2 string
for k, v := range objMap {
fmt.Println(k)
fmt.Println(v)
valStr1 += k
}
for k, v := range objMap {
fmt.Println(k)
fmt.Println(v)
valStr2 += k
}
fmt.Println(valStr1 == valStr2)
if valStr1 != valStr2 {
fmt.Println("not equal")
}
}
fmt.Println("end")
-
Typisches Nutzungsszenario: Ein typisches Nutzungsszenario für map ist, dass kein sicherer Zugriff von mehreren Goroutinen erforderlich ist. -
Atypische Szenarien (erfordert atomare Operationen): Die Karte kann Teil einer größeren Datenstruktur oder einer bereits synchronisierten Berechnung sein.
， // 不支持并发读写
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}