由于本文篇幅较长，故分为三次发送。完整目录整理如下
什么是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.
说明：在计算机科学中，包含键值对（key-value）集合的抽象数据结构（关联数组、符号表或字典），其每个可能的键在该集合中最多出现一次，这样的数据结构就是一种Map。
操作
对Map的操作主要是增删改查：
- 在集合中增加键值对
- 在集合中移除键值对
- 修改某个存在的键值对
- 根据特定的键寻找对应的值
实现
Map的实现主要有两种方式：哈希表（hash table）和搜索树（search tree）。例如Java中的hashMap是基于哈希表实现，而C++中的Map是基于一种平衡搜索二叉树——红黑树而实现的。以下是不同实现方式的时间复杂度对比。
可以看到，对于元素查找而言，二叉搜索树的平均和最坏效率都是O(log n)，哈希表实现的平均效率是O(1)，但最坏情况下能达到O(n)，不过如果哈希表设计优秀，最坏情况基本不会出现（所以，读者不想知道Go是如何设计的Map吗）。另外二叉搜索树返回的key是有序的，而哈希表则是乱序。
哈希表
由于Go中map的基于哈希表（也被称为散列表）实现，本文不探讨搜索树的map实现。以下是Go官方博客对map的说明。
One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.
学习哈希表首先要理解两个概念：哈希函数和哈希冲突。
哈希函数
哈希函数（常被称为散列函数）是可以用于将任意大小的数据映射到固定大小值的函数，常见的包括MD5、SHA系列等。
一个设计优秀的哈希函数应该包含以下特性：
- 均匀性 ：一个好的哈希函数应该在其输出范围内尽可能均匀地映射，也就是说，应以大致相同的概率生成输出范围内的每个哈希值。
- 效率高 ：哈希效率要高，即使很长的输入参数也能快速计算出哈希值。
- 可确定性 ：哈希过程必须是确定性的，这意味着对于给定的输入值，它必须始终生成相同的哈希值。
- 雪崩效应 ：微小的输入值变化也会让输出值发生巨大的变化。
- 不可逆 ：从哈希函数的输出值不可反向推导出原始的数据。
哈希冲突
重复一遍，哈希函数是将任意大小的数据映射到固定大小值的函数。那么，我们可以预见到，即使哈希函数设计得足够优秀，几乎每个输入值都能映射为不同的哈希值。但是，当输入数据足够大，大到能超过固定大小值的组合能表达的最大数量数，冲突将不可避免！（参见抽屉原理）
抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。抽屉原理有时也被称为鸽巢原理。
如何解决哈希冲突
比较常用的Has冲突解决方案有链地址法和开放寻址法。
在讲链地址法之前，先说明两个概念。
- 哈希桶。哈希桶（也称为槽，类似于抽屉原理中的一个抽屉）可以先简单理解为一个哈希值，所有的哈希值组成了哈希空间。
- 装载因子。装载因子是表示哈希表中元素的填满程度。它的计算公式：装载因子=填入哈希表中的元素个数/哈希表的长度。装载因子越大，填入的元素越多，空间利用率就越高，但发生哈希冲突的几率就变大。反之，装载因子越小，填入的元素越少，冲突发生的几率减小，但空间浪费也会变得更多，而且还会提高扩容操作的次数。装载因子也是决定哈希表是否进行扩容的关键指标，在java的HashMap的中，其默认装载因子为0.75；Python的dict默认装载因子为2/3。
链地址法
链地址法的思想就是将映射在一个桶里的所有元素用链表串起来。
下面以一个简单的哈希函数 H(key) = key MOD 7（除数取余法）对一组元素 [50, 700, 76, 85, 92, 73, 101] 进行映射，通过图示来理解链地址法处理Hash冲突的处理逻辑。
链地址法解决冲突的方式与图的邻接表存储方式在样式上很相似，发生冲突，就用单链表组织起来。
开放寻址法
对于链地址法而言，槽位数m与键的数目n是没有直接关系的。但是对于开放寻址法而言，所有的元素都是存储在Hash表当中的，所以无论任何时候都要保证哈希表的槽位数m大于或等于键的数据n（必要时，需要对哈希表进行动态扩容）。
开放寻址法有多种方式：线性探测法、平方探测法、随机探测法和双重哈希法。这里以线性探测法来帮助读者理解开放寻址法思想。
- 线性探测法
设 Hash(key) 表示关键字 key 的哈希值， 表示哈希表的槽位数（哈希表的大小）。
线性探测法则可以表示为：
如果 Hash(x) % M 已经有数据，则尝试 (Hash(x) + 1) % M ;
如果 (Hash(x) + 1) % M 也有数据了，则尝试 (Hash(x) + 2) % M ;
如果 (Hash(x) + 2) % M 也有数据了，则尝试 (Hash(x) + 3) % M ;
……
我们同样以哈希函数 H(key) = key MOD 7 （除数取余法）对 [50, 700, 76, 85, 92, 73, 101] 进行映射，通过图示来理解线性探测法处理 Hash 碰撞。
其中，empty代表槽位为空，occupied代表槽位已被占（后续映射到该槽，则需要线性向下继续探测），而lazy delete则代表将槽位里面的数据清除，并不释放存储空间。
两种解决方案比较
对于开放寻址法而言，它只有数组一种数据结构就可完成存储，继承了数组的优点，对CPU缓存友好，易于序列化操作。但是它对内存的利用率不如链地址法，且发生冲突时代价更高。当数据量明确、装载因子小，适合采用开放寻址法。
链表节点可以在需要时再创建，不必像开放寻址法那样事先申请好足够内存，因此链地址法对于内存的利用率会比 开方 寻址法高。链地址法对装载因子的容忍度会更高，并且适合存储大对象、大数据量的哈希表。而且相较于开放寻址法，它更加灵活，支持更多的优化策略，比如可采用红黑树代替链表。但是链地址法需要额外的空间来存储指针。
值得一提的是，在Python中dict在发生哈希冲突时采用的开放寻址法，而java的HashMap采用的是链地址法。
