概述
Go语言中的map类型是一种非常有用的数据结构，可以快速查找和添加键值对。底层实现采用了哈希表，这种数据结构使用哈希函数将键映射到桶中，桶再保存键值对数据。它的主要好处是在O(1)时间内访问每个元素，所以查找和添加元素的时间复杂度是O(1)。
哈希表的实现
哈希表的核心是哈希函数。哈希函数将键转换为散列值（通常是一个整数）。该散列值表示桶数组中的索引位置。桶数组是一个包含桶的数组，每个桶都包含元素。当要查找或插入键时，哈希函数将它们映射到桶数组中并查找/插入对应的桶。由于哈希函数不是一一对应的，不同的键可能会被映射到相同的索引位置。当出现键冲突时，Go语言的解决方案是使用链表。
桶数组中的每个元素都是一个指向哈希桶链表的指针。如果在查找一个键值对时，它的散列值所对应的桶链表中有对应的键值对，则查找成功；反之，则会遍历同一个桶中的所有元素，直到找到指定键值对，或者链表末尾。
哈希函数是在key被插入map时计算的，其目的是分配桶位置。在map的生命周期中，元素的key值不会改变，因此哈希函数的值就是固定的。这也是哈希函数一定要快速的原因。如果我们对性能和内存资料有很高的要求，我们可能需要覆盖Go的默认哈希函数以实现自定义的哈希函数。
resize操作
在实际使用中，仅仅上述数据结构还不够。当插入键值对数量达到哈希表容量时，哈希表的内存空间就已经被使用完了，map再添加新的键值对，就需要重新使用离散的内存地址。因为哈希表使用了数组，因此在增大容量时需要重新分配一个更大的数组，然后将旧的哈希表中的键值对复制到新的哈希表中。此时会遍历旧哈希表中的所有桶以便复制每个节点。因为增量大小是原来大小的d倍，即使计算散列函数的代价很高，也能够达到O(d)。
resize是哈希表内部的一个数组扩容操作，当map中元素个数达到阈值或者容量到达极限时，将自动触发resize操作。resize操作的复杂度是O(N)。在进行resize时，map底层会新建一个全新的哈希表，并且重新将索引mapping到hashmap的entry中。同时为了防止频繁的resize操作，map面向的是空间换时间策略，试图提前准备较大的容量。
在Go1.12之前，哈希表使用的是最为简单直接的resize策略，即容量为当前key的两倍。在Go1.12，哈希表的resize策略进行了改变，通过引入溢出桶来减少碰撞，可以解决一些极端场景的问题，进一步提升了哈希表的性能。
本文来自投稿，不代表亲测学习网立场，如若转载，请注明出处：https://www.qince.net/golang-e2w2j.html
郑重声明：
本站所有内容均由互联网收集整理、网友上传，并且以计算机技术研究交流为目的，仅供大家参考、学习，不存在任何商业目的与商业用途。 若您需要商业运营或用于其他商业活动，请您购买正版授权并合法使用。
我们不承担任何技术及版权问题，且不对任何资源负法律责任。
如遇到资源无法下载，请点击这里失效报错。失效报错提交后记得查看你的留言信息，24小时之内反馈信息。
如有侵犯您的版权，请给我们私信，我们会尽快处理，并诚恳的向你道歉！
