golang マップの実装原理-Golang-php.cn

golang マップの実装原理

王林

リリース： 2023-05-15 11:59:36

オリジナル

871 人が閲覧しました

Golang を学習する過程で、マップはよく使用されるデータ構造であり、キーと値のペアを保存するために使用できます。しかし、マップがどのように実装されるかについて考えたことはありますか?この記事では、Golang でマップがどのように実装されるかを見ていきます。

map の実装原理の紹介

map は実際にはハッシュテーブルであり、その実装原理はハッシュアルゴリズムです。ハッシュテーブルは、キーに基づいてメモリの保存場所に直接アクセスするデータ構造です。つまり、キーをメモリアドレスにマップする方法を提供します。ハッシュテーブルでは、キーワードを「キー」、ハッシュ関数によって計算されたメモリアドレスを「バケット」と呼び、バケットにはキーと値のペアが格納されます。

Golang では、マップはバケットのメモリ領域にキーと値のペアを格納することによって実装されます。各バケットには、バケットの状態を記述するためのヘッダー構造があります。このヘッダー構造は「バケット」と呼ばれます。

バケットデータ構造

最初にバケットデータ構造を見てみましょう:

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
}

ログイン後にコピー

上記の定義から、バケットには次の情報が保存されていることがわかります:

tophash: 一致しないキーをすばやく除外するために使用されます;
data: キーと値のペアを格納するデータ;
overflow: オーバーフローのリンクリストを格納するポインター配列;
count: 現在のバケットに保存されているキーと値のペアの数 (最大 8) を保存します;
flags: バケットのステータス情報を保存します;
BmapType: storage data に保存されているデータのタイプを示します;
tophash0: バケットに関連付けられたキーのタイプ。

実装原理

map に格納されるデータはキーと値のペアであり、キーと値のペアのキー値は反復不可能で比較できるため、ハッシュを使用可能この関数は、キー値を一意のハッシュ値に変換し、そのハッシュ値をキー値に対応するインデックスとして使用し、インデックスに値の値を格納します。

Golang では、各マップにハッシュテーブルがあります。このハッシュテーブルは、実際には複数のバケットを保存できる連続した記憶領域です。各バケットはバケットタイプの構造です。

それでは、ハッシュテーブルのサイズはどのように決定されるのでしょうか?マップの作成時にメモリが動的に割り当てられ、スペースが最初に割り当てられるときに使用されるデフォルトのサイズは 8 バケットです。初めて要素を追加するときにバケットの数が十分でない場合、ハッシュテーブルのサイズが拡張され、ハッシュテーブル内の各要素のインデックス位置が再計算されます。

Golang では、ハッシュ関数の主な機能はキー値をハッシュすることです。これにより、ハッシュテーブル内のバケットを見つけることが容易になり、キー値に対応する値の検索が高速化されます。。 Golang では、ハッシュ関数は MurmurHash3 アルゴリズムを使用して実装されます。

ハッシュ関数はキーを整数にマッピングするため、異なるキー値が同じインデックスにマッピングされる可能性があります。この状況はハッシュ衝突と呼ばれます。ハッシュの競合が発生した場合、Golang はリンクリスト方式を使用して解決し、同じインデックス上のキーと値のペアをインデックスのリンクリストに保存します。これらのキーと値のペアはオーバーフローと呼ばれます。

概要

Golang のマップ実装原理は、主にハッシュテーブルとハッシュ関数に依存しています。ハッシュ関数を使用してキー値をハッシュし、それをハッシュテーブル内のバケットにマッピングすることで、値の検索操作が高速化されます。ハッシュテーブルは複数のバケットで構成され、各バケットはキーと値のペアの情報を格納するバケットタイプ構造によって表されます。ハッシュテーブル内の同じインデックス位置に複数のキーと値のペアがある場合、リンクリスト方式を使用してオーバーフローを格納します。 Golang のマップは実際には動的ハッシュテーブルであり、ハッシュテーブルのサイズを動的に調整できます。マップを使用するときは、ハッシュの衝突を避け、比較できないサイズの型をキーとして含めるように注意する必要があります。

以上がgolang マップの実装原理の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。