概念
哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。
使用哈希查找有两个步骤:
- 使用哈希函数将被查找的键转换为数组的索引，在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况，所以哈希查找的第二个步骤就是处理冲突。
- 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
在Hash表中，记录在表中的位置和其关键字之间存在着一种确定的关系，这样就能够预先知道所查关键字在表中的位置，从而直接通过下标找到记录，使ASL趋近于0
1) 哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地 址集合的大小不超出允许范围即可；
2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1！=key2，而 f (key1) = f(key2)。
3). 只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字， 而地址集合的元素仅为哈希表中的地址值
在构造这种特殊的”查找表”时，除了需要选择一个”好”(尽可能少产生冲突)的哈希函数之外，还需要找到一种”处理冲突”的方法。
Hash处理冲突方法
通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：
开放定址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：
1. 线性探测再散列
di=1，2，3，…，m-1
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
2. 二次探测再散列
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
3. 伪随机探测再散列
di = 伪随机探测再散列
具体实现时，应该建立一个伪随机数发生器，如 i = (i+p) % m），并给定一个随机数做起点。
再哈希法
这种方法是同时构造多个不同的哈希函数
当哈希地址H1 = RH1(key) 发生冲突时， 再计算 H2 = RH2(key) …..直到冲突不产生，这种方法不容易产生聚集，但增加了计算时间。
链地址法
这种方法的基本思想就是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表中的第 i 个单元中，因而查找，插入和删除主要在同义词链中进行，链地址法适用与经常插入和删除的情况。
Java中HashMap的底层实现中的链表部分就是使用的链地方法。
建立公共溢出区
这种方法的基本思想就是： 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突元素，一律填入溢出表。
