go语言实现哈希表 golang hashmap

golang hashmap的使用及实现

由于go语言是一个强类型的语言，因此hashmap也是有类型的，具体体现在key和value都必须指定类型，比如声明一个key为string，value也是string的map，

公司主营业务：成都网站制作、成都网站设计、外贸营销网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出长顺免费做网站回馈大家。

需要这样做

大部分类型都能做key，某些类型是不能的，共同的特点是： 不能使用== 来比较，包括: slice, map, function

在迭代的过程中是可以对map进行删除和更新操作的，规则如下：

golang的map是hash结构的，意味着平均访问时间是O(1)的。同传统的hashmap一样，由一个个bucket组成:

那我们怎么访问到对应的bucket呢，我们需要得到对应key的hash值

各个参数的意思：

目前采用的是这一行:

| 6.50 | 20.90 | 10.79 | 4.25 | 6.50 |

golang map源码浅析

golang 中 map的实现结构为： 哈希表 + 链表。 其中链表，作用是当发生hash冲突时，拉链法生成的结点。

可以看到， []bmap 是一个hash table， 每一个 bmap是我们常说的“桶”。 经过hash 函数计算出来相同的hash值， 放到相同的桶中。 一个 bmap中可以存放 8个 元素， 如果多出8个，则生成新的结点，尾接到队尾。

以上是只是静态文件 src/runtime/map.go 中的定义。 实际上编译期间会给它加料 ，动态地创建一个新的结构：

上图就是 bmap的内存模型， HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 这样的形式。源码里说明这样的好处是在某些情况下可以省略掉 padding 字段，节省内存空间。

每个 bmap设计成 最多只能放 8 个 key-value 对 ，如果有第 9 个 key-value 落入当前的 bmap，那就需要再构建一个 bmap，通过 overflow 指针连接起来。

map创建方法:

我们实际上是通过调用的 makemap ，来创建map的。实际工作只是初始化了hmap中的各种字段，如：设置B的大小， 设置hash 种子 hash 0.

注意 :

makemap 返回是*hmap 指针， 即 map 是引用对象， 对map的操作会影响到结构体内部 。

使用方式

对应的是下面两种方法

map的key的类型，实现了自己的hash 方式。每种类型实现hash函数方式不一样。

key 经过哈希计算后得到hash值，共 64 个 bit 位。 其中后B 个bit位置， 用来定位当前元素落在哪一个桶里， 高8个bit 为当前 hash 值的top hash。 实际上定位key的过程是一个双重循环的过程， 外层循环遍历 所有的overflow， 内层循环遍历 当前bmap 中的 8个元素 。

举例说明： 如果当前 B 的值为 5， 那么buckets 的长度 为 2^5 = 32。假设有个key 经过hash函数计算后，得到的hash结果为：

外层遍历bucket 中的链表

内层循环遍历 bmap中的8个 cell

建议先不看此部分内容，看完后续 修改 map中元素 - 扩容 操作后 再回头看此部分内容。

扩容前的数据：

等量扩容后的数据：

等量扩容后，查找方式和原本相同， 不多做赘述。

两倍扩容后的数据

两倍扩容后，oldbuckets 的元素，可能被分配成了两部分。查找顺序如下：

此处只分析 mapaccess1 ,。 mapaccess2 相比 mapaccess1 多添加了是否找到的bool值， 有兴趣可自行看一下。

使用方式：

步骤如下：

扩容条件 ：

扩容的标识 ： h.oldbuckets ！= nil

假设当前定位到了新的buckets的3号桶中，首先会判断oldbuckets中的对应的桶有没有被搬迁过。 如果搬迁过了，不需要看原来的桶了，直接遍历新的buckets的3号桶。

扩容前：

等量扩容结果

双倍扩容会将old buckets上的元素分配到x， y两个部key 1 B == 0 分配到x部分，key 1 B == 1 分配到y部分

注意： 当前只对双倍扩容描述， 等量扩容只是重新填充了一下元素， 相对位置没有改变。

假设当前map 的B == 5，原本元素经过hash函数计算的 hash 值为：

因为双倍扩容之后 B = B + 1，此时B == 6。key 1 B == 1, 即 当前元素rehash到高位，新buckets中 y 部分. 否则 key 1 B == 0 则rehash到低位，即x 部分。

使用方式：

可以看到，每一遍历生成迭代器的时候，会随机选取一个bucket 以及 一个cell开始。 从前往后遍历，再次遍历到起始位置时，遍历完成。

goland map底层原理

map 是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？

总体来说golang的map是hashmap，是使用数组+链表的形式实现的，使用拉链法消除hash冲突。

golang的map由两种重要的结构，hmap和bmap(下文中都有解释)，主要就是hmap中包含一个指向bmap数组的指针，key经过hash函数之后得到一个数，这个数低位用于选择bmap(当作bmap数组指针的下表)，高位用于放在bmap的[8]uint8数组中，用于快速试错。然后一个bmap可以指向下一个bmap(拉链)。

Golang中map的底层实现是一个散列表，因此实现map的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫 hmap (a header for a go map)，一个叫 bmap (a bucket for a Go map，通常叫其bucket)。这两种结构的样子分别如下所示：

hmap :

图中有很多字段，但是便于理解map的架构，你只需要关心的只有一个，就是标红的字段： buckets数组 。Golang的map中用于存储的结构是bucket数组。而bucket(即bmap)的结构是怎样的呢？

bucket ：

相比于hmap，bucket的结构显得简单一些，标红的字段依然是“核心”，我们使用的map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构。例如下图：

由此看出hmap和bucket的关系是这样的：

而bucket又是一个链表，所以，整体的结构应该是这样的：

哈希表的特点是会有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，Golang也是很有意思。

Golang把求得的值按照用途一分为二：高位和低位。

如图所示，蓝色为高位，红色为低位。 然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找。 需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:

并不是key0/value0/key1/value1的形式，这样做的好处是：在key和value的长度不同的时候，可 以消除padding(内存对齐)带来的空间浪费 。

现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中，高位用于key的快速预览，用于快速试错)

map的扩容

当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将旧数组的数据迁移至新数组。

加载因子

判断扩充的条件，就是哈希表中的加载因子(即loadFactor)。

加载因子是一个阈值，一般表示为：散列包含的元素数 除以 位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了。

每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容。

Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。

当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中，而是，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。

如下图所示：当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组

上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket，橘黄色代表空的bucket。

扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：

注意：这里并不会直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存。

map中数据的删除

如果理解了map的整体结构，那么查找、更新、删除的基本步骤应该都很清楚了。这里不再赘述。

值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：

1

2

3

4

1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；

2、如果是值类型的，则清除相关内存。

3、同理，对``value``做相同的操作。

4、最后把key对应的高位值对应的数组index置为空。