1 哈希表

　　哈希表是一种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多得让人难以置信。不论哈希表中有多少数据，插入和删除只需要接近常量的时间:即O(1)的时间级。实际上，这只需要几条机器指令。
　　对哈希表的使用者来说，这是非常迅速的事情。哈希表运算得非常快，在计算机程序中，如果需要在一秒钟内查找上千条记录，通常使用哈希表。哈希表的速度明显比树快，树的操作需要O(N)的时间级，哈希表不仅速度快，而且变成实现容易。
　　哈希表也有一些缺点:它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降非常严重，所以程序员必须清楚表中将要存储多少个数据(或者准备好定时地把数据转移到更大的哈希表中)而且也没有一种简便的方法可以以任何一种顺序，比如从小到大遍历表中的数据项，如果需要，只能选择其他数据结构。
　　然而，如果不需要有序遍历数据，并且可以提前预测数据量的大小，那么哈希表在速度和易用性方面是无与伦比的。

2 哈希化简介

　　本节介绍哈希表和哈希化。其中一个重要的概念是如何把关键字转换成数组下标。在哈希表中，这个转换通过哈希函数来完成。然而对于特定的关键字，并不需要哈希函数；关键字的值可以直接用于数组下标。先看一个例子，然后再说明，如果关键字值不能恰好用于数组下标时候，如何使用哈希函数进行转换。

2.1 关键字作为索引

　　假设现在要写一个程序，存取一个公司的雇员记录，公司大约1000名员工，每个员工1000个字节的存储空间，因此整个数据库的大小约1MB，一般的计算机都可以满足。
这时候1-1000的雇员号码就可以作为存取记录的关键字。但是对于删除就很麻烦。因为数组的删除效率很低。但是查找和存储很快。

2.2字典

　　如果要把a到zyzzyva，都写入内存以便快速读写，哈希表是个不错的选择。
　　比如想在内存中存储50000个英文单词，起初可能考虑每个单词占据一个数组单元，那么数组大小是50000.那么怎么找到下标呢？
　　可以把单词转化成数组下标。a是97，b是98依次类推。然后就可以把字母表示成数字，并且可以进行求和，将单词转化成数字，比如cats是43。但是这个会产生一个问题，比如多个单词都会用同一个下标，例如was等等。
　　另外一种方案是用幂相乘并且求和，这种方式虽然可以产生唯一的下标，但是会导致数组下标非常大，导致内存无法存储这么大的数据。比如zzzzzzzzz，z用26表示，加上空格27，变成幂的和将超过7万亿。显然这个数字太大了。

2.3 哈希化

　　现在需要一种压缩方法，把数位幂的连乘系统中得到的巨大的整数范围压缩到可接受的数组范围中。对于英语词典，多大的数组才合适？如果只有50000个单词，可能会假设这个数组大概就有这么多空间，但实际上需要多一倍的空间容纳这些单词。所以最终需要容量为100000的数组。所以需要找到一种方法把0到超过7万亿的范围，压缩到0到10万。有一种简单的方法是取余数可以做到。
　　比如0——199，被10整除时候，余数会在0到9之间，这样就实现了压缩。这种函数叫哈希函数。它把一个大范围的数字哈希(转化)成一个小范围的数字，这个小的范围对应着数组的下标，使用哈希函数向数组插入数据后，这个数组就称为哈希表。
　　若结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。由此，不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function），按这个思想建立的表为散列表。
　　对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。

2.4 冲突

　　把巨大的数字空间压缩成较小的数字空间，必然要付出代价，即不能保证每个单词都映射到数组的空白单元。另外还可能导致的问题是两个单词的下标相同，这种情况称为冲突。
　　冲突的可能性会导致哈希化方案无法实施，实际上，可以通过另外的方式解决这个问题，记住，前面已经说过，指定的数组大小两倍于需要存储的数据量，因此可能一半的单元是空的，当冲突发生的时候，一个方法是通过系统的方法找到数组的一个空位，并把单词填入，而不再用哈希函数的数组下标。这个方法叫做开放地址法。例如cats哈希化的结果是5421，但它的位置已经被parsnip占用，那么可以把cats放在5422位置上。第二种方法是创建一个存放单词链表的数组，数组内不直接存储单词。这样，当发生冲突时，新的数据项直接存到这个数组下标所指的链表中，这个方法叫链地址法。另一种方法叫开放地址法。在开放地址法中，若数据不能直接放在哈希函数计算出来的数组下标所指的单元时，就要寻找数组的其他位置。下面要探索开放地址法的三种方法，它们在寻找下一个空白单元时使用的方法不同，这三种方法分别是线性探测、二次探测和再哈希法。

