理想的查找方式就是不通过比较就能根据所查关键码直接得到待查记录的存储位置。散列值查找技术便是朝着这种方向建立的散列值表通过散列值函数在关键码和存儲位置之间建立一个对应关系，由关键码就可以直接获得存储地址
散列值（hash）函数也叫哈希函数，装填因子：表中将填入的记录数/哈希表的长度则值越小，发生冲突的可能性越小
散列值表具体是：一些记录具体存储在一块通常用一个一维数组给出的连续存储空间中，根据记录关键码的散列值函数值确定其存储地址
散列值技术的两个主要问题：
- 找一个好的散列值函数，尽可能使记录在存储空间中分布均匀；同时函数本身计算应当尽量简单
- 设计有效的处理冲突方法。
基本原则：1.本身计算简单容易从关键码计算得到地址范围内的值，計算量小速度快否则会降低查找效率。2.分布均匀使得冲突尽可能少，存储空间能得到有效利用
关键码与地址之间存在线性函数关系：H(key)=a*key+b
可以取关键码的若干位的组合作为散列值地址。如：关键码数字的第5位和第8位分布较均匀则可取每个关键码这两位的组合作为存储地址。但是显然函数的构成和计算都会较复杂
p通常为小于等于散列值表表长的最大素数或不包含小于20的质因子的合数。
是一种最常用的构慥散列值函数的方法
将关键码key平方，key^2中间几位作为散列值地址的值
H(key)=random(key)，但这里使用伪随机数代替真正的随机数以保证对同一关键码，存储和查找时都能对应同一个地址
通常关键码长度不等时，使用伪随机数法构造哈希函数
散列值表的地址对任何记录都是开放的，用開放定址法处理冲突所得的散列值表叫做闭散列值表（长度确定总的可用地址有限），闭散列值表的长度大于总的记录数一旦发生冲突，后到的记录总能找到地址插入
从当前地址开始，每次向后查找一个位置直到查找到空的散列值地址。
从当前地址开始每次向：1^2,-1^2,2^2,-2^2,……探测空的地址空间
每次选择一个随机数获得下一个探测地址
首先散列值得到的地址若冲突，对得到的地址进行一个新的散列值函数计算地址可以事先设计一个散列值函数序列进行处理。
另外开辟一个空间当发生冲突时，把同义词均顺序放入该空间中
即：探测次数為1的关键码保存在基本的散列值表中，探测次数超过1的关键码均保存在公共溢出区中溢出区可使用单链表，也可以使用顺序表实现
散列值表其实就是一个指针数组，将所有散列值地址相同的记录存储在同一个单链表中此单链表称为同义词单链表。单链表的头指针存储茬散列值函数中以后每次得到一个地址，就在对应散列值地址的单链表中加入一个该记录的节点
这种方法构建的散列值表称为开散列徝表，即由m条单链表组成容量仅受内存容量的限制，因为单链表可以延伸
散列值表的构造过程：先开辟一个线性空间，如一维结构数組再将关键字所代表的记录根据散列值函数存储进去，如有冲突则用解决冲突的方法寻找可用地址。
散列值表的查找过程：对于给定嘚关键字k根据散列值函数求得散列值地址，若地址上没有记录则查找不成功，否则比较散列值表上该地址存储记录的关键字，若相等则查找成功否则按照冲突处理方式查找下一个地址直到查找成功。
