哈希表核心原理
首先要明确的是，哈希表和java里的Map键值对不是一个东西，Map是系列接口，哈希表只是利用其数据结构的特点实现了一种Map，除此之外还有TreeMap等。主要是为了解释，不要听见Map就认为他的查询是O(1)，这个得具体看是什么map的实现。
哈希表的基本原理
哈希表可以理解为一个加强版数组。
数组可以通过索引在O(1)的时间复杂度下查找对应的元素，索引是一个非负整数。
哈希表示类似的，可以通过key在O(1)的时间下查找到对应的value。key的类型可以是数字、自负转等多种类型。
hashmap的底层数据结构就是一个数组我们称之为table，首先吧key通过一个哈希函数转化成数组里面的索引，然后增删查改操作基本和数组相同
class MyHashMap{
private:
vector<void*> table;
public:
void put(auto key,auto value){
int index = hash(key);
table[index] = value;
}
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转换为固定长度的索引。
整个哈希表其中一个步骤就是哈希函数，如果哈希函数没有设计好，就会导致整个哈希表的效果都变差，比如，如果哈希函数的时间复杂度是O(n)，就算哈希表查询理论上是O(1),但由于需要加入哈希函数，就会导致哈希表复杂度变O(n)。所以要保证哈希函数复杂度要小，并且要保证同一个值经过哈希函数处理之后索引的值是唯一的，不能出现同一个a被哈希函数处理之后两次结果不一样。
哈希函数的实现方式有很多，这边介绍一下java里的默认的一种方式。任意java对象都会有一个int hashcode（）函数，如果不重写这个方法的话，这个就会默认返回这个对象的内存地址，这个是唯一的，所以如果我们将key的值用hashcode处理之后就可以将它变成一个唯一的整数。
确保索引合法
hashcode方法返回的是int，所以第一问题就是万一返回的是负数会出现很大的问题。如果直接进行取反的操作，会出现另一个问题，因为在二进制里，32位比特位中，最左边的一位是符号位，当符号位为1时为负数，为0时为正数，所以最小可以到达-2^31，但最大时只能到2^31-1 。所以直接取反可能会导致越界问题。于是我们就直接进行与运算。
int h = hashcode();
h = h&0x7fffffff; , h和除了最左边的一位以外都是1的相与，这样h最左边的一位不管怎么样都会变成0。
之后就是要解决如何将索引映射到table里的合法索引，这个时候就可以通过循环数组里的技巧来操作，
int hash(K key){
int h = key.hashcode();
h = h & 0x7ffffff;
return h % table.length;
}
哈希冲突
从刚才说的索引合法性里面的“如何将索引映射到table里的合法索引“这个方法不难看出，我们的索引是容易重复的。比如一个数组里有五个位置，0，1，2，3，4，5.那么如果想将无限可能的数字映射到这五个数字上，我们用上述提到的方法来映射时，就会出现这种情况：我需要映射的值为0，5，10等值时，都会存放在同一个位置a[0]上，这就叫哈希冲突。
哈希冲突是无法避免的，只能通过算法层面尽量规避，所以说hash函数的选取也是减少哈希冲突的方式之一。
那一般解决方式分两种，一是拉链法，二是线性探查法（开放寻址法）。
拉链法
其实就是将冲突的地方纵向延伸，当出现了哈希冲突的时候，多个key映射到同一个数组的位置上时，将多个key连成一个链表来存储。
线性探查法
而线性探查法的思路是，一个 key 发现算出来的 index 值已经被别的 key 占了，那么它就去 index + 1 的位置看看，如果还是被占了，就继续往后找，直到找到一个空的位置为止。
扩容和负载因子
从上面的两个方法可以看出，如果我们采用了这两种方法后，每次inde = hashcode（key）之后，你发现这个value不是你的值时，你不能确定真的没有这个值，你得去遍历这个点的列表（拉链法）或者是遍历这个数组（线性探查法）去确保这个值没有。那这个时候你就需要O（K）的时间复杂度，K为连续探查的次数或者是链表的长度。
所以说如果频繁出现hash冲突，那就会导致k的次数变大，哈希表的效率也会降低。哈希冲突主要由以下两点导致
1、哈希函数设计有问题，导致key的分布不均匀，很多key投射到同一个索引上
2、哈希表里面已经装了太多的key-value对，这种情况下哈希函数再好也会导致冲突
1的话直接调用语言自带的哈希函数就可以了，2的话就要通过负载因子来进行扩容了。
负载因子
负载因子是一个哈希表装满的程度。一般来说负载因子越大说明他的哈希表里面的key-value越多，哈希冲突的可能越大，哈希表的效果就越差。
负载因子计算公式也简单，size/table.length size是哈希表里的key-value对数量，table.length是哈希表底层数组的容量。
我们可以看出来，拉链法实现的哈希表的负载因子可以无限大，因为他的size可以无限延长，而线性探查法的负载因子一般不会超过1，因为他的size最多跟数组长度一样。像 Java 的 HashMap，允许我们创建哈希表时自定义负载因子，不设置的话默认是 0.75，这个值是经验值，一般保持默认就行了。（后续根据进一步学习发现，数组里的键值对如果超过table的size * 0.75就需要扩容，而小于table的size * 0.125时就要缩容）
当哈希表内元素达到负载因子时，哈希表会扩容。和之前的 [动态数组的实现]是类似的，就是把哈希表底层 table 数组的容量扩大，把数据搬移到新的大数组中。size 不变，table.length 增加，负载因子就减小了。
为什么不能依赖哈希表的遍历
首先我们能看出来，根据前面的知识key是通过hash函数获取index，也就是数组下标，从而知道访问对应值的，那就不可能是顺序存储这个key-value。
其次我们刚才知道了，当哈希表达到负载因子就会出发扩容，那扩容之后就会创建一个新的数组，然后把旧的数组的key重新计算然后把对应的value放进新的index对应的位置里面，那么顺序又一次被打破。
为什么不建议for循环中增删哈希表的key
如果在遍历的过程中还往里面进行插入数据的话，那出现的问题就更多了，如果这个哈希表在增删的时候可能会扩/缩容，那就会导致整个table数组都变了，那你的整个key的顺序又再次改变了，那你后面要遍历的可能是你之前遍历过的。比如我一开始已经经过了k节点它的index是4，但是这个时候我往里面增加数据了，触发扩容。新的table的k节点的index在5，那我不就是又一次遍历他，那以前在5的又不知道去哪了，也有可能跑到1，那我就跳过了这个节点。
key必须是不可变的
所谓不可变类型，就是说这个对象一旦创建，它的值就不能再改变了。比如 Java 中的 String, Integer 等类型，一旦创建了这些对象，你就只能读取它的值，而不能再修改它的值了。
作为对比，Java 中的 ArrayList、LinkedList 这些对象，它们创建出来之后，可以往里面随意增删元素，所以它们是可变类型。
因此，你可以把 String 对象作为哈希表的 key，但不能把 ArrayList 对象作为哈希表的 key
以下是将arrylist当作哈希表的对象的后果：
public int hashCode() {
int h = 0;
for (int i = 0; i < elementData.length; i++) {
h = 31 * h + elementData[i];
}
}
第一个就是效率问题，每次计算 hashCode 都要遍历整个数组，复杂度是 O(N)，这样就会导致哈希表的增删查改操作的复杂度退化成 O(N)。
更严重的问题是，ArrayList 的 hashCode 是根据它里面的元素计算出来的，如果你往这个 ArrayList 里面增删元素，或者其中某个元素的 hashCode 值发生改变，那么这个 ArrayList 的 hashCode 返回值也会发生改变。
比方说，你现在用一个 ArrayList 类型的 arr 变量作为哈希表的 key 在哈希表中保存了对应的 value。但如果 arr 中的某个元素在程序的其他位置被修改了，那么 arr 的 hashCode 就会变化。此时你再用这个 arr 变量去哈希表中查询，发现找不到任何值了。
也就是说，你存入哈希表的 key-value 意外丢失了，这是非常非常严重的 bug，还会带来潜在的内存泄漏问题。
public class Test {
public static void main(String[] args) {
// 错误示例
// 把可变类型作为 HashMap 的 key
Map<ArrayList<Integer>, Integer> map = new HashMap<>();
ArrayList<Integer> arr = new ArrayList<>();
arr.add(1);
arr.add(2);
map.put(arr, 999);
System.out.println(map.containsKey(arr)); // true
System.out.println(map.get(arr)); // 999
arr.add(3);
// 出现严重 bug，键值对丢失
System.out.println(map.containsKey(arr)); // false
System.out.println(map.get(arr)); // null
// 此时 map 底层的 table 中，arr 的键值对数据依然存在
// 但是由于 arr 的 hashCode 改变了，此键值对无法被查找到
// 这也会导致内存泄漏，因为这个 arr 变量被 map 引用着，无法被垃圾回收
}
}
拉链法实现哈希表
上面提到过，解决哈希冲突的实现哈希表的方式有两种，一种是拉链法，一种是线性探查法。这里就介绍如何用拉链法实现哈希表。
其实拉链法就是将哈希表底层的table里的每个成员设置成一个链表。如果出现了哈希冲突，就将映射到同一个key的内容放到这个链表里，从而解决哈希冲突。
实现过程
template<typename K,typename V>;
class MychainHashMap{
struct KVNode{
K key;
V value;
KVNode(K key, V val):key(key),value(val);
};
vector<list<KVNode>> table;
int size_; //table里面键值对的个数
static constexpr int INIT_CAP = 4; //初始table的大小
// 哈希函数，将键映射到 table 的索引
int hash(K key) {
return (hash<K>{}(key) & 0x7fffffff) % table.size();
}
void resize(int newcap){
newCap = max(newCap,1); //防止newcap为0，出现取空模的情况。
MychainHashMap<K,V> newMap(newcap);
for(auto &list : table){
for(auto &node : list){
newMap.put(node.key,node.value); //将旧的map里的元素放入新的map里面
}
}
this->table = newMap.table;
}
public:
MyChainHashMap(): MyChainHashMap(INIT_CAP){
}
/*explicit是用于让c++避免使用隐式转换的，因为隐式转换是可以让，
MyChainingHashMap map = 10成立，这样看着很奇怪，因为map不是int类型为啥可以等于10，实际上
他的意思是map =MyChainingHashMap（10），等于是调用了构造函数。这个禁止隐式转换
就必须要求写出构造函数才可以，避免出现误解。 */
explicit MyChainingHashMap(int initCapacity) {
size_ = 0;
// 保证底层数组的容量至少为 1，因为 hash 函数中有求余运算，避免出现除以 0 的情况
initCapacity = max(initCapacity, 1);
table.resize(initCapacity);
}
//增/改
void put(K key,V val){
auto &list = table[hash(key)];
// 如果 key 之前存在，则修改对应的 val
for (auto &node: list) {
if (node.key == key) {
node.value = val;
return;
}
}
// 如果 key 之前不存在，则插入，size 增加
list.emplace_back(key, val);
size_++;
// 如果元素数量超过了负载因子，进行扩容
if (size_ >= table.size() * 0.75) {
resize(table.size() * 2);
}
}
//删
void remove(K key){
auto &list = table[hash(key)];
for(auto it = list.begin();it != list.end; ++it){
if(it->key = key){
list.erase(it);
size_--;
}
if(size_<= table.size/8){
resize(table.size/4);
}
}
}
//查 ，如果有key对应的value，就返回value，没有就返回nullptr
V get(K key){
auto &list = table[hash(key)];
for(auto &node : list){
if(node.key == key){
return node.value;
}
}
return;
}
list<K> keys(){
list<K> keys;
for(const auto &list : table){
for(const auto &node : list){
keys.push_back(node.key);
}
}
return keys;
}
int size() const {
return size_;
}
};