引言
问题：统计ASCII字符串中每种字符出现的次数。
解决方案:
void count(char *str) {
int dict[] = {0};
while (*str != '\0') {
dict[*str] += 1;
str++;
}
}对于任意一个ASCII字符c，都可以在\(O(1)\)时间获得c出现的次数。之所以会有这么快的速度，是因为可以直接通过字符c的值获得它在dict对应的地址。
hash表就是一个类似于上面dict的一个结构：通过给定的键(key)，我们能计算出对应值(value)在数组中的位置，以此达到快速访问元素的目的，元素所在的位置称为槽。
hash函数
当key的可能的取值范围（全域\(U\)）比较小时，可以直接用key的值作为索引（比如引言中的例子）。这种时候也被称为直接寻址表(direct-address table)。
直接寻址表的缺点十分明显：如果 全域\(U\)很大，建立一个大小为\(|U|\)的表\(T\)就不太实际。事实上key的取值知识\(U\)中的一部分，可以把存储需求降到K，然后通过hash函数把key映射到\([0,k)\)上，即 \(hash(U) \rightarrow [0, k)\)。
除法散列法
通过取k除以m的余数，把键k映射到m个槽的某一个，即散列函数\(hash(k) = k \mod m\)。
当应用除法散列法时，要避免选择m的某些值，比如\(m=2^n\)。一般使用一个和\(2^n\)不接近的素数。
乘法散列法
散列函数\(hash(k) = \lfloor m(kA - \lfloor kA \rfloor) \rfloor\)
其中\(k\)是关键字，\(A\)是一个大于0小于1的常数，\(m\)一般是2的某个次幂。
全域散列函法
对于特定的散列算法，恶意用户可以选择特殊的关键字，使得这些关键字都被散列到hash表的同一个槽中。这样hash表的平均查询时间就会下降至\(O(n)\)。
全域散列(universal hashing) 通过随机的选择散列函数，使之独立于关键字。在执行散列之前，全域散列法会在预先设计的函数集中随机选择一个作为散列函数。
冲突
在散列过程中，不同的键可能被映射到相同的槽中，这种情况被称为冲突。常见的解决办法有链接法、开放寻址法。
链接法
链接法把散列到同一个槽的所有元素都放在一个链表中， 把链表的头结点放在槽中。
链接法实现简单，但存在退化成链表的风险：当过多的关键字被散列到同一个槽时，对hash表的查询时间会接近\(O(n)\)。
为了解决这个问题，Java中的HashMap通过设置阈值限制链表的长度，当链表长度达到阈值时进行rehash或把链表转为红黑树。
另一方面，链接法的内存利用率较低，存在较多的槽未放置元素。
在简单均匀散列的情况下，一个能存放n个元素、具有m个槽位的散列表T，使用链接法的查询时间为\(O(1+\alpha)\)，其中负载因子\(\alpha = n/m\)。
开放寻址法
开放地址法的思想是：当关键字发生冲突时，通过探查散列表以选择一个空的槽放入元素。
在开放地址法中，所有的元素都会放在表中，不会使用额外的空间，表中各个槽要么有一个元素，要么为空。所以表的负载因子\(\alpha \le 1\)总是成立。
开放寻址法的查询效率受探查方法的影响。最简单的探查方法就是顺序检查表中的槽，直到找到空槽。这样的效率很低，查找时间是\(O(n)\)。实际上，探查的顺序依赖于待插入的关键字。
线性探查
第\(i\)此查询的位置\(h(k, i) = (h'(k)+i) \mod m\)，\(h'\)是一个普通的散列函数，在这里担任辅助散列函数。
二次探查
\(h(k, i) = (h'(k)+c_1 i + c_2 i^2) \mod m\)
双重散列
\(h(k, i) = (h_1(k) + i h_2(k)) \mod m\)