基本原理
哈希表可以理解为一个加强版的数组。数组可以通过索引在 O(1) 的时间复杂度内查找到对应元素，索引是一个非负整数。哈希表是类似的，可以用key在O(1) 的时间复杂度内查找到这个
key对应的value。key的类型可以是数字、字符串等多种类型。其主要原理非常简单，哈希表的底层实现就是一个数组（下文代码table），他先把这个key通过一个哈希函数（hash）转化成数组里边的索引，然后增删改查操作核数组基本相同：
// 哈希表伪码逻辑
class MyHashMap {
private:
vector<void*> table;
public:
// 增/改，复杂度 O(1)
void put(auto key, auto value) {
int index = hash(key);
table[index] = value;
}
// 查，复杂度 O(1)
auto get(auto key) {
int index = hash(key);
return table[index];
}
// 删，复杂度 O(1)
void remove(auto key) {
int index = hash(key);
table[index] = nullptr;
}
private:
// 哈希函数，把 key 转化成 table 中的合法索引
// 时间复杂度必须是 O(1)，才能保证上述方法的复杂度都是 O(1)
int hash(auto key) {
// ...
}
};具体实现上有不少细节需要处理，比如哈希函数的设计、哈希冲突的处理等等。但你只要明白了上面的核心原理，就已经成功了一半了，剩下的就是写代码了。
关键概念
在哈希表中，key是唯一的，value可以重复
哈希表中，不可能出现两个相同的 key，而 value 是可以重复的。
明白了上面讲的原理应该很好理解，你直接类比数组就行了：
数组里面每个索引都是唯一的，不可能说你这个数组有两个索引 0。至于数组里面存什么元素，随便你。所以哈希表是一样的，key 的值不可能出现重复，而 value 的值可以随意。
哈希函数
哈希函数的作用是把任意长度的输入（key）转化成固定长度的输出（索引）。在哈希表的增删查改的方法中都会用到哈希函数来计算索引，如果你设计的这个哈希函数复杂度是 O(N)O(N)，那么哈希表的增删查改性能就会退化成 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数组的合法索引。这个就更好解决了，只需要参考环形数组原理用%求模运算就可以了。
int hash(K key) { int h = key.hashCode(); // 保证非负数 h = h & 0x7fffffff; // 映射到 table 数组的合法索引 return h % table.length; }当然，直接使用
%也有问题，因为%这个求余数的运算比较消耗性能，一般在追求运行效率的标准库源码中会尽量避免使用%运算，而是使用位运算提升性能。
哈希冲突
上面给出了 hash 函数的实现，那么你肯定也会想到，如果两个不同的 key 通过哈希函数得到了相同的索引，怎么办呢？这种情况就叫做「哈希冲突」。
哈希冲突不可能避免，只能在算法层面妥善处理出现哈希冲突的情况。
哈希冲突是一定会出现的，因为这个
hash函数相当于是把一个无穷大的空间映射到了一个有限的索引空间，所以必然会有不同的key映射到同一个索引上。就好比三维物体映射到二维影子一样，这种有损压缩必然会出现信息丢失，有损信息本就无法和原信息一一对应。
出现哈希冲突的情况怎么解决？两种常见的解决方法，一种是拉链法，另一种是线性探查法（也经常被叫做开放寻址法）。 名字听起来高大上，说白了就是纵向延伸和横向延伸两种思路。
拉链法相当于是哈希表的底层数组并不直接存储 value 类型，而是存储一个链表，当有多个不同的 key 映射到了同一个索引上，这些 key -> value 对儿就存储在这个链表中，这样就能解决哈希冲突的问题。
而线性探查法的思路是，一个 key 发现算出来的 index 值已经被别的 key 占了，那么它就去 index + 1 的位置看看，如果还是被占了，就继续往后找，直到找到一个空的位置为止。
扩容和负载因子
拉链法和线性探查法虽然能解决哈希冲突的问题，但是它们会导致性能下降。
比如拉链法，你算出来 index = hash(key) 这个索引了，结果过去查出来的是个链表，你还得遍历一下这个链表，才能在里面找到你要的 value。这个过程的时间复杂度是 O(K)，K 是这个链表的长度。
线性探查法也是类似的，你算出来 index = hash(key) 这个索引了，你去这个索引位置查看，发现存储的不是要找的 key，但由于线性探查法解决哈希冲突的方式，你并不能确定这个 key 真的不存在，你必须顺着这个索引往后找，直到找到一个空的位置或者找到这个 key 为止，这个过程的时间复杂度也是 O(K)，K 为连续探查的次数。
所以说，如果频繁出现哈希冲突，那么 K 的值就会增大，这个哈希表的性能就会显著下降。这是我们需要避免的。
频繁出现哈希冲突的原因有两个：
- 哈希函数设计的不好，导致
key的哈希值分布不均匀，很多key映射到了同一个索引上。- 哈希表里面已经装了太多的
key-value对了，这种情况下即使哈希函数再完美，也没办法避免哈希冲突。
对于第一个问题没什么好说的，开发编程语言标准库的大佬们已经帮你设计好了哈希函数，你只要调用就行了。
对于第二个问题是我们可以控制的，即避免哈希表装太满，这就引出了「负载因子」的概念。
负载因子是一个哈希表装满的程度的度量。一般来说，负载因子越大，说明哈希表里面存储的
key-value对越多，哈希冲突的概率就越大，哈希表的操作性能就越差。负载因子的计算公式也很简单，就是
size / table.length。其中size是哈希表里面的key-value对的数量，table.length是哈希表底层数组的容量。你不难发现，用拉链法实现的哈希表，负载因子可以无限大，因为链表可以无限延伸；用线性探查法实现的哈希表，负载因子不会超过 1。
像 Java 的 HashMap，允许我们创建哈希表时自定义负载因子，不设置的话默认是
0.75，这个值是经验值，一般保持默认就行了。当哈希表内元素达到负载因子时，哈希表会扩容。
为什么不能依赖哈希表的顺序遍历
哈希表中键的遍历顺序是无序的，不能依赖哈希表的遍历顺序来编写程序。
哈希表的遍历本质上就是遍历那个底层 table 数组。
首先，由于
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必须是不可变的
所谓不可变类型，就是说这个对象一旦创建，它的值就不能再改变了。原因：
第一个就是效率问题，每次计算 hashCode 都要遍历整个数组，复杂度是 O(N)，这样就会导致哈希表的增删查改操作的复杂度退化成 O(N)。
第二个原因，hashCode 是根据它里面的元素计算出来的，如果某个元素的 hashCode 值发生改变，那么相应的返回值也会发生改变。也就是说，你存入哈希表的 key-value 意外丢失了，这是非常非常严重的 bug，还会带来潜在的内存泄漏问题。
总结：
1、为什么我们常说，哈希表的增删查改效率都是 O(1)？
因为哈希表底层就是操作一个数组，其主要的时间复杂度来自于哈希函数计算索引和哈希冲突。只要保证哈希函数的复杂度在 O(1)，且合理解决哈希冲突的问题，那么增删查改的复杂度就都是 O(1)。
2、哈希表的遍历顺序为什么会变化？
因为哈希表在达到负载因子时会扩容，这个扩容过程会导致哈希表底层的数组容量变化，哈希函数计算出来的索引也会变化，所以哈希表的遍历顺序也会变化。
3、哈希表的增删查改效率一定是 O(1)O(1) 吗？
不一定，正如前面分析的，只有哈希函数的复杂度是 O(1)，且合理解决哈希冲突的问题，才能保证增删查改的复杂度是 O(1)。
哈希冲突好解决，都是有标准答案的。关键是哈希函数的计算复杂度。如果使用了错误的 key 类型，比如前面用 ArrayList 作为 key 的例子，那么哈希表的复杂度就会退化成 O(N)。
4、为啥一定要用不可变类型作为哈希表的 key？
因为哈希表的主要操作都依赖于哈希函数计算出来的索引，如果 key 的哈希值会变化，会导致键值对意外丢失，产生严重的 bug。