哈希表

转载：http://www.jianshu.com/p/54c745beeb08

哈希表无论是在面试中，还是在日常编程中，都有着举足轻重的地位，我们虽然不用完完全全自己去构建一个哈希表的数据结构，但是也应该知道哈希表是什么，它的原理是什么，它有什么好处等等这些内容

哈希表是什么：

对于数组或者是链表的查找，通常都是遍历整个结构，然后判断每一个单元的内容是否和需要查找的内容相符，那么我们就会思考这样一个问题，能不能跳过这些判断，直接得出结果呢，这就是构建哈希表的初衷。 在描述什么是哈希表之前还要引出一个定义，那就是散列技术。散列技术在存储位置和这个存储位置记录的关键字之间建立一个确定的对应关系f，使得每一个关键字key都对应一个存储位置f（key）。f（key）这个函数被称为散列函数，也叫哈希函数。 采用散列技术把关键字存储在一块连续的存储空间中，这块存储空间称为散列表或者哈希表（Hash table），基本结构是一个数组。 哈希表的内部实现步骤

存储时：通过散列函数计算关键字的散列地址，按照这个散列地址将该关键字放入到哈希表中 查找时：同样通过散列函数计算关键字的散列地址，然后通过这个散列地址去访问哈希表中的值 哈希表的利和弊

利： 简化了比较过程，效率大大提高，普通的查找的时间复杂度为O（n），哈希表的查找的时间复杂度为O（1） 弊： 关键字有重复的情况不合适（例如存储一个班的学生将性别作为关键字） 无法进行范围，最大值，最小值等的查找 哈希函数的构造

直接定址法：

例子： 对一个年级的软件工程的期末考试分数0-100分的同学数量进行统计，那么就可以直接用这个关键字作为地址，f（key）= key 函数公式： f（key）= a * key + b （a、b为常数） 特点： 简单均匀，同时不会产生冲突，但是需要事先知道关键字的情况，适合数据连续的情况，由于现实中的条件限制，这种方法往往不能满足实际需求 数字分析法：

例子： 例如同一个地区的身份证号码，前面很多位都可能是一样的，所以我们只需要将最后几位抽取出来作为关键字 特点： 适合处理关键字位数比较大，同时事先知道了关键字的分布 平方取中：

例子： 例如关键字是1234，那么平方就是1522756，最后将中间的三维抽取出来，作为散列地址 特点：适用于不知道关键字的分布，同时位数也不是很大的情况 折叠法：

例子： 关键字从左到右分割为几个部分，然后将这几个部分相加，得到的结果（或者仅取几位）作为散列地址 特点：适用于不知道关键字的分布，同时位数很大的情况 除留余数法：

公式： f（key）= key MOD p（p <= m） MOD表示取模 m代表哈希表的长度 根据前辈们的经验，p一般取小雨或者等于哈希表长（最好接近m）的最小质数或者是不包含小于20的质因子的合数 特点： 是最常见的构造方法 随机数法：

公式： f（key） = random（key）