我们用数组来存储符号表的键-值对，通过算术运算将键转换成数组的索引。当需要查找元素时，将待查找元素的键转换成数组索引，直接通过下标访问即可。这样的办法称为哈希（hashing）。
这样的算法包含两部分：首先是计算哈希函数(hash function)，将键转换为数组索引。理想化的结果是每一个键的哈希值互不相同。通常情况下，多个键会映射到同一个哈希值，所以有了第二部分——冲突修复(collision resolution)，我们后面将采用两种办法来实现冲突修复：分离链接(separate chaining)和线性探查(linear probing)。
哈希是一个很好的时空复杂度平衡(time-space tradeoff)的例子。理想情况下，每个键的哈希值互不相同，这样，就可以直接通过数组索引访问，但这样需要维护一张很大的哈希表，内存占用太大。如果多个键指向同一个哈希值，就可以显著减少哈希表的大小，但通过数组所有找到元素位置后，还需要某种办法（比如最简单的线性扫描）才能唯一的查找到元素，增加了时间开销。
哈希函数（Hash Function）
如果我们有一个大小为M的数组来存储键-值对，那么我们就需要一个哈希函数能将元素的键转化为[0,M-1]之内的整数，作为数组的索引。这个函数必须满足两个条件：
- 易于计算
- 使键均匀分布，即每个键转化为[0,M-1]之间的任意整数必须是近似等可能的
哈希函数依赖于键本身的数据结构，所以不同类型的键就需要不同的哈希函数。
为了更好地理解均匀分布的含义，考虑下面一个例子：我们要存储1000个人的个人信息，他们的身份证号作为键，要构造出一个哈希函数来将每个人的身份证号转换为[0-999]直接的数字。我们可以直接取身份证号后三位，也可以直接取身份证号前三位，但显然取后三位要比前三位好。因为前三位与地理位置紧密相关，1000个人的身份证号前三位很可能不是均匀分布于[0,999]，可能有一半以上的人前三位相同。
当然更好的做法是将身份证号的18位转化成18位的大整数，用这个整数来计算哈希值。
正整数的哈希
对于整数，最常用的办法是模运算哈希(modular hashing)。我们选一个合适的质数M来作为哈希表的大小，对每个整数进行模M运算，得到的结果就是它的哈希值。
为什么一定要用质数
比较下面表格中的两种情况
| Key | hash (M=100) | hash (M=97) |
|---|---|---|
| 212 | 12 | 18 |
| 618 | 18 | 36 |
| 302 | 2 | 11 |
| 940 | 40 | 67 |
| 702 | 2 | 23 |
| 704 | 4 | 25 |
| 612 | 12 | 30 |
| 606 | 6 | 24 |
| 772 | 72 | 93 |
| 510 | 10 | 25 |
| 423 | 23 | 35 |
| 650 | 50 | 68 |
| 317 | 17 | 26 |
| 907 | 7 | 34 |
| 507 | 7 | 22 |
| 304 | 4 | 13 |
| 714 | 14 | 35 |
| 857 | 57 | 81 |
| 801 | 1 | 25 |
| 900 | 0 | 27 |
| 413 | 13 | 25 |
| 701 | 1 | 22 |
| 418 | 18 | 30 |
| 601 | 1 | 19 |
从表格中可以看出，用质数可以使元素分布得更均匀。因为使用100实际上只用了后两位数字所包含的信息，而用质数则用到了每一位包含的信息。
浮点数的哈希
如果键是0-1之间的实数，那么可以给每个数乘M然后向下取整得到[0,M-1]之内的数组索引。但这种做法是有缺陷的，因为它给予高位上的数字更大的影响权重，而最后一位对结果几乎不起什么作用。
解决这个问题的一种办法就是对小数的二进制表示直接进行模运算哈希
字符串的哈希
我们可以将字符串看作是一个大整数来进行模运算哈希，将字符串里的每个字符转化成对应的整数，代码如下：
int hash = 0;
for (int i = 0; i < s.length(); i++)
hash = (R * hash + s.charAt(i)) % M;
当R比任意字符对应的整数大时，我们实际上相当于把字符串转化成了一个N位R进制的整数。如果选一个足够小但又比任何字符对应整数大的R，我们就可以得到想要的分布于[0,M-1]之间的整数。
保持相等的一致性（Consistent with equals）
不论是哪种类型，哈希函数必须保持相等的一致性：即若两个键相等，则它们的哈希值相等；若哈希值相等，则键不一定相等。
用户自定义类型的哈希
对于用户自定义的类型，可以对类中的每个部分进行哈希，然后进行算术运算，得到最终的哈希值。例如，对于Transaction类型，可以采用以下的办法：
public class Transaction
{
...
private final String who;
private final Date when;
private final double amount;
public hashCode()
{
int hash = 17;
hash = 31 * hash + who.hashCode();
hash = 31 * hash + when.hashCode();
hash = 31 * hash + ((Double) amount).hashCode();
return hash;
}
...
}
注：对于基本类型（如double），需要进行包装(wrap)，才可以使用hashCode()方法。
缓存
可以在类里面添加一个属性hash，这样，只需要第一次计算hash值就可以，此后只需要访问hash这个属性。
用分离链接的办法解决冲突（Hashing with separate chaining）
当发生冲突时（多个键对应同一哈希值，这是很常见的），一个很直接且常用的办法就是对哈希表中的每个索引建一个链表，来存储对应这个哈希值的所有的键。
————————————————————————
在采用分离链接法，有M个链表、N个键-值对的哈希表中，每个链表中的元素个数小于 C*N/M 的可能性十分接近于1。（其中，C是一个很小的常数）。而且，对于查找失败和插入操作，所需要的比较操作次数为 ~N/M
————————————————————————
注意：如果哈希函数不是均匀的，那么查找和插入的开销甚至不会优于顺序查找。
表的大小
采用分离链接法时，我们要选择一个足够小的M值使得不至于浪费很多空间来存储大量的空表，同时又要足够大，使得不至于浪费太多时间去对长链表进行顺序查找。
基于顺序的操作
进行哈希后，元素间的顺序关系就不存在了，所以哈希表不能高效支持任何基于顺序的操作，比如找出最值。任何基于顺序的操作的时间复杂度都为O(n)。
用线性探查的办法解决冲突（Hashing with linear probing）
另一种解决冲突的办法是将N个元素存储到一个大小为M（M>N）的哈希表中，用表中的空位来解决冲突的问题。这类方法都称为开放地址法，其中最简单的是线性探查。
线性探查的基本原理如下：当我们通过哈希值索引到哈希表中的某一位置时，检查这个位置上的元素与查找元素的键是否相同，如果不同，在哈希表中向后移动一位，继续比较键，直到遇到空位置或者键匹配。遇到空位置，即说明是search miss，对于查找，可以返回查找失败；对于插入，可以在此处插入新的键-值对。
- 键与查找的键相同：查找成功
- 遇到空位置：查找失败
- 键与查找的键不同：尝试哈希表中的下一个元素
删除
对于删除操作，我们不能简单地将待删除元素位置的键设为空。如果这样，那么该键后面紧邻的键将永远不能被查出。所以我们要将待删除元素后面紧邻的所有键依次向前移动一位（重新插入）。
簇
将采用线性探查的哈希表中彼此相邻的一组元素称为一个簇。由查找原理可知，越小的簇越有利于提高查找效率，越大的簇会导致越长的线性搜索。然而，不幸的是，采用线性探查方法，越大的簇更易于增大，因为插入元素的哈希值落在大簇中的可能性更大（落在每个索引处等可能）。
有一个办法可以解决这个问题，即换一种探查序列。在线性探查中，一旦匹配到哈希值，我们探查的序列是：1，2，3，4，···；我们可以换成1，2，4，8，···这样的平方探查(quadratic probing)序列或某种伪随机数序列。
性能分析
————————————————————————
在一个使用线性探查，大小为M，含有 N = αM 个键的哈希表中：对于查找成功和查找失败（插入），分别平均需要 ~(1+1/(1-α))/2 和 ~(1+1/(1-α)^2)/2次探查(probe)。这个估计在α接近1时会失去准确性，然而我们不需要这部分的准确性，因为通过可变数组，我们总可以使数组内元素数量保持在1/8~1/2之间。
————————————————————————
数组大小可变
对于线性探查来说，数组大小可变是必须的，一个满的数组会导致死循环，一个接近满的数组也会降低性能，而接近空的数组又会浪费空间。对于分离链接来说，数组大小可变是可选的，只要你对N有一个不错的估计。
总结
哈希表的最大优点是：对于查找和插入来说，时间复杂度都为O(1)。而它的主要缺点是：不支持基于顺序的操作。两种解决冲突的办法没有绝对的优劣之分，分离链接更能使用零散的内存块，而线性探查使用一整块内存来存储数组，使用哪一个取决于具体的环境。