概念
在顺序结构以及平衡树中，元素关键字与他们存储的位置并没有直接的映射关系，从而会影响查找关键字的效率，顺序结构中查找关键字的时间复杂度为O（N），平衡树查找关键字的时间复杂度为O（log2^N）。
最理想的搜索方法——只搜索一次就能找到关键字。
如果有一种数据结构，能够使得关键字根据某种映射规则，将关键字和它的存储位置一一映射起来，那么在查找时通过映射规则就能够很快将关键字查找出来。
在这个数据结构中
插入元素：
根据某种特定的映射规则，找到关键字在存储结构中的位置，然后插入。
搜索元素：
根据某种特定映射规则，将求得的函数值作为元素的存储位置，然后与结构中此位置的元素比较，若关键字相等，则搜索成功。
该方式就被称为哈希或者散列，使用的映射函数就为哈希函数或者散列函数，构造出来的存储结构就为哈希表或者散列表。
比如：数据集合{1，7，6，4，5，9}
如果哈希函数设置为hash(key)=key%10，则数据在存储结构内会呈现以下关系
该方法查找每一个数只需要进行一次比较，效率很高，但是这种存储方式在实际使用的时候会导致很多的空间浪费，有些空间为空，被没有被有效利用起来，所以实际使用时模数的取值一般为不超过存储结构容量的最大质数。
哈希冲突
哈希冲突的原因是由于，当有一组数据需要通过相同的映射规则存储到到一个存储结构时，此时就有可能两个数得到的hash(key)的值相同，但是又不可能将两个数字同时存储在一个空间里面，这时就造成了哈希冲突，或者叫哈希碰撞。
此时把具有相同哈希地址的不同关键字记为“同义词”。
发生哈希表该如何处理呢？
处理方法
拉链法
比如：数据集合{1，7，6，4，5，9，12，25，36}
加入存储结构容量为7，则哈希函数为hash(key)=key%7。
这种情况就将哈希地址相同的数据元素依次链接到之前元素的后面。
成功查找的平均查找长度 ASL成功=（6*1+2*2）/9=1.11
ASL失败=9/7=1.286。
装填因子=表中记录数/散列表长度。
装填因子越大表示表装得越满。
直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
由于这是一个一次函数，所以对于每一个不相同的元素对应的值就不相同，所以哈希地址不会存在冲突。
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
开放定址法
线性探测法
意思就是通过哈希函数处理后得到的关键字哈希地址如果存在冲突，那么就依次往后面去找空位将这个数放进去。
