一、哈希表（散列表）
关键字映射到位置
数组 + 链表实现
恒等函数 ：H（key)=key
除留余数法 ：H（key)=key%p ( p为表长最大质数 ）
a ( 装填因子 ）=n(表中元素）/m(表长）=0.75 //用0.75求表长
直接定地址法 ：H（key)=key 或 H (key) =a*key+b
除留余数法 ：H（key)=key%p ( p为表长最大质数 ）
二、冲突处理-开放定址法
线性探测法
eg
求表长 ： 9/0.75=12
15%11=4；29%11=7；18%11=7（冲突后移放到8） ......
51%11=7（后移到11依旧冲突接着遍历0，1）
ans
查找
eg1 ： 8
eg2 : 48
比较三次，查找失败（空位置也算！！！）
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 数据 | 11 | 51 | 15 | 26 | 29 | 18 | 20 | 40 | 8 | |||
| 查找成功次数 | 1 | 7 | 1 | 2 | 1 | 2 | 1 | 4 | 4 | |||
| 查找失败次数 | 3 | 2 | 1 | 1 | 3 | 2 | 1 | 8 | 7 | 6 | 5 | 不存在 |
ASL-Average Search Length (平均查找长度）
ASL成功=（1+7+1+2+1+2+1+4+4）/9 =23/9
ASL失败=（3+2+1+1+3+2+1+8+7+6+5）/11=39/11
0要到2才算失败，查找3次
删除
打标记DEL（设置成-1） 后续可以插入
平方探测法
冲突时候按照 +1^2,-1^2,+2^2,-2^2,+3^2,-3^2……顺序进行探测（表尾后面是表首）
表长=某个4k+3的质数（k为正整数）
17时候，在3发生冲突，先看3+1=4冲突，再看3-1=2；
24时候在3冲突，先看3+1=4冲突，看3-1=2冲突，看2+4=7就是0不冲突
三、冲突处理-拉链法
所有同义词用单链表（头插法）串起来
ASL成功=（1*7+2*3+3*1）/11=16/11
ASL失败=（0+0+1+2+3+1+0+2+0+1+0+0+1）/13=11/13
可以直接删除！！！
四、代码(做题遇到的）
1.unordered_map<key,value> mp
eg ：unordered_map<int,int> mp; //无序哈希表，查找平均素的O（1）
unordered_map:C++的无序哈希表容器
作用：存【键-值 对】key->value，就像字典
第一个int：key的类型，存key数值
第二个int：value的类型，存value的数组下标
mp:变量名字 mp[数值]=下标
2.mp.find(need)!=mp.end().find(); //查找key,找到返回迭代器，找不到返回 .end（）含义；
mp.find(寻找key)
若哈希表存在need,返回一个迭代器，指向键值对；
若哈希表不存在need，返回特殊值mp.end()
//mp.end() 不是哈希表里面元素，是一个“末尾标记”，表示找遍了没找到
3.mp[nums[i]]=i; //把当前数字作为key，下标作为value放进哈希表
