当我们在编程过程中，往往需要对线性表进行查找操作。在顺序表中查找时，需要从表头开始，依次遍历比较a[i]与key的值是否相等，直到相等才返回索引i；在有序表中查找时，我们经常使用的是二分查找，通过比较key与a[i]的大小来折半查找，直到相等时才返回索引i。最终通过索引找到我们要找的元素。 　　　但是，这两种方法的效率都依赖于查找中比较的次数。我们有一种想法，能不能不经过比较，而是直接通过关键字key一次得到所要的结果呢？这时，就有了散列表查找（哈希表）。

　　　 要说哈希表，我们必须先了解一种新的存储方式—散列技术。 　　　 散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每一个关键字都对应一个存储位置。即：存储位置=f（关键字）。这样，在查找的过程中，只需要通过这个对应关系f 找到给定值key的映射f（key）。只要集合中存在关键字和key相等的记录，则必在存储位置f（key）处。我们把这种对应关系f 称为散列函数或哈希函数。 　　　 按照这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为哈希表。所得的存储地址称为哈希地址或散列地址。

　　　①、存储数据时，将数据存入通过哈希函数计算所得哪那个地址里面。 　　　②、查找时，使用同一个哈希函数通过关键字key计算出存储地址，通过该地址即可访问到查找的记录。

　　在理想的情况下，每一个 关键字，通过哈希函数计算出来的地址都是不一样的。但是在实际情况中，我们常常会碰到两个关键字key1≠key2,但是f(key1) = f(key2), 这种现象称为冲突，并把key1和key2称为这个散列函数的同义词。 　　冲突的出现会造成查找上的错误，具体解决方法会在后文提到。

　　①、计算简单； 　　②、散列地址分布均匀。

　　①、直接定址法：不常用 　　 　取关键字或关键字的某个线性函数值为哈希地址： 　　 　即：Ｈ(key) = key 或 H(key) = a*key+b 　　　　优点：简单，均匀，不会产生冲突； 　　　　缺点：需要实现直到关键字的分布情况，适合查找表比较小且连续的情况。 　　 　　②、数字分析法 　　　数字分析法用于处理关键字是位数比较多的数字，通过抽取关键字的一部分进行操作，计算哈希存储位置的方法。 　　　例如：关键字是手机号时，众所周知，我们的１１位手机号中，前三位是接入号，一般对应不同运营商的子品牌；中间四位是ＨＬＲ识别号，表示用户号的归属地；最后四位才是真正的用户号，所以我们可以选择后四位成为哈希地址，对其在进行相应操作来减少冲突。 　　　数字分析法适合处理关键字位数比较大的情况，事先知道关键字的分布且关键字的若干位分布均匀。 　　　 　　③、平方取中法 　　　具体方法很简单：先对关键字取平方，然后选取中间几位为哈希地址；取的位数由表长决定，适用于不知道关键字的分布，而位数又不是很大的情况。 　　 　　④、折叠法 　　 将关键字分成位数相同的几部分（最后一部分位数 可以不同），然后求这几部分的叠加和（舍去进位），并按照散列表的表长，取后几位作为哈希地址。 　　 适用于关键字位数很多，而且关键字每一位上数字分布大致均匀。 　　 　　 ⑤、除留余数法 　　 此方法为最常用的构造哈希函数方法。对于哈希表长为m的哈希函数公式为： 　　 f(key) = key mod p (p