编程珠玑--关于查找（二分法、自组织链、哈希）
查找是我们现实生活中经常需要做的事情。例如用字典查一个英文单词的释意，首先我们会定位到这个单词所在的页，然后再看与该单词关联的解释。这个过程中，单词是key，而单词+单词的释意则是一个record。信息的组织方式很大程度上影响了查找的方法，《编程珠玑》和《数据结构与算法分析》一样，介绍了针对两种信息组织方式的不同的查找方法。
首先是链表/数组的线性组织方式。在这种情况下，如果数据是排序的，那么二分查找显然是最高效的了。下面是我写的两种二分查找：
?
除了排序和非排序的线性组织方法，其实还有一种，就是通过key与其下标的映射函数来插入和查找key，这就是哈希函数(hashing function)。一般情况下，我们很难找到key和下标（位置）之间的一一映射，如果两个Key计算出来的下标相同，我们就说发生了冲突。好的哈希函数应该尽量让发生冲突的机率小一些。
但冲突总是存在的。冲突解决方法基本可以分成两种，一种称为open hashing，open hashing通过将计算出相同下标的Key放在同一个链表上来解决冲突，查找key的时候，首先计算该key的下标，然后通过哈希表中该下标指向的链表，对key进行（线性）查找。就像我们前面的桶排序一下，先把key分在不同的桶里，然后再对小数据进行查找或排序。
另一种称为close hashing，close hasing将所有的记录都放在哈希表上。把key通过哈希函数h(k)计算出来的下标称为home。如果home已经被其他记录占据，close hashing通过为它找到下一个下标而将其仍旧存放在哈希表中。有两种方法获取下一个下标。第一种是bucket hashing.把哈希表分成几个bucket,每个bucket有多个slot，哈希函数计算出来的下标将是指bucket的序号。除了有标号的bucket之外，还有一个overflow bucket，当有标号的bucket里的slot被用完了，元素将被放到overflow bucket里面去。因此，查找一个key时，如果在它对应的bucket里找不到它，而且该bucket是满的，那么必须去overflow buckte里面找。而我们知道overflow bucket里面的Key分布是没有规律的。
第二种是probing（探询）。本质上就是为一个key值设计一个探询函数 p(K, i)，如果它的home已经被占据，将根据这个探询函数来为它计算另一个位置，如果这个位置又被占了，再计算第二个，...，第i个... pos=(home+p(K,i))%M，M是下标的范围。最简单的探询函数是线性探询p(K,i)=i，也就是，如果Key的home被占了，那就找沿着它往下挨个找，直到找到一个空的位置。好的探询函数应该使所有的空槽被选中的机会相等，但是是像p(K,i)=i这样的线性探询，将会使探询序列聚合在一起，例如对于home=1的情况，其接下来的可能位置将是2, 3, 4,...，对于Home=2，其接下来的可能位置将是3, 4, 5, ..，跟home=1的序列将很快撞到一起，从而影响性能。这种现象在hashing过程中称为primary clustering。应该尽量使不同Home的候选序列尽早地分散开来。例如使用一个随机数列Perm[]={2,5,32,...},p(K,i)=Perm[i]，这样对于home= 1,其候选序列为{3,6,33....}而home=2的候选队列为{4, 7, 34,...}。或者使用二次探询函数：p(K,i)=i^2，则home=1的候选队列为{2,5,10,...}，home=2的候选队列为{3,6,11,...}。
伪随机探询和二次探询解决了primary clustering, 但是对于home位置相同的Key，它们的候选队列将是一样的，这形成了second clustering问题。解决的办法是使用复式散列（double hashing）：p(K,i)=i*h_2(K).关于哈希表的大小，《STL源码分析》里侯捷这样说到：“如果我们假设表格（哈希表）大小为质数，而且永远保持负载系数在0.5以下（只用了一半以下的糟）（也就是说超过0.5就重新配置并重新整理表格），那么就可以确定每插入一个新元素所需要的探测次数不多于2.
对于哈希表来说，主要有三个操作：插入(insert)，查找(search)，以及删除(remove)一个元素。下面实现了前面提到的OpenHashing, CloseHashing中的BucketHashing和ProbeHashing:首先是虚基类Hashing:
?
接着是虚基类CloseHashing:
?
然后是CloseHashing的实现：BucketHashing和ProbeHashing：
class Compare{public:static bool eq( const char a, const char b ){ return a==b; }static bool eq( const char* a, const char* b ){while( *a!='\0' && *b!='\0' && *a++==*b++ );return *a == *b;}static bool eq( const int a, const int b ){ return a==b; }};//EXAMPLE://以int为例子，假设key的值在[0,100]，那么range以外的值都可以拿来当EMPTY和TRASHint EMPTY = -1;int TRASH = -2;int M_SIZE = 11;int BUCKET_SIZE = 3;int OVERFLOW_BUCKET = 10;//int的值本身就是keyint getkey( const int& a ){return a;}//简单的哈希函数int inth( const int& a ){return a%M_SIZE;}//线性探询函数int intp( const int& a, int i ){return i;}int main(){Hashing<int, int, Compare, Compare>* test;//test = new BucketHashing<int, int, Compare, Compare>( M_SIZE, BUCKET_SIZE, OVERFLOW_BUCKET, inth, getkey, EMPTY, TRASH );test = new ProbeHashing<int, int, Compare, Compare>( M_SIZE, EMPTY, TRASH, inth, intp, getkey );//test = new OpenHashing<int, int, Compare, Compare>( M_SIZE, inth, getkey );test->insert( 23 );test->insert( 12 );test->insert( 1 );test->insert( 34 );test->print();cout<<"---------------------------------------"<<endl;int a=-1;test->search(34, a);cout<<a<<endl;test->search(30, a);cout<<a<<endl;test->search(1, a);cout<<a<<endl;cout<<"--------------------------------------:"<<endl;test->remove( 23, a );test->remove( 1, a );test->search( 34, a );cout<<a<<endl;test->print();cout<<"---------------------------------------"<<endl;test->insert( 10 );test->insert( 1 );test->insert( 34 );test->print();cout<<"---------------------------------------"<<endl;cout<<test->size()<<endl;test->clear();test->print();cout<<"---------------------------------------"<<endl;}?
?
除了链表/数组的线性组织方式，另一种方式即树的组织方式，我在《基于树的索引结构介绍》（http://philoscience.iteye.com/admin/blogs/1112759）中总结过，不过至今未实现其代码，呵呵，接下来就来试试。
