1哈希表哈希表是编程中比较常见的数据结构之一，基本上所有的语言都会实现数组和哈希表这两种结构，哈希表它的历史比较久远，我们在编程的时候离不开它。这个数据结构的作用其实很简单，就是我们可以根据一个键找到对应的值，也就是说这个数据结构存储了一个键值对的“列表”。1.1原理首先哈希表中第一个点就是哈希函数，也就是我们需要一个函数根据我们的key计算出一个值，然后根据这个值直接找到对应的值。因为我们哈希表的一个功能就是以O(1)的复杂度找到key对应的值。一个完美的哈希函数可以从任何键值计算出一个唯一的、固定大小的值。不幸的是，世界上还没有这样完美的哈希函数。因此，我们需要解决的另一个问题是哈希冲突的解决。1.1.1hash冲突如果我们有两个不同的key，hash函数计算出来的结果是一样的，那么我们不能认为这两个key在map中是一样的，也就是说如果出现这种情况，我们的map结构可以解决这个问题。目前有很多解决方案，这里只介绍三种常见的解决方案：开放寻址法（OpenAddressing）：写的时候：如果密钥Alice和Bob通过hash函数计算出来的结果有冲突。当keyAlice已经存在于map中，再将key写成Bob，发现在hash结果对应的位置已经存在Alice。这时候再找Alice所在位置后面的位置，找一个空的位置，直到Bob写完。读取时：此时映射中已经存在键Alice和Bob，哈希结果相同。这时候，当你要找到Bob对应的值时，先计算Bob的哈希结果，然后用哈希结果在地图中找到位置。此时由于哈希结果与Alice的相同，而Alice在Bob之前的map中存在，所以会直接查找Alice的位置，发现key是Alice而不是Bob，然后再往后查找Alice的位置，直到找到密钥Bob或者它是空的。重新散列（Re-Hashing）：设计多个散列函数，如果Alice和Bob计算出相同的散列结果，则使用另一个散列函数计算Bob的散列值，通过这种方式解决散列冲突。链地址法（SeparateChaining）：这种方法把同一个散列结果对应的位置想象成一个桶。如果多个key对应同一个hash结果，则都放在同一个桶中，桶中的元素采用链表结构存储。写入时：Alice和Bob的哈希结果相同。这时，地图上已经有了爱丽丝。写给Bob时，发现对应的哈希结果位置已经存在Alice。此时，在当前桶中，Alice之后链接了一个Bob。此时哈希结果对应的桶中有Alice和Bob两个元素。读取时：读取Bob的key时，发现哈希结果对应的桶中第一个元素是Alice。此时按照链表的顺序逐一查找桶，直到key相同或者为空。加载因子：这个方案有问题。当一个桶中的元素过多时，它的复杂度就会增加。在极端情况下，它会变成一个链表。所以我们会限制一个桶中元素的数量。这样，当一个桶中的元素过多时，就需要生成一个新的桶。加载因子=元素总数/桶总数在Go语言中，map使用的是链地址方式。2Go中的map分析2.1map数据结构map的源码位于src/runtime/map.go文件中，结构如下：typehmapstruct{countint//当前map中的元素个数flagsuint8Buint8//当前桶数，2^B等于桶数noverflowuint16//approximatenumberofoverflowbuckets;seeincrnoverflowfordetailshash0uint32//哈希种子bucketsunsafe.Pointer//buckets数组指针oldbucketsunsafe.Pointer//扩展时保存之前的buckets数据。nevacuateuintptr//progresscounterforevacuation(bucketslessthanthishavebeenevacuated)extra*mapextra//optionalfields}//每个bucket的结构，即hmap中bucket指向的数据。typebmapstruct{tophash[bucketCnt]uint8}//编译时重构这个结构体typebmapstruct{topbits[8]uint8keys[8]keytypevalues[8]valuetypepaduintptroverflowuintptr}关于hmap的结构体，这里列出了很多重要的字段，其中最重要的最重要的是水桶部分。根据我们上面提到的链地址法，我们可以知道相同类型的key（具有相同的哈希结果）被放入同一个桶中。这时候每个bucket都有另外一个字段overflow，即如果当前bucket放不下，就会创建一个新的bucket。这是Go中map的主要实现方法，后面会讲到更详细的部分。2.2源代码map的源代码位于src/runtime/map.go文件中。map操作的具体实现可以看这里：创建一个map：funcmakemap(t*maptype,hintint,h*hmap)*hmap访问一个key：返回结果只包含value：funcmapaccess1(t*maptype,h*hmap,keyunsafe.Pointer)unsafe.Pointer返回结果包括boolresult:funcmapaccess2(t*maptype,h*hmap,keyunsafe.Pointer)(unsafe.Pointer,bool)savekey:funcmapassign(t*maptype,h*hmap,keyunsafe.Pointer)unsafe.Pointer删除key：funcmapdelete(t*maptype,h*hmap,keyunsafe.Pointer)本文不带大家看源码，只对实现过程进行分析以图片或文字的形式呈现，但建议大家有时间根据本文内容再阅读一遍源码。如果我在这里解释所有的源代码，估计朋友们很快就会忘了。最好记住实施流程。所以本文更多的是介绍每个map操作的流程图和一些关键点，而不是逐行解释源码。3.Diagrammap3.1创建地图我们已经知道了地图的数据结构。其实map的初始化无非就是填充各种字段：第一个是hash0字段，这里会给出一个随机种子，用于hash函数使用的计算。hash函数运行时，Go会检测CPU是否支持aes，支持则使用aeshash，否则使用memhash。alginit()函数位于路径下：src/runtime/alg.go。根据参数提示计算需要的桶数。根据桶的数量创建一个连续的空间来存储桶数据。一般来说，就是这样一个过程。源码中一些检查项废话不多，源码注释也写的很清楚。下图是一个map的主要相关存储结构：map的主要结构3.2定位key我们已经知道了map初始化后的基本结构，接下来就是如何在其中添加一个key对应的value这个结构。我们再看一下每个bucket的结构：typebmapstruct{topbits[8]uint8keys[8]keytypevalues[8]valuetypepaduintptroverflowuintptr}其中keys和values字段是存放key和value的真实内存。我们可以看到每个都是长度为8的数组，也就是说一个bucket里面存放了两个数组，一个存放key列表，一个存放value列表，每条数据的大小都是8。那么当第九个元素进入桶，我们需要创建一个新的桶，即溢出字段指向一个新的桶（bmap结构）。另外一个字段是topbits，也是一个长度为8的数组，其实我们应该认为这三个数组长度相同，应该是有对应关系的，也就是说topbits数组中的第一个元素是一个8位的Size，我们称它为高8位，这个就是我们回忆哈希函数的时候，我们哈希函数的结果取高8位，然后存入topbits数组，然后我们称其为索引在数组i中，那么我们就可以在keys和values数组的第i个位置存储数据。上面是在一个已知的桶中添加或修改元素，那么我们如何找到这个桶呢？我们知道hmap中有一个buckets字段，它指向的是[]bmap数组。那么我们就需要通过key找到对应bmap在[]bmap中的位置。如果对这里的计算感兴趣，可以看看源码。各个算子是如何操作的就不细说了，只说大概的过程：hmap中有一个B字段，根据B字段的值，和key的hash值来计算位置[]bmap中的目标桶（其实就是把key的hash的最后几位作为数组的下标）。现在我们可以根据一个key在hmap中的buckets字段中找到对应的bmap对象，同时根据keyhash的高八位找到它在bmap中的keys和values数组中的位置。这里我们没有说是否有溢出的情况。其实不用说大家也能猜到，当我们定位一个bmap的时候，并不知道它有多少个溢出桶：假设我们有桶A，A的溢出域指向B桶，B的溢出域指向bucketC，假设我们此时已经根据key的hash找到了bucketA，然后循环遍历bucket中的topbits数组，如果某个高位8位hash与high相同-order我们要找的key的8位hash，然后到对应位置的keys数组中去找到对应的key1。如果key1等于我们的目标key，那么直接返回对应values数组中的值。如果key1不等于我们的目标键，则变量桶中的其他元素。假设遍历完bucket中的所有元素都没有找到相同的key，那么这时候就需要去bucketA的溢出bucketB再遍历，如果在B中还是没有找到，那么再去到桶C进行搜索。这个时候大家可以想一下，如果是你，你会怎么实现这部分代码。你的实现和Go的源码一样吗？当我们知道了上面定位key的过程后，对key进行增删改查的过程就不难了。多说一句，因为我们掌握了核心，现在可以看源码了，这时候大家就事半功倍了。
