哈希

哈希就是为了把一些很大值去对应一个较小的键，然后便于查找和存储的一种数据结构，基于二维数组实现

解决哈希冲突的方法

开放寻址法：find，insert，取模后不断去寻找第一个空位，找不到就去找下一个，找完了就从头再找

拉链法：同一个下标不存一个值，通过链表存多个映射过来的值（c++stl）

1——const表示定义的数组长度L不变

6——定义了指针数组nodes，每一位都是一个初始为空的指针（在完整的代码中，会定义一个**变量名来指向第一个指针

逻辑1：p对应的是nodes的下标，k和v都是用户自定义的值。通过L把k转化为了p，用p找到了k对应在数组中的位置，k和v都存在数组的同一位中（这个数组nodes是自定义过的结构体数组，它不像普通数组一样只有一个值和下标，他每一位都是一个Node结构体，分别有key，val，*next这三个东西）（正确）

逻辑2：拉链法存hash的话，是不是就不会有同一个key取模后的结果存在两个不同的数组元素中的，即使这个数组有空，是不是一定会在同一个数组中一个元素开出的链表里，有之前没有的key取模结果后，才再占用数组中的一个元素（正确）

链表+红黑树法：略（Java的实现）

哈希表长度的选择

避免大量的数字被映射到同一个位置，导致拉链过长

mt19937_64 rnd(time(0)); // 随机数生成器

mt19937_64，#include<random>

rnd是变量名

time，随机数种子，#include<ctime>

扰动的是原始输入的key，所有的key都通过同一个值（那个静态随机数）去变化为另一个值，这个扰动就是异或运算，“同一个值”指的是那个随机数。

下面一种方法解决取模较慢的问题

2的k次方数+高位扰动

当且仅当 L = 2^k 时，它的二进制有且仅有一个 1，后面跟着 k 个 0：

这个数减去一之后，他的二进制就是在第k位到最后都是一，第k位之前都是1

还可以设置更多的随机数：

重哈希

动态调整哈希长度

STL中的hash

将一个数据类型通过计算转化为一个64位无符号整数size_t

再次对重载和匿名函数进行学习