2.5 线性探测法

　　在线性探测中，线性地查找空白单元。如果5421是要插入数据的位置，并且已经被占用，那么就使用5422，然后是5433，依次类推，直到找到空位，这就叫做线性探测。因此当哈希表数据越来越满时候，效率会变低。这种数据越来越满被称为聚集，聚集严重会导致非常长的探测长度，存取序列会很耗时。当数组填得三分之二满的时候，情况良好，如果超过这个界限，聚集会越来越严重，性能下降严重。因此设计哈希表的关键是确保它不会超过整个数组容量的一半，最多到三分之二。

find方法

　　find方法首先调用hashFunc方法把待查找关键字转换成数组下标hashVal。hashFunc方法把求余操作符应用于查找关键字和数组容量。
　　接着，在while循环中，find方法检查这个下标所指单元是否为空，如果不空，它检查这个数据项是否包含待检查关键字，如果包含，find方法返回这个数据项，如果不包含，find递增hashVal，并且回到while循环的开始，检查下一个单元是否被占用。

public DataItem find(int key){
    int hashVal = hashFunc(key);
    while(hashArray[hashVal] != null){
        if(hashArray[hashVal].getKey() == key){
            return hashArray[hashVal];
        }
        ++hashVal;
        hashVal %= arraySize;
    }
    //没有找到
    return null;
}

　　随着hashVal递增，它最终到达数组的尾端，这种情况发生时，我们希望它能再次回到数组的起始端。

insert方法

　　insert方法插入新的数据项，使用find类似的算法定位数据项，但是需要寻找一个空位或者被删除的数据项(关键字为-1)

public void insert(DataItem item){
    int key = item.getKey();
    int hashVal = hashFunc(key);
    //如果有数据项
    while(hashArray[hashVal] != null && hashArray[hashVal].iData != -1){
        ++hashVal;
        hashVal %= arraySize;
    }
    //没有数据项
    hashArray[hashVal] = item;
}

delete方法

　　下面的delete方法用find方法的算法找到一个已存在的项，当找到这个数据项后，delete方法用特殊的数据项nonItem覆盖原来的数据，这个变量事先定义为-1。

public DataItem delete(int key){
    int hashVal = hashFunc(key);
    while(hashArray[hashVal] != null){
        if(hashArray[hashVal].getKey() == key){
            DataItem temp = hashArray[hashVal];
            hashArray[hashVal] = nonItem;
            return temp;
        }
        ++hashVal;
        hashVal %= arraySize;
    }
    return null;
}

扩展数组
　　当哈希表变得太满时，一个选择是扩展数组，在java中数组大小固定，且不能扩展，编程时候只能创建一个新的更大的数组，然后把旧数组的所有内容插入到新的数组中。
　　哈希函数根据数组大小计算给定数据项的位置，所以，这些数据项不能再放在新数组中和老数组相同的位置上，因此，不能简单地从一个数组向另一个数组拷贝数据。因此不能简单地从一个数组向另一个数组拷贝数据，需要按顺序遍历老数组，用insert方法向新数组中插入每个数据项，这叫做重新哈希化。
　　扩展后的数组容量通常是原来的两倍。实际上，因为数组容量应该是一个质数，所以新数组要比两倍的容量多一点。计算新数组的容量是重新哈希化的一部分。

private int getPrime(int min){
    for(int j = min + 1; true; j++){
        if(isPrime(j)){
            return j;
        }
    }
}
private boolean isPrime(int n){
    for(int j = 2; (j*j <= n); j++){
        if(n % j == 0){
            return false;
        }
    }
    return true
}

2.6 二次探测

　　在开放地址法的线性探测中会发生聚集，一旦聚集形成，它会变得越来越大，聚集越大，增长也越快。
　　已填入哈希表的数据项和哈希表长度的比率叫做装填因子。有10000个单元的哈希表填入6667个数据后，它的填装因子是2/3。当填装因子不太大时，聚集分布得比较连贯，哈希表的某个部分可能包含大量的聚集，而另一个部分还很稀疏，聚集降低了哈希表的性能。
　　二次探测是防止聚集产生的一种尝试，思想是探测相隔较远的单元，而不是和原始位置相邻的单元。
步骤是步数的平方
　　在线性探测中，如果哈希函数计算的原始下标是x，线性探测就是x+1, x+2, x+3，依次类推。而在二次探测中，探测的过程是x+1，x+4, x+9, x+16，依此类推，到原始位置的距离是步数的平方。二次探测也会产生聚集问题。比如将184,302,420和544 依次插入到表中，它们都映射到7，那么302需要以1为步长，420需要以4为步长，544需要以9为步长的探测。只要有一项，其关键字映射到7，就需要更长步长的探测，这个现象叫做二次聚集。二次聚集不是一个严重的问题，但是，二次聚集不会经常使用。

