Hash一般被翻译为哈希，也被称为散列。

给定一个数据元素，其关键字为key，按照一个确定的哈希函数Hash计算出hash(key)，把hash(key)作为关键字key对应元素的存储地址（或称哈希地址），再进行数据元素的插入和检索操作。

哈希表是具有固定大小的数组。
并不能保证每个元素的关键字与函数值是一一对应的，有可能不同的元素值，计算出相同的函数值。因此需要进行冲突处理。

常用的函数函数构建方法

（1）直接寻址法
取关键字或关键字的某个线性函数值为散列地址。

即h（key）=key或h（key）=a·key+b，其中a和b均为整型常数，这种散列函数叫做自身函数。

例如，有一个人口数字统计表，人的年龄取值范围为1～100岁，其中，年龄作为关键字，哈希函数取关键字自身，但这种方法效率比较低，时间复杂度为O（1），空间复杂度为O（n），n为关键字的个数。

直接寻址法不会产生冲突，但由于它没有压缩映象，因此当关键字集合很大时，使用这种Hash函数是不可能实现地址编码的散列的。

（2）取模法
选择一个合适的正整数p，令hash（Key）=Keymod p。
p如果选择的是比较大的素数，则效果比较好，一般选取p为TableSize，即哈希表的长度。

（3）数字分析法

（4）折叠法

（5）平方取中法

（6）除留余数法

（7）随机数法

解决冲突办法

（1）开发地址法
基本思想：当发生地址冲突时，在哈希表中按照某种方法继续探测其他的存储地址，直到找到空闲的地址为止。

（2）链地址法
基本思想：链地址法解决冲突的主要思想：如果哈希表空间为[0，m-1]，则设置一个由m个指针组成的一维数组CH[m]，然后在寻找关键字哈希地址的过程中，所有哈希地址为i的数据元素都插入到头指针为CH[i]的链表中。这种方法比较适合于冲突比较严重的情况下使用。

（3）再散列法
当发生冲突时，使用第二个、第三个哈希函数计算地址，直到无冲突时。但这种方法的缺点是计算时间会大幅增加。

（4）建立一个公共溢出区
假设哈希函数的值域为[0，m-1]，则设向量HashTable[0，…，m-1]为基本表，另外设立存储空间向量OverTable[0，…，v]用以存储发生冲突的记录。

总结

Hash主要是用来进行“快速存取”，在O（1）时间复杂度里就可以查找到目标元素，或者判断其是否存在。

Hash数据结构里的数据对外是杂乱无序的，无法得知其具体存储位置，也不知道各个存储元素位置之间的相互关系，但是却可以在常数时间里判断元素位置及存在与否。

在海量数据处理中，使用Hash方法一般可以快速存取、统计某些数据，将大量数据进行分类。例如，提取某日访问网站次数最多的IP地址等。