原创 散列技术

        最近在看一些关于索引算法的东西，第一次接触到散列表，以前听说过这个概念但是没有应用到，现在重新来审视这个技术

        首先要从散列表说起，散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存放记录的数组叫做散列表，关键码值通过散列函数得到的象成为散列地址。

        通常散列表的存储空间是一个一维数组，散列地址是数组的下标。构造散列表需关注两个问题：1.选择一个计算简单且冲突少的“均匀”散列函数；2.确定一个解决冲突的方法，以存储产生冲突的同义词。

       以下是几种计算简单且效果好的散列函数

       1）选取关键字中数字分布比较均匀的几位作为散列地址

       2）经关键字平方，然后取中间几位或其组合

       3）关键字位数较多，可将关键字分割成位数相同的几段，然后叠加

       4）选择一个适当的正整数P，用P去除关键字，取所得余数作为地址，一般选P为小于或等于散列表长度M的某个最大素数比较好，该方法最常用

       5）将原关键字看为另一进制上的数，然后转化为原进制，取其中若干位做地址

       6）取关键字的随机函数值作为地址，当关键字长度不等时此法比较恰当

       处理冲突的方法：

      1）开放地址法，思想是如果当前地址发生冲突则按照某种规则查找开放地址，建表前单元全部置空。

      2）拉链法，思想是将所有关键字为同义词的结点链接在同一个单链表中

      只要装填因子选择合适，散列表上的平均查找长度就是一个常数。