2.7 再哈希法

　　为了消除原始聚集和二次聚集，可以使用另外一个方法:再哈希法。二次聚集产生的原因是，二次探测的算法产生的探测序列步长总是固定的:1, 4, 9, 16，依次类推。
　　现在需要的一种方法是产生一种依赖关键字的探测序列，而不是每个关键字都一样。那么，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。
　　方法是把关键字用不同的哈希函数再做一遍哈希化，用这个结果作为步长，对指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用不同的步长。
经验说明，第二个哈希函数必须具备如下特点:
1. 和第一个哈希函数不同
2. 不能输出0，否则，将没有步长，每次探测都是原地踏步，算法将陷入死循环。
　　专家们已经发现下面形式的哈希函数工作得非常好:
　　stepSize = constant - (key % constant);
　　其中constant是质数，且小于数组容量，例如stepSize = 5 - (key % 5);

　　表容量是质数的原因是如果不是质数，例如表长是15，有一个特定关键字，映射到0，步长为5，那么探测序列是0,5,10,0,5,10，依此类推，算法将不会找到1,2,3或其他位置，程序将崩溃。如果容量是13，探测序列0,5,10,2,7,12,4,9,1,6,11,3，一直下去,只要表中有空位，就可以探测到。用质数作为数组容量使得任何数想整除它都是不可能的，因此会探测所有单元。

3 开放地址法

　　开放地址法中，通过在哈希表中再寻找一个空位解决冲突问题。另一个方法是在哈希表每个单元中设置链表。某个数据项的关键字值还是像通常意义映射到哈希表的单元中，而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加到链表中。不需要在原始的数组中寻找空位。

　　链地址法在概念上比开放地址法中的几种探测策略要简单，但是代码会比其他的长，因为必须要包含链表机制，这就要在程序中增加一个类。
填装因子
　　链地址法中的填装因子(数据项数和哈希表容量的比值)与开放地址法不同，在链地址法中，需要在有N个单元的数组中装入N个或更多的数据项，因此填装因子一般大于等于1.这没有问题，因为某些位置包含的链表中包含两个或两个以上的数据项。
　　当然，如果链表中有许多项，存取时间就会变长，因为存取特定数据项平均需要搜索链表一半的数据项。找到初始的单元需要O(1)的时间级，而搜索链表的时间与M成正比，M为链表包含的平均项数，即O(M)的时间级，因此，并不希望链表太满。填装因子为1的情况下，大约三分之一的单元为空，三分之一的单元有1个数据项，三分之一的单元有更多数据项。
重复值问题
　　这里允许重复，在填入过程中可以填重复出现的值。所有相同关键字值的项都放在同一链表中。所以如果需要找到所有项，不管查找是否成功，都要搜索整个链表，这会使性能略微下降。
表的容量
　　如果用链地址法的话，表容量是质数要求就不像在二次探测和再哈希法中显得那么重要，这里没有探测，所以不需要担心探测会因为表容量能被步长整除，而陷入无限的循环中。但是当容量不是质数时，这种关键字的分布还是能够导致数据的聚集。
桶
　　另一种方法类似于链地址法，它在哈希表的每个单元中使用数组，而不是链表，这样的数组有时称为桶，然而这个方法不如链表有效，因为桶容量不好选择。如果容量太小，可能会溢出。如果太大浪费空间，链表是动态分配的，不会有这个问题。

4 哈希函数

