哈希表和哈希冲突的解决方法
哈希：把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。
这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不能从散列值来唯一确定输入值。
哈希表：
哈希表也称散列表，一个哈希表包含一个数组，通过特殊的关键码key来访问数组中的元素。哈希表的主要思想是通过一个哈希函数，把关键码映射的位置去寻找存放值得地方，读取的时候也是直接通过关键码来找到位置并存进去。
常见的哈希算法：
哈希表的组成取决于哈希算法，也就是哈希函数的构成。
1）直接定址法
-取关键字或关键字的某个线性函数值为散列地址。
-即f(key)=key或f(key)=a*key+b，其中a和b为常数。
2）除留余数法
-取关键字被某个不大于散列表长度m的数p求余，得到的作为散列地址。
-即f(key)=key%p, p<m。这是最为常见的一种哈希算法。
3）数字分析法
-当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
-仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
4）平方取中法
-先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
-随机分布的关键字，得到的散列地址也是随机分布的。
5）随机数法
-选择一个随机函数，把关键字的随机函数值作为它的哈希值。
-通常当关键字的长度不等时用这种方法。
哈希冲突：
哈希表因为其本身的结构使得查找对应的值变得方便快捷，但也带来了一些问题，以字典为例，key中的一个拼音对应一个字，那如果字典中有两个字的拼音相同时，它们有不同的key值，但经过哈希算法计算后得到的是相同的哈希数组下标值，因此在前后两次存储和查找时会发生哈希数组被占用的情况，可以采取一些方法处理哈希冲突。
哈希冲突解决方法：
1）开放地址法：
开放地址的做法是，当冲突发生时，使用某种探测算法在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。按照探测序列的方法，一般将开放地址法区分为线性探查法、二次探查法、双重散列法等。
1.1）线性探查法：
fi=(f(key)+i)%m, 0<=i<=m-1
探查时从地址d开始，首先探查T[d]，然后一次探查T[d+1]，...，直到T[m-1]，此后又循环到T[0]，T[1]，...，直到探查到有空余的地址或者到T[d-1]为止。
缺点：需要不断处理冲突，无论是存入还是查找效率都会大大降低。
1.2）二次探查法：平方探测法
fi=(f(key)+di)%m, 0<=i<=m-1
探查时从地址d开始，首先探查T[d]，然后依次探查T[d+di],di为增量序列1^2，-1^2, 2^2, -2^2 ,...,q^2, -q^2且q<=1/2(m-1)，直到探查到有空余地址或者到T[d-1]为止。
缺点：无法探查到整个散列空间。
1.3）双哈希函数探测法：
fi=(f(key)+i*g(key))%m (i=1,2,....,m-1)
其中，f(key)和g(key)是两个不同的哈希函数，m为哈希表的长度。
步骤-双哈希函数探测法，先用第一个函数f(key)对关键码计算哈希地址，一旦产生地址冲突，再用第二个函数g(key)确定移动的步子因长，最后通过步子因长序列由探测函数寻找空的哈希地址。
2）链地址法：
哈希表的每一位对应一个指向某个桶的指针，所有key经过哈希算法得到该表下标的输入都存入桶中。
3）建立公共缓冲区
建立一个公共溢出区域，把冲突的都放在另一个地方，不在表里面。
哈希的应用：
1）主要用于信息安全领域中的加密算法，它把一些长度不同的信息转换成杂乱的128位编码，这些编码值叫做hash值。hash就是找到一种数据内容和数据存放地址之间的映射关系。
2）查找：知道key时，直接计算出这个元素在哈希表中的位置。
3）hash表在海量数据处理中有着广泛的应用。
问题实例（海量数据处理）
我们知道hash表在海量数据处理中有着广泛的应用。问题：海量日志数据，提取出某日访问百度次数最多的那个IP。
方案：IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。