哈希表等于Map吗
首先，我需要先阐明一个初学者很容易犯的概念错误。
请问，哈希表和我们常说的 Map（键值映射）是不是同一个东西？不是。
这一点用 Java 来讲解就很清楚，Map 是一个 Java 接口，仅仅声明了若干个方法，并没有给出方法的具体实现：
interface Map {
V get(K key);
void put(K key, V value);
V remove(K key);
// ...
}
Map 接口本身只定义了键值映射的一系列操作，HashMap 这种数据结构根据自身特点实现了这些操作。还有其他数据结构也实现了这个接口，比如 TreeMap、LinkedHashMap 等等。
换句话说，你可以说 HashMap 的 get, put, remove 方法的复杂度都是 O(1) 的，但你不能说 Map 接口的复杂度都是 O(1) 。因为如果换成其他的实现类，比如底层用二叉树结构实现的 TreeMap，这些方法的复杂度就变成 O(logN) 了。
我为什么要强调这一点呢？主要是针对使用非 Java 语言的读者。
其他编程语言可能没有 Java 这么清晰的接口定义，所以很容易让读者把哈希表和 Map 键值对混为一谈，听到键值对操作，就认为其增删查改的复杂度一定是 O(1) 。这是不对的，具体要看这个底层的数据结构是如何实现键值操作的。
那么这一章节我会带大家动手实现一个哈希表，探讨哈希表为什么能做到增删查改 O(1) 复杂度，以及解决哈希冲突的两种办法。
哈希表的基本原理
几句话就能解释清楚
哈希表可以理解为一个加强版的数组。
数组可以通过索引在 O(1) 的时间复杂度内查找到对应元素，索引是一个非负整数。
哈希表是类似的，可以通过 key 在 O(1) 的时间复杂度内查找到这个 key 对应的 value。key 的类型可以是数字、字符串等多种类型。
怎么做的？特别简单，哈希表的底层实现就是一个数组（我们不妨称之为 table）。它先把这个 key 通过一个哈希函数（我们不妨称之为 hash）转化成数组里面的索引，然后增删查改操作和数组基本相同：
// 哈希表伪码逻辑
class MyHashMap {
private Object[] table;
// 增/改，复杂度 O(1)
public void put(K key, V value) {
int index = hash(key);
table[index] = value;
}
// 查，复杂度 O(1)
public V get(K key) {
int index = hash(key);
return table[index];
}
// 删，复杂度 O(1)
public void remove(K key) {
int index = hash(key);
table[index] = null;
}
// 哈希函数，把 key 转化成 table 中的合法索引
// 时间复杂度必须是 O(1)，才能保证上述方法的复杂度都是 O(1)
private int hash(K key) {
// ...
}
}
具体实现上有不少细节需要处理，比如哈希函数的设计、哈希冲突的处理等等。但你只要明白了上面的核心原理，就已经成功了一半了，剩下的就是写代码了，这有何难呢？
下面我们来具体介绍一下上述增删查改过程中几个关键的概念和可能出现的问题。
几个关键概念及原理
key是唯一的，value可以重复
哈希表中，不可能出现两个相同的 key，而 value 是可以重复的。
明白了上面讲的原理应该很好理解，你直接类比数组就行了：
数组里面每个索引都是唯一的，不可能说你这个数组有两个索引 0。至于数组里面存什么元素，随便你，没人 care。
所以哈希表是一样的，key 的值不可能出现重复，而 value 的值可以随意。
哈希函数
哈希函数的作用是把任意长度的输入（key）转化成固定长度的输出（索引）。
你也看到了，增删查改的方法中都会用到哈希函数来计算索引，如果你设计的这个哈希函数复杂度是 O(N)，那么哈希表的增删查改性能就会退化成 O(N)，所以说这个函数的性能很关键。
这个函数还要保证的一点是，输入相同的 key，输出也必须要相同，这样才能保证哈希表的正确性。不能说现在你计算 hash("123") = 5，待会儿计算 hash("123") = 6，这样的话哈希表就废了。
那么哈希函数是如何把非整数类型的 key 转化成整数索引的？又是如何保证这个索引是合法的呢？
如何把 key 转化成整数
这个问题可以有很多种答案，不同的哈希函数设计会有不同的方法，我这里就结合 Java 语言说一个简单的办法。其他编程语言也是类似的，可以参考这个思路，查询相关的标准库文档。
任意 Java 对象都会有一个 int hashCode() 方法，在实现自定义的类时，如果不重写这个方法，那么它的默认返回值可以认为是该对象的内存地址。一个对象的内存地址显然是全局唯一的一个整数。所以我们只要调用 key 的 hashCode() 方法就相当于把 key 转化成了一个整数，且这个整数是全局唯一的。
当然，这个方法也有一些问题，后续讲解，但现在至少找到了一种把任意对象转化为整数的方法。
如何保证索引合法
hashCode 方法返回的是 int 类型，首先一个问题就是，这个 int 值可能是负数，而数组的索引是非负整数。
那么你肯定想这样写代码，把这个值转化成非负数：
int h = key.hashCode();
if (h < 0) h = -h;
但这样有问题，int 类型可以表示的最小值是 -2^31，而最大值是 2^31 - 1。所以如果 h = -2^31，那么 -h = 2^31 就会超出 int 类型的最大值，这叫做整型溢出，编译器会报错，甚至产生不可预知的结果。
为什么 int 的最小值是 -2^31，而最大值是 2^31 - 1？这涉及计算机补码编码的原理，简单说，int 就是 32 个二进制位，其中最高位（最左边那位）是符号位，符号位是 0 时表示正数，是 1 时表示负数。现在的问题是，我想保证 h 非负，但又不能用负号直接取反。那么一个简单直接的办法是利用这种补码编码的原理，直接把最高位的符号位变成 0，就可以保证 h 是非负数了：
int h = key.hashCode();
// 位运算，把最高位的符号位去掉
// 另外，位运算的运行速度也会比一般的算术运算快
// 所以你看标准库的源码，能用位运算的地方它都会优先使用位运算
h = h & 0x7fffffff;
// 这个 0x7fffffff 的二进制表示是 0111 1111 ... 1111
// 即除了最高位（符号位）是 0，其他位都是 1
// 把 0x7fffffff 和其他 int 进行 & 运算之后，最高位（符号位）就会被清零，即保证了 h 是非负数
关于补码编码的原理我这里就不详细展开了，有兴趣的话你可以自己搜索学习一下。
好的，上面解决了 hashCode 可能是负数的问题，但还有一个问题，就是这个 hashCode 一般都很大，我们需要把它映射成 table 数组的合法索引。
这个问题对你来说应该不难吧，我们之前在 环形数组原理及实现 里面用 % 求模运算来保证索引永远落在数组的合法范围内。所以这里也可以用 % 运算来保证索引的合法性，完整的 hash 函数实现如下：
int hash(K key) {
int h = key.hashCode();
// 保证非负数
h = h & 0x7fffffff;
// 映射到 table 数组的合法索引
return h % table.length;
}
当然，直接使用 % 也有问题，因为 % 这个求余数的运算比较消耗性能，一般在追求运行效率的标准库源码中会尽量避免使用 % 运算，而是使用位运算提升性能。
不过本章主要目的是带你理解实现一个简单的哈希表，就忽略这些细节优化了。有兴趣的话你可以去看一下 Java HashMap 的源码，看看它是如何实现这个 hash 函数的。
哈希冲突
上面给出了 hash 函数的实现，那么你肯定也会想到，如果两个不同的 key 通过哈希函数得到了相同的索引，怎么办呢？这种情况就叫做「哈希冲突」。
哈希冲突是否可以避免？
哈希冲突不可能避免，只能在算法层面妥善处理出现哈希冲突的情况。
哈希冲突是一定会出现的，因为这个 hash 函数相当于是把一个无穷大的空间映射到了一个有限的索引空间，所以必然会有不同的 key 映射到同一个索引上。
就好比三维物体映射到二维影子一样，这种有损压缩必然会出现信息丢失，有损信息本就无法和原信息一一对应。
出现哈希冲突的情况怎么解决？两种常见的解决方法，一种是拉链法，另一种是线性探查法（也经常被叫做开放寻址法）。名字听起来高大上，说白了就是纵向延伸和横向延伸两种思路嘛：
拉链法相当于是哈希表的底层数组并不直接存储 value 类型，而是存储一个链表，当有多个不同的 key 映射到了同一个索引上，这些 key -> value 对儿就存储在这个链表中，这样就能解决哈希冲突的问题。
而线性探查法的思路是，一个 key 发现算出来的 index 值已经被别的 key 占了，那么它就去 index + 1 的位置看看，如果还是被占了，就继续往后找，直到找到一个空的位置为止。
比方说上图，key 的插入顺序是 k2, k4, k5, k3, k1，那么哈希表底层就会变成这样：
这里先讲一下原理，后面的章节我会手把手带大家分别实现这两种方法来解决哈希冲突。
扩容和负载因子
相信大家都听说过「负载因子」这个专业术语，现在你明白了哈希冲突的问题，就能理解负载因子的意义了。拉链法和线性探查法虽然能解决哈希冲突的问题，但是它们会导致性能下降。
比如拉链法，你算出来 index = hash(key) 这个索引了，结果过去查出来的是个链表，你还得遍历一下这个链表，才能在里面找到你要的 value。这个过程的时间复杂度是 O(K)，K 是这个链表的长度。
线性探查法也是类似的，你算出来 index = hash(key) 这个索引了，你去这个索引位置查看，发现存储的不是要找的 key，但由于线性探查法解决哈希冲突的方式，你并不能确定这个 key 真的不存在，你必须顺着这个索引往后找，直到找到一个空的位置或者找到这个 key 为止，这个过程的时间复杂度也是 O(K)，K 为连续探查的次数。
所以说，如果频繁出现哈希冲突，那么 K 的值就会增大，这个哈希表的性能就会显著下降。这是我们需要避免的。那么为什么会频繁出现哈希冲突呢？两个原因呗：
1、哈希函数设计的不好，导致 key 的哈希值分布不均匀，很多 key 映射到了同一个索引上。
2、哈希表里面已经装了太多的 key-value 对了，这种情况下即使哈希函数再完美，也没办法避免哈希冲突。
对于第一个问题没什么好说的，开发编程语言标准库的大佬们已经帮你设计好了哈希函数，你只要调用就行了。对于第二个问题是我们可以控制的，即避免哈希表装太满，这就引出了「负载因子」的概念
负载因子
负载因子是一个哈希表装满的程度的度量。一般来说，负载因子越大，说明哈希表里面存储的 key-value 对越多，哈希冲突的概率就越大，哈希表的操作性能就越差。
负载因子的计算公式也很简单，就是 size / table.length。其中 size 是哈希表里面的 key-value 对的数量，table.length 是哈希表底层数组的容量。
你不难发现，用拉链法实现的哈希表，负载因子可以无限大，因为链表可以无限延伸；用线性探查法实现的哈希表，负载因子不会超过 1。像 Java 的 HashMap，允许我们创建哈希表时自定义负载因子，不设置的话默认是 0.75，这个值是经验值，一般保持默认就行了。
当哈希表内元素达到负载因子时，哈希表会扩容。和之前讲解 动态数组的实现 是类似的，就是把哈希表底层 table 数组的容量扩大，把数据搬移到新的大数组中。size 不变，table.length 增加，负载因子就减小了。
为什么不能依赖哈希表的遍历顺序
你大概也听过一个编程常识，即哈希表中键的遍历顺序是无序的，不能依赖哈希表的遍历顺序来编写程序。这是为什么呢？哈希表的遍历本质上就是遍历那个底层 table 数组
// 遍历所有 key 的伪码逻辑
// 哈希表底层的 table 数组
KVNode[] table = new KVNode[1000];
// 获取哈希表中的所有键
// 我们不能依赖这个 keys 列表的顺序
List keys = new ArrayList<>();
for (int i = 0; i < table.length; i++) {
KVNode node = table[i];
if (node != null) {
keys.add(node.key);
}
}
你如果理解了前面讲的内容，应该已经能够理解这个问题了。
首先，由于 hash 函数要把你的 key 进行映射，所以 key 在底层 table 数组中的分布是随机的，不像数组/链表结构那样有个明确的元素顺序。
其次，刚才讲了哈希表达到负载因子时会怎样？会扩容对吧，也就是 table.length 会变化，且会搬移元素。那么这个搬移数据的过程，是不是要用 hash 函数重新计算 key 的哈希值，然后放到新的 table 数组中？而这个 hash 函数，它计算出的值依赖 table.length。也就是说，哈希表自动扩容后，同一个 key 的哈希值可能变化，即这个 key-value 对儿存储在 table 的索引也变了，所以遍历结果的顺序就和之前不一样了。
你观察到的现象就是，这次遍历的第一个键是 key1，但是增删几个元素再遍历，可能发现 key1 跑到最后去了。所以说，这些东西没必要背的，原理搞明白了，你稍微推理下自己都能想通。
为什么不建议在 for 循环中增/删哈希表的key
注意我这里说的是不建议，并不是一定不可以。因为不同的编程语言标准库对哈希表的实现不同，有些语言针对这种情况做了优化，所以到底行不行，要查阅文档。
我们这里仅从哈希表的原理上分析，在 for 循环中增/删哈希表的 key，是很容易出现问题的，原因和上面相同，还是扩缩容导致的哈希值变化。
遍历哈希表的 key，本质就是遍历哈希表底层的 table 数组，如果一边遍历一边增删元素，如果遍历到一半，插入/删除操作触发了扩缩容，整个 table 数组都变了，那么请问，接下来应该是什么行为？还有，在遍历过程中新插入/删除的元素，是否应该被遍历到？扩缩容导致 key 顺序变化是哈希表的特有行为，但即便排除这个因素，任何其他数据结构，也都不建议在遍历的过程中同时进行增删，否则很容易导致非预期的行为。如果你非要这样做，请确保查阅了相关文档，做到心里有数。
key必须是不可变的