　　本节讨论设计好的哈希函数所需的因素。
快速的计算
　　好的哈希函数很简单，能进行快速计算。哈希表的优点是它的速度。如果哈希函数运行速度缓慢，速度就会降低，哈希函数中有许多乘法和除法是不可取的，如果是2的幂次，可以通过移位来进行。
　　哈希函数的目的是得到关键字值的范围，把它用一种方式转化成数组的下标值，这种方法应该使关键字值随机地分布在整个哈希表中。关键字可能完全随机，但也有可能不那么完全随机。
随机关键字
　　所谓完美的哈希函数把每个关键字都映射到表中的不同位置。只有在关键字组织得异乎寻常的好，且它的范围足够小，可以直接用于数组的下标的时候，这种情况才可能出现。大多数情况下，这种情况不会发生，哈希函数需要把较大的关键字值范围压缩成较小的数组下标范围。
　　在特定的数据库中，关键字值的分布决定哈希函数需要做什么。例如取余操作，只包含一个数学操作，如果关键字是随机的，得到的下标也是随机的。
非随机关键字
　　数据通常不是随机分布的，例如手机号码，每个字段有特定的含义。
不要使用无用的数据
　　压缩关键字段时候，要把每个位都计算在内，无用的数据应该舍弃。
使用所有数据
　　除了无用数据外，关键字的每个部分都应该在哈希函数中有所反映。不要只使用部分数据，关键字提供的数据越多，哈希化后，越能覆盖整个下标范围。有时关键字的范围太大，超出了int和long类型的规定，马上会说到哈希化字符串，将可以看到如何控制溢出。
　　总结：关于哈希函数的窍门是找到既简单又快的哈希函数，而且去除依赖于其他字段的无用数据，就是要覆盖所有的元数据字段。

使用质数作为取模的基数

　　通常，哈希函数包含对数组容量的取模操作。前面已经看到，使用二次探测和再哈希法时，要求数组容量为质数是多么的重要，如果关键字本身不是随机分布的，不论使用什么哈希化系统，都应该要求数组容量是质数。

哈希化字符串

　　前面已经看到如何把短小的字符串转化成数字，也就是幂乘积的形式。变成数字后，再哈希化即可。

public static int hashFunc1(String key){
    int hashVal = 0;
    int pow27 = 1;
    for(int j = key.length - 1; j >= 0; j--){
        int letter = key.charAt(j) - 96;
        hashVal += pow27 * letter;
        pow27 *= 27;
    }
    return hashVal % arraySize;
}

　　不幸的是，hashFunc方法不能处理大于7个字符的字符串，更长的字符串会导致hashVal的值超出int类型范围。不过，我们可以在中间进行取模操作，和最后一步进行取模操作结果一样，但是避免了溢出。

public static int hashFunc(String key){
    int hashVal = 0;
    for(int j = 0; j < key.length(); j++){
        int letter = key.charAt(j) - 96;
        hashVal = (hashVal * 27 + letter)%arraySize;
    }
    return hashVal;
}

折叠
　　另一个哈希函数是把关键字的数字分成几组，然后几个组相加。这样做确保了所有数字对哈希值都有贡献。一个组拥有几个数字，是和数组容量相对应的。即对于有1000项的数组，每组包含3个数字。
　　例如，假设要哈希化一个9位数的社会安全号码，使用线性探测。如果数组容量是1000项，就把9位分层三组，例如某个号码是123-45-6789，然后按公式123+456+789=1368，计算关键字和，然后取模，1368%1000=368。如果数组容量是100，就分成4个两位数和1个一位数的组:12+34+56+78+9=189,然后189%100=89

5 哈希化的效率

　　已经注意到在哈希表中执行插入和搜索操作可以达到O(1)的时间级，如果没有发生冲突，只需要使用一次哈希函数和数组的引用，就可以插入一个新数据项或找到一个已经存在的数据项。这是最小的存取时间级。
　　如果发生冲突，存取时间就依赖后来的探测长度。在一次探测中，每个单元的存取时间要加上寻找一个空白单元(插入时)或一个已经存在单元的时间，在一次存取中，要检查这个单元是不是空的，以及(查找或删除时)这个单元是不是包含要寻找的数据项。
　　因此，一个单独的查找或插入时间与探测的长度成正比，这里还要加上哈希函数的常量时间。平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度也越来越长。

5.1 开放地址法

　　随着填装因子变大，效率下降的情况，在不同开放地址法方案中比链地址法更严重。
　　开放地址法中，不成功查找比成功的查找花费更多的时间。在探测序列中，只要找到要查找的数据项，算法就能停止，平均起来，这会发生在探测序列的一半。另一方面，要确定算法不能找到这样的项，就必须走过整个探测序列。
线性探测
　　下面的等式显示了线性探测时，探测序列(P)和填装因子(L)的关系，对成功的查找来说
P=(1+1/(1-L)^2)/2
而对于不成功的查找来说
P = (1+1/(1-L))/2

