一、基本概念
哈希表（hash table）是一种根据关键字直接访问内存存储位置的数据结构，通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系，建立这种对应关系的函数称为哈希函数。
哈希表
二、哈希表的构造方法
假设要存储的数据元素个数是n，设置一个长度为m(m > n)的连续存储单元，分别以每个数据元素的关键字Ki(0<=i<=n-1)为自变量，通过哈希函数hash(Ki)，把Ki映射为内存单元的某个地址hash(Ki),并将数据元素存储在内存单元中。
从数学的角度看，哈希函数实际上是关键字到内存单元的映射，因此我们希望通过哈希函数通过尽量简单的运算使得哈希函数计算出的哈希地址尽量均匀的被映射到一系列的内存单元中，构造哈希函数有三个要点：（1）运算过程要尽量简单高效，以提高哈希表的插入和检索效率；（2）哈希函数应该具有较好的散列型，以降低哈希冲突的概率；第三，哈希函数应具有较大的压缩性，以节省内存。
（1）直接地址法：以关键字的某个线性函数值为哈希地址，可以表示为hash(K)=aK+C;优点是不会产生冲突，缺点是空间复杂度可能会较高，适用于元素较少的情况
（2）除留余数法：它是由数据元素关键字除以某个常数所留的余数为哈希地址，该方法计算简单，适用范围广，是经常使用的一种哈希函数，可以表示为：
hash(K=K mod C)该方法的关键是常数的选取，一般要求是接近或等于哈希表本身的长度，研究理论表明，该常数选素数时效果最好
（3）数字分析法：该方法是取数据元素关键字中某些取值较均匀的数字来作为哈希地址的方法，这样可以尽量避免冲突，但是该方法只适合于所有关键字已知的情况，对于想要设计出更加通用的哈希表并不适用
三、哈希冲突的解决方案
在构造哈希表时，存在这样的问题：对于两个不同的关键字，通过我们的哈希函数计算哈希地址时却得到了相同的哈希地址，我们将这种现象称为哈希冲突
哈希冲突
哈希冲突主要与两个因素有关
（1）填装因子，填装因子是指哈希表中已存入的数据元素个数与哈希地址空间的大小的比值，a=n/m ; a越小，冲突的可能性就越小，相反则冲突可能性较大；但是a越小空间利用率也就越小，a越大，空间利用率越高，为了兼顾哈希冲突和存储空间利用率，通常将a控制在0.6-0.9之间，而.net中的HashTable则直接将a的最大值定义为0.72 （虽然微软官方MSDN中声明HashTable默认填装因子为1.0，但实际上都是0.72的倍数）
（2）与所用的哈希函数有关，如果哈希函数得当，就可以使哈希地址尽可能的均匀分布在哈希地址空间上，从而减少冲突的产生，但一个良好的哈希函数的得来很大程度上取决于大量的实践。
哈希冲突通常是很难避免的，解决哈希冲突有很多种方法，通常分为两大类：
1.开放地址法：他是一类以发生哈希冲突的哈希地址为自变量，通过某种哈希函数得到一个新的空闲内存单元地址的方法，开放地址法的哈希冲突函数通常是一组
image.png
2.链表法：当未发生冲突时，直接存放数据，当冲突产生时，把产生冲突的数据元素另外存放在单链表中
image.png
网友评论