首先golang的哈希表又称为map，这个数据结构的优势在于读写性能都是O（1）的。同时拥有数组和链表的优势。

哈希表是key-value形式，本质上是一个数组。在对key进行哈希函数处理后，得到一个整型索引，和value对应。

实现哈希表的关键在于哈希函数的选择，很大程度上决定了哈希表的读写性能。在理想情况下，哈希函数应该能够将不同键映射到不同的索引上，这要求哈希函数输出范围大于输入范围，但是由于键的数量会远远大于映射的范围，所以在实际使用时，这个理想的结果是不可能实现的。

比较实际的方式是让哈希函数的结果能够尽可能的均匀分布，然后通过工程上的手段解决哈希碰撞的问题，但是哈希的结果一定要尽可能均匀，结果不均匀的哈希函数会造成更多的冲突并导致更差的读写性能

在一个使用结果较为均匀的哈希函数中，哈希的增删改查都需要 O(1) 的时间复杂度，但是非常不均匀的哈希函数会导致所有的操作都会占用最差 O(n) 的复杂度，所以在哈希表中使用好的哈希函数是至关重要的。

但是哪怕再好的哈希函数，输入的范围一定会远远大于输出的范围，所以使用哈希表一定会遇到冲突，需要需要一些方法来解决哈希冲突（哈希碰撞）的问题。常见的有开放寻址法和拉链法（链表法）。

不想写了。。。贴大神的文章吧 （怕有一天看不到了）

<!doctype html>理解 Golang 哈希表 Map 的原理 | Go 语言设计与实现

<span style=color:#a6e22e>buckets</span>    <span style=color:#a6e22e>unsafe</span>.<span style=color:#a6e22e>Pointer</span>
<span style=color:#a6e22e>oldbuckets</span> <span style=color:#a6e22e>unsafe</span>.<span style=color:#a6e22e>Pointer</span>
<span style=color:#a6e22e>nevacuate</span>  <span style=color:#66d9ef>uintptr</span>

<span style=color:#a6e22e>extra</span> <span style=color:#f92672>*</span><span style=color:#a6e22e>mapextra</span>

}

type mapextra struct {
overflow []bmap
oldoverflow []bmap
nextOverflow bmap
}

countBbucketslen(buckets) == 2^Bhash0oldbucketsbucketsbuckets

图 3-12 哈希表的数据结构

hmapbmapbmapextra.nextOverflowbmapbmap
bmaptophashtophash
bmaptophashcmd/compile/internal/gc.bmap

如果哈希表存储的数据逐渐增多，我们会对哈希表进行扩容或者使用额外的桶存储溢出的数据，不会让单个桶中的数据超过 8 个，不过溢出桶只是临时的解决方案，创建过多的溢出桶最终也会导致哈希的扩容。

从 Go 语言哈希的定义中就可以发现，它比前面两节提到的数组和切片复杂得多，结构体中不仅包含大量字段，还使用了较多的复杂结构，在后面的小节中我们会详细介绍不同字段的作用。

3.3.3 初始化

既然已经介绍了常见哈希表的基本原理和实现方法，那么可以开始分析 Go 语言中哈希表的实现，首先要分析的就是在 Go 语言中初始化哈希的两种方法 — 通过字面量和运行时。

字面量

key: value
cmd/compile/internal/gc.maplitcmd/compile/internal/gc.maplit

}

addMapEntries

这种初始化的方式与前面两节分析的数组和切片的几乎完全相同，由此看来集合类型的初始化在 Go 语言中有着相同的处理方式和逻辑。

一旦哈希表中元素的数量超过了 25 个，就会在编译期间创建两个数组分别存储键和值的信息，这些键值对会通过一个如下所示的 for 循环加入目标的哈希：

vstatkvstatvmake[]

运行时

BUCKETSIZE8
makemakeruntime.makemapruntime.makemap

}

这个函数的执行过程会分成以下几个部分：

fastrandhintruntime.makeBucketArray
runtime.makeBucketArrayB

}

hmapruntime.newobject

3.3.4 读写操作

哈希表作为一种数据结构，我们肯定需要分析它的常见操作，首先就需要了解其读写操作的实现原理，访问哈希表一般都是通过下标或者遍历两种方式进行的：

for k, v := range hash {
// k, v
}

range
delete

除了这些操作之外，我们还会分析哈希的扩容过程，这能帮助我们深入理解哈希是如何对数据进行存储的。

访问

hash[key]OINDEXMAPcmd/compile/internal/gc.walkexprOINDEXMAP

赋值语句左侧接受参数的个数会决定使用的运行时方法：

runtime.mapaccess1bucketMaskadd
bucketlooptophashtophashtophashtophash

图 3-13 访问哈希表中的数据

tophashtophashkeys[0]keyvalues[0]
runtime.mapaccess2runtime.mapaccess1
v, ok := hash[k]v == nilv

上面的过程其实是在正常情况下，访问哈希表中元素时的表现，然而与数组一样，哈希表可能会在装载因子过高或者溢出桶过多时进行扩容，哈希表的扩容并不是一个原子的过程，在扩容的过程中保证哈希的访问是比较有意思的话题，我们在这里其实也省略了相关的代码，不过会在下面展开介绍。

写入

hash[k]runtime.mapassignruntime.mapaccess1

again:
bucket := hash & bucketMask(h.B)
b := (bmap)(unsafe.Pointer(uintptr(h.buckets) + bucketuintptr(t.bucketsize)))
top := tophash(hash)

tophashinsertiinsertkvalkval
tophashkey

图 3-15 哈希遍历溢出桶

newoverflowhmapnoverflownoverflow

done:
return val
}

typedmemmovevalmapassign
runtime.mapassign_fast64runtime.mapassign24(SP)LEAQAXMOVQ“88”

扩容

我们在介绍哈希的写入过程时省略了扩容操作，随着哈希表中元素的逐渐增加，哈希的性能会逐渐恶化，所以我们需要更多的桶和更大的内存保证哈希的读写性能：

runtime.mapassign
  1. 装载因子已经超过 6.5；
  2. 哈希使用了太多溢出桶；
runtime.mapassign
sameSizeGrowsameSizeGrowsameSizeGrow
runtime.hashGrow

}

runtime.makeBucketArrayoldbucketsbuckets

图 3-15 哈希表触发扩容

runtime.hashGrowruntime.evacuate
runtime.evacuateevacDst

图 3-16 哈希表扩容目的

evacDst

}

b72bfae3f3285244c4732ce457cca823bc189e0b0b11(3)
0b110b111typedmemmove

图 3-17 哈希表桶数据的分流

runtime.evacuateruntime.advanceEvacuationMarknevacuateoldbucketsoldoverflow
runtime.mapaccess1oldbuckets
runtime.evacuate
runtime.mapassignruntime.growWork
runtime.growWork
runtime.growWorksameSizeGrow

删除

delete

图 3-18 哈希表删除操作

deleteODELETEODELETEmapdeletemapdeletemapdelete_faststrmapdelete_fast32mapdelete_fast64

}

runtime.mapdelete
deleteruntime.mapdeleteruntime.mapassign

3.3.5 小结

Go 语言使用拉链法来解决哈希碰撞的问题实现了哈希表，它的访问、写入和删除等操作都在编译期间转换成了运行时的函数或者方法。

tophash

随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容，扩容会将桶的数量翻倍，元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大抖动。

3.3.6 延伸阅读