什么是哈希表

哈希表是以 Key-Value 形式存储的的数据结构，当我们需要查找某个值，只需要输入相应的Key值即可。
首先我们看看整个哈希表的逻辑机构图

逻辑结构图

哈希的整个思路也比较简单，首先将Key按照特定的哈希算法（算法的选择，根据需要而定）函数H(Key)生成哈希值，再将哈希值转为数组的一个索引（Index）；因为不同的哈希值可能获得同意额索引，也有可能不同的Key 但哈希值相同，所以接下来就是处理索引冲突。

常见的哈希函数

.正整数
如果Key是正整数，常用的哈希算法就是对Key取模运算，也就是对于长度为L的数组，那么对于任意的正整数N，获得 index = N%L
.字符串
对于字符串也可以采用取模的运算 来获取索引值，但是须将字符串转为正整数，常用的方法就是将字符串中的每个字符进行hash
例如Java中：

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

哈希冲突

拉链法

通过H（key）可以将哈希值转为0 至 L-1范围内的索引，但是对于索引相同的情况，就需要有一种方法来解决这种问题。
一种比较简单的办法就是，将长度为L 的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法。下图很清楚的描述了什么是拉链法。
如下图所示

网络图片

图中，”John Smith”和”Sandra Dee” 通过哈希函数都指向了152 这个索引，该索引又指向了一个链表， 在链表中依次存储了这两个字符串。
该方法的基本思想就是选择足够长度的数组，使得所有的链表都尽可能的短小，以保证查找的效率。对采用拉链法的哈希实现的查找分为两步，首先是根据散列值找到对应的链表，然后沿着链表顺序找到相应的哈希值H(key)。此链表可以自己实现。当然，您也可以使用Java里面内置的LinkedList。使用拉链法最关键的就是选择合适长度的数组，使得因为链表太长而增加查找时间，又不会因为空置的链表的浪费空间。

开放地址法

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p₁，如果p₁仍然冲突，再以p为基础，产生另一个哈希地址p₂，以此类推直到找出一个不冲突的哈希地址p_i ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
Hi=（H（key）+d_i）% m （i=1，2，…，n)
其中H（key）为哈希函数，m 为表长，d_i称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

1.线性探测再散列法

d_i(i=1，2，3，…，m-1)
这种方法的特点是：冲突发生时，顺序查看表中下一单元地址，直到找出一个空单元或查遍全表。

2.二次探测再散列

d_i=1²，-1²，2²，-2²，…，k²，-k² ( k<=m/2)
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

3.伪随机探测再散列

d_i=伪随机数序列。具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。
如果用线性探测再散列处理冲突，下一个哈希地址为H₁=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H₂=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H₃=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。
如果用二次探测再散列处理冲突，下一个哈希地址为H₁=3 + 1²）% 11 = 4，仍然冲突，再找下一个哈希地址为H₂=（3 - 1²）% 11 = 2，此时不再冲突，将69填入2号单元。
如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H₁=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H₂=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

再哈希法

这种方法是同时构造多个不同的哈希函数：
H=RH_i（key） （i=1，2，…，k)
当哈希地址H=RH_i（key）发生冲突时，再计算H=RH_i+1（key，以此类推直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。