散列表

散列技术是记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字key对应一个存储位置。这种对应关系又称为散列函数，或者哈希函数。采用散列技术将记录存储在一块连续的存储空间中，这款连续存储空间成为散列表或者哈希表。
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。
可以说，如果没有数组，就没有散列表。
散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

散列表查找步骤：

1.在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录
2.当查找记录时，我们ton过同样的散列函数计算机路的散列地址，按此散列地址访问该记录。

散列函数的构造方法：

1.直接定址法：f(key) = a*key + b 适合查找表较小且连续的函数
2.数字分析法：使用关键字的一部分来计算散列存储位置。适合处理关键字位数比较大的情况，关键字的若干位分布均匀
3.平方取中法：例1234->1522756，中间三位为227，可做散列地址。适合于不知道关键字的分布，位数又不是很大的情况
4.折叠法：将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
关键字位数较多时。
5.除留余数法：f(key)=key%p
6.随机数法：取关键字的随机函数值为散列地址，关键字长度不等时。

散列冲突：

两个关键字key1 !=key2，但却有f(key1) = f(key2)，这种现象称为冲突。，并把key1和key2称为这个散列函数的同义词。

处理散列冲突的方法：

1.开放地址法：一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
f(key) =(f(key)+d) % m
当d=1,2,3,4,5...，称为线性探测法
当d=1的平方，2的平方...，称为二次探测法
当d采用随机函数计算得到，称为随机探测法一个散列函数计算。
2.再散列函数法：每当发生散列地址冲突时，就换一个散列函数计算。
3.链地址法：将so有关键字为同义词的记录存储在一个单链表中。
4.公共溢出区法：将有冲突的关键字建立一个公共的溢出区来存放。