golang map
维基百科里这样定义 map：
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.
在golang中，map的实现主要是基于hash算法。而hash算法常常会出现碰撞的问题，一般有两种方式进行应对，一是链表地址(golang就采用了此方式)，再就是开放寻址法。
通过建立key与elem的映射，达到高效查找key对应的elem，一般时间复杂度为O(1)。
举个简单的例子：
仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。
那么，如何基于 key 定位对应的桶呢？这是通过哈希函数（hash function）实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间
输入一个 key ，哈希函数的计算过程分为以下两步。
通过某种哈希算法 hash() 计算得到哈希值。
将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。
index = hash(key) % capacity随后，我们就可以利用 index 在哈希表中访问对应的桶，从而获取 value 。
设数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100 。
从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。
对于上述示例中的哈希函数，当输入的 key 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为 12836 和 20336 的两个学生时，我们得到：
1 | |
两个学号指向了同一个姓名，这显然是不对的。我们将这种多个输入对应同一输出的情况称为哈希冲突（hash collision）
容易想到，哈希表容量越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。
类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。
负载因子（load factor）是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在 golang 中，当负载因子超过 $0.65$ 时，系统会将哈希表扩容至原先的 $2$ 倍。