　　上图说明，当填装因子是1/2时，成功的搜索需要1.5次比较，不成功的搜索需要2.5次，当填装因子为2/3时，分别需要2.0次和5.0次比较，如果填装因子更大，比较次数会非常大。应该使填装因子保持在2/3以下，最好在1/2以下，另一方面，填装因子越低，对于给定数量的数据项，就需要越多的空间。实际情况中，最好的填装因子取决于存储效率和速度之间的平衡，随着填装因子变小，存储效率下降，而速度上升。
二次探测和再哈希法
　　二次探测和再哈希法的性能相当。它们的性能比线性探测略好。对成功的搜索，公式是
　　-log2(1 - loadFactor) / loadFactor
　　对于不成功的查找是
　　1 / (1-loadFactor)
　　对应的图是：

　　当填装因子是0.5时，成功和不成的查找平均需要2次比较，当填装因子为2/3时，分别需要2.37和3.0次比较，当填装因子为0.8时，分别需要2.9和5.0次，因此对于较高的填装因子，对比线性探测，二次探测和再哈希法还是可以忍受的。

链地址法
　　链地址法的效率分析有些不同，一般来说比开放地址法简单。
查找
1+loadFacotor/2
　　不管链表是否有序，都遵循这个公式，在不成功的查找中，如果链表不是有序的，要检查所有的数据项，所以时间是
1 + loadFactor
插入
　　如果链表是无序的，插入操作是立即完成的，这里不需要比较，哈希函数必须计算，所插入的时间是1。
　　如果是有序的，那么由于存在不成功的查找，平均要检查一半的数据项，所以插入时间是1+loadFactor/2。

5.2 开放地址法和链地址法的比较

　　如果使用开放地址法，对于小型的哈希表，再哈希法似乎比二次探测的效果好，有一个情况例外，就是内存充足，并且哈希表一经创建，就不再改变其容量。这种情况下，线性探测相对容易实现，并且填装因子低于0.5，几乎没有什么性能下降。
　　如果在哈希表创建时，要填入的项数未知，链地址法要好过开放地址法，如果用开放地址法。如果用开放地址法，随着填装因子变大，性能会很快下降，但是使用链地址法性能只是线性的下降。
　　当两者都可选时，使用链地址法，它需要使用链表类，但回报是增加比预期更多的数据时，不会导致性能的快速下降。

6 哈希化和外部存储

　　磁盘由许多包含文件的块组成，存取一个块的时间比任何在内存中存取数据的时间要长得多，因此，设计外部存储策略时候，不考虑最小化存取块的数量。
　　另一方面，外部存储器单位容量相当便宜，所以可以使用更大数量的存储器，超过要存储的项数，如果这样的话，会加快存取时间，这就有可能使用哈希表。
文件指针表
　　外部哈希化的关键部分是一个哈希表，它包含块成员，指向外部存储器的块，哈希表有时叫做索引，它可以存储在内存中，如果它太大，也可以存储在磁盘上，而把它的一部分放在内存中。即使把哈希表都放在内存中，也要在磁盘中保存一个备份，文件打开时，把它读入内存。
未填满块
　　一个块大小为8192字节，一个记录为512字节。因此一块可以容纳16个记录。哈希表的每个条目指向某个块，假设一个特殊的文件有100个块，内存中的索引(哈希表)记录了文件块的指针，第一块为0，一直到99.
　　在外部哈希化中，重要的是块不要填满，因此，每个块平均存储8个记录，有的块多些，有的少些，一个块大概有800个记录。

　　所有关键字映射为同一个值的记录都定位到相同的块，为找到特定关键字的一个记录，搜索算法哈希化关键字，用哈希值作为哈希表的下标，得到某个下标中的块号，然后读取这个块。
这个过程是有效的，因为定位一个特定的数据项，只需要访问一次块，缺点是相当多的磁盘空间被浪费了，因为设计时规定，块是不允许填满的。
　　为了实现这个方案，必须仔细选择哈希函数和哈希表的大小，为的是限制映射到相同的值的关键，在本例中，平均每个值只对应8个记录。
填满的块
　　即使用一个好的哈希函数，块偶尔也会填满。这时，可以使用在内部哈希表中讨论的处理冲突的不同方法:开放地址法和链地址法。
　　在开放地址法中，插入时，如果发现一个块是满的，算法在相邻的块插入新纪录，在线性探测法中是下一个块，但也可以用二次探测或再哈希法选择，在链地址法中，有一个溢出块，当发现已满时，新纪录在溢出块中。

数据结构和算法9——哈希表