一、哈希表散列表关键字映射到位置数组 链表实现恒等函数 Hkey)key除留余数法 Hkey)key%p ( p为表长最大质数 a ( 装填因子 n(表中元素/m(表长0.75 //用0.75求表长直接定地址法 Hkey)key 或 H (key) a*keyb除留余数法 Hkey)key%p ( p为表长最大质数 二、冲突处理-开放定址法线性探测法eg求表长 9/0.751215%11429%11718%117冲突后移放到8 ......51%117后移到11依旧冲突接着遍历01ans查找eg1 8eg2 : 48比较三次查找失败空位置也算数组01234567891011数据11511526291820408查找成功次数171212144查找失败次数32113218765不存在ASL-Average Search Length (平均查找长度ASL成功171212144/9 23/9ASL失败32113218765/1139/110要到2才算失败查找3次删除打标记DEL设置成-1 后续可以插入平方探测法冲突时候按照 1^2,-1^2,2^2,-2^2,3^2,-3^2……顺序进行探测表尾后面是表首表长某个4k3的质数k为正整数17时候在3发生冲突先看314冲突再看3-1224时候在3冲突先看314冲突看3-12冲突看247就是0不冲突三、冲突处理-拉链法所有同义词用单链表头插法串起来ASL成功1*72*33*1/1116/11ASL失败0012310201001/1311/13可以直接删除四、代码(做题遇到的1.unordered_mapkey,value mpeg unordered_mapint,int mp; //无序哈希表查找平均素的O1unordered_map:C的无序哈希表容器作用存【键-值 对】key-value就像字典第一个intkey的类型存key数值第二个intvalue的类型存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放进哈希表