本博文来源于浙江大学《数据结构》。 散列是重要的检索方法。 其基本思想是：以数据对象的关键字key为自变量，根据确定的函数关系h计算相应的函数值h(key )，解释为存储数据对象的目的地，据此存储，即“存储目的地=h(key )”
散列表的定义是在搜索数据对象时，计算从函数h给出的值key的地址，并将key与该地址单元内的数据对象密钥进行比较来确定搜索是否成功。 因此，散列法也称为“关键字-地址转换法”。散列方法中使用的计算函数称为散列函数（也称哈希函数），按这个思想构造的表称为散列表，所以它是一种存储方法。
装填因子一般来说，假设散列表的空间大小为m，填入表中的元素个数为n，则=n/m称为散列表的装填因子。 例如，尺寸为17，元素为11，装填因子为0.65。 实用上，一般散列表的大小设计为=0.5~0.8较好。
同义词映射到同一哈希地址的关键字称为同义词
如何构建散列函数“好”散列函数通常需要考虑以下两个因素：
计算简单，可以提高转换速度，使对应关键词的地址空间分布均匀，将冲突抑制在最小限度。 也就是说，对于关键词集合中的任何关键词，通过哈希函数映射到地址集合中的任何地址的概率都几乎相等。 数字关键字的哈希结构直接寻址法
这类函数计算简单、分布均匀、不发生冲突，但由于要求地址集合和关键字集合的大小相同，不适用于大的关键字集合。 所以在现实应用中很少使用
蒸馏剩余法在现实应用中常用的方法是蒸馏剩余法。 选择tablesize (假设选择tablesize，通常由关键字集合的大小n和允许的最大填充因子决定，通常tablesize为n/)散列表的长度，选择正整数p=TableSize，哈哈
h(key )=key mod p即把关键词除以p的馀数作为散列地址。 使用除数剩余法，选择合适的p很重要，一般选择哈希表长度TableSize以下的任意一个最大素数比较好。 素数求出的馀数作为散列地址，很有可能比较均匀地分布在整个地址空间中。
数字分析法
该方法的核心是利用数字的随机部分生成哈希值
对于字符串的哈希函数结构字符串型关键字，由于字符串比较比整数比较成本更高，通过哈希函数计算将字符串映射到整数后进行比较也是哈希方法的一个优点。
ASCII码加法
该方法的核心是将ascii码字符和散列表的长度作为mod，冲突明显。 例如，tea和eat的单词即使改变位置，散列值也是相同的。
前三个字符移位法
忽略空白字符，前三位所有可能的不同组合有26^3=17 576种，TableSize=10 007似乎是个不错的选择，但英语单词也有规则，最多000种转换、填充因子太小，浪费。因此，虽然很容易计算，但是当散列表太大的时候，这个函数还是不合适的。
移位法
在这个方法中，因为对所有的字符进行移位和散列化，所以如果高位的溢出。一般用这种方法时，是不使用整个字符串，而是从中选择若干有代表性的字符进行映射。例如字符串的长度大于12，则容易只选择奇数位置的字符来实现散列函数。
处理冲突的方法开放地址法
选择di的方法如下
线性检测
插入的时候，最尴尬的是30，取11和模型的话就是8。 也就是这个位置。 因为保存29的时候是和7发生冲突的时候，所以应该有30个村子的地方，后面冲突不断，最后30只能去1。 非常刺痛我的心。 这样的线性检测会带来一定的麻烦。可能会出现很多元素在相邻的散列地址上“堆积”起来的现象，会大大降低查找效率。解决这样问题的方法是采用其它检测方法。
平方检测法
使用平方勘探，研究人员已经给出了强有力的理论保证，也就是：如果散列表长度TableSize是某个4k+3(k是正整数)形式的素数时，平方探测法就可以探查到整个散列表空间。
大家不要轻视这个结论。 我们先学到最多的是排线。 整个横移是我们的理想状况。 能够进行平方检测，表示使用它这两个词。
双散列检测法
采用双散列检测法会增加每次检测的乘法和除法，但期望的检测次数相对较少，理论上很有吸引力。
再哈希法英文名(Rehashing )，这正如幸福的Preflance老师的stl立面所述，该方法是解决装填因子过大的情况，解决方法是将哈希表扩大两倍，将减少一半。 这个过程称为再散列。 在需要这样的扩展的情况下，有可能发生实时系统的停顿，所以在必须是实时的情况下需要“分离链接法”
分离链路法
制作m个起始节点的空链表，将哈希地址的位I的所有关键词插入Head[i]指向的单链表。 插入时，新元素将插入到标题中。 这不仅是为了方便，而且是因为新插入的元素最有可能被访问。 这将加快在单链表中顺序搜索的速度。
散列表的性能分析散列表主要涉及检索，避免冲突是他需要解决的问题，测量性能也由此分析，影响会发生冲突
多少有以下三个因素： 散列函数是否均匀处理冲突的方法散列表的装填因子α 线性探测法的查找性能 平方探测法和双散列探测法的查找性能 分离链接法查找性能 期望探测次数与装填因子α的关系
当装填因子α<0.5的时候，各种探测法的期望探测次数都不大，也比较接近。
随着α的增大，线性探测法的期望探测次数增加较快，不成功查找和插入查找的期望探测次数比成功的期望探测次数要大。因此合理的最大装入因子α应该不超过0.85