散列表的查找技术
我们学过的查找技术都是通过一系列的给定值与关键码的比較，查找效率依赖于查找过程中进行的给定值与关键码的比較次数。
而散列表的查找不用比較。通过关键码直接确定存储位置。
在存储位置和关键码之间建立一个确定的相应关系。
散列表的基本思想：在记录的存储地址和他的关键码之间建立一个确定的相应关系。
这样。不经过比較，一次读取就能得到所查元素的查找方法。
散列表：採用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。
散列函数：将关键码映射为散列表中适当存储位置的函数。
散列地址：由散列函数所得的存储位置。
比如 ：一组数：12， 37。 52， 43， 84， 99
散列表函数为：H（k） = k%11
散列表：长度为11
散列既是一种查找技术，也是一种存储技术。散列仅仅是通过记录的关键码定位该记录。没有完整的表达记录之间的逻辑关系，所以。散列主要是面向查找的存储结构。
散列技术的关键问题：1、散列函数的设计。怎样设计一个简单、均匀、存储利用效率高的散列函数。
2、冲突的处理。
怎样採用合适的处理冲突方法来解决冲突。
冲突：对于两个不同的关键码Ki != Kj,有H(Ki) = H(Kj),即两个不同的记录须要存放在同一个存储位置。Ki和Kj相对于H称为同义词。
散列函数。设计散列函数一般应遵循下面原则：
1、计算简单。
散列函数不应该有非常大的计算量。否则会减少查找效率。
2、函数值即散列地址分布均匀。
函数值要尽量均匀散布在地址空间，这样才干保证存储空间的有效利用并降低冲突。
（1）、散列函数-直接定址法
散列函数是关键码的线性函数。即H(key) = a *key + b (a、b为常数)
适用情况：事先知道关键码。关键码集合不是非常大且连续性较好。
(2)、散列函数-除留余数法
散列函数为 ： H(key) = key mod p 普通情况下。选p为小于或等于表长（最好接近表长）的最小素数。
适用情况：不要求事先知道关键码的分布。
（3）、散列函数-数字分析法
依据关键码在各个位上的分布情况，选取分布比較均匀的若干位组成散列地址。
适用情况：能预先预计出所有关键码的每一位上各种数字出现的频度，不同的关键码集合须要又一次分析。
（4）、散列函数-平方取中法
对关键码平方后，依照散列表大小，取中间的若干位作为散列地址（平方后截取）
适用情况:实现不知道关键码的分布且关键码的位数不是非常大。
（5）、散列函数-折叠法
将关键码从左到右切割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。
适用情况：关键码位数非常多，事先不知道关键码的分布。
处理冲突的方法-开放定址法
由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址。并将记录存入。
方法：1、线性探測法 2、二次探測法 3、随机探測法