基于先前的学习计划，最近打算深入学习Java的集合类，首先要研究的就是HashMap，在学习HashMap前，我花了几天时间温习了一下类中用到的数据结构 （哈希表，二叉树），并决定把所学的知识记录写成文章，本文讲述的就是关于哈希表的知识。
什么是哈希表在之前的博客文章里，我们简单介绍了数据结构的几种分类，其中就包括哈希表，也称散列表，从根本上来说，一个哈希表包含一个数组，通过特殊的关键码(也就是key)来访问数组中的元素。哈希表的主要思想是通过一个哈希函数， 把关键码映射的位置去寻找存放值的地方 ，读取的时候也是直接通过关键码来找到位置并存进去。
最直接的例子就是字典，例如下面的字典图，如果我们要找 “啊” 这个字，只要根据拼音 “a” 去查找拼音索引，查找 “a” 在字典中的位置 “啊”，这个过程就是哈希函数的作用，用公式来表达就是：f(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中的一个拼音对应一个字，那如果字典中有两个字的拼音相同呢？例如，我们要查找 “按” 这个字，根据字母拼音就会跳到 “安” 的位置，这就是典型的哈希冲突问题。这个时候用公式表达就是：
key1 ≠ key2 ， f(key1) = f(key2)一般来说，哈希冲突是无法避免的，如果要完全避免的话，那么就只能一个字典对应一个值的地址，也就是一个字就有一个索引 (安 和 按就是两个索引)，这样一来，空间就会增大，甚至内存溢出。
哈希冲突的解决办法常见的哈希冲突解决办法有两种，开放地址法和链地址法。
一、开放地址法
开发地址法的做法是，当冲突发生时，使用某种探测算法在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。按照探测序列的方法，一般将开放地址法区分为线性探查法、二次探查法、双重散列法等。
这里为了更好的展示三种方法的效果，我们用以一个模为8的哈希表为例，采用除留余数法，往表中插入三个关键字分别为26，35，36的记录，分别除8取模后，在表中的位置如下：
这个时候插入42，那么正常应该在地址为2的位置里，但因为关键字30已经占据了位置，所以就需要解决这个地址冲突的情况，接下来就介绍三种探测方法的原理，并展示效果图。
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]为止。
插入42时，探查到地址2的位置已经被占据，接着下一个地址3，地址4，直到空位置的地址5，所以39应放入地址为5的位置。
缺点：需要不断处理冲突，无论是存入还是査找效率都会大大降低。
2） 二次探查法
fi=(f(key)+di) ％ m，0 ≤ i ≤ m-1