散列表hash

0x00 问题引入

​ 编译器在对变量进行管理的时候，需要插入 查找、删除、变量，以变量的名字 字符串为关键字进行管理，是一个动态查找问题。

​ 目前已经指导的查找方法有 1遍历 2二分查找 3查找树/平衡二叉树 。

​ 遍历太慢了 O(n) 二分查找是静态查找O(logn) 平衡二叉树O(logn)但是平衡二叉树关键字树数字，容易比较，而字符串不容易比较。

​ 查找的本质：已知对象找位置 ，思路1 有序(全序 半序)安排对象，然后按照顺序找 思路2 直接算出对象的位置，也就是散列 hash

​ 散列查找的两项基本工作：1计算位置:构造散列函数确定关键字储存的位置，2解决冲突：应用某种策略解决两个对象的位置冲突。

0x01 散列表的抽象数据结构

散列表举例

字符串为关键字

0x02 数字散列函数构造方法

​ 一个好的散列函数应该考虑以下两个因素：

​ 1 计算简单以提高转换速度 2关键词对应的地址空间分布均匀，以尽量减少冲突，提高空间利用率

​ 数字关键词的散列函数构造

​ 1直接定址法：去关键字的某个线性函数为散列地址

​ 2除留余数法（最常用的）：数对p进行取余，p一般取表的大小

​ 3数字分析法：分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址

​ 4折叠法，把关键字分割成数位相同的几个部分然后叠加

​ 5平方取中法，先对数字平方 再取中间几位（目的是希望地址能被更多位影响）

0x03 字符关键词的散列函数构造

​ 1最简单的ascill码求和法 ascill码求和然后对表长p取余

​ 2 简单的改进 前三个字符位移法 ，将前三个字符当作27尽职数然后求和

​ 3好的散列函数 位移法 将所有字符看成32进制数（不是27 因为32可以位运算 比较快），可以看成级数的和

实现方法：