最近在看Bartosz Milewski的C++ In Action Industrial-Strength Programming Techniques，這本書很不錯，它不是語言基礎教程，全書主要介紹了許多工業(yè)強度的編程技術，如清理，隱藏實現(xiàn)細節(jié)，資源管理，共享，資源管理，使用標準模板庫，重載運算符等技術。這是Bartosz Milewski的簡介:Bartosz Milewski，C++ In Action 的作者。是Reliable Software公司的總裁，Reliable Software公司是一家為程序員制造高質量開發(fā)工具的公司。在過去幾年間，Bartosz Milewski在多家知名雜志發(fā)表了大量技術文章。在微軟工程工作的8年期間，他擔任Windows2000中Content Index組件的開發(fā)主管，他曾經(jīng)在波蘭的Wroclaw大學講授C++編程課程，而且他獲得了Wroclaw大學的理論物理學博士學位。 這是他為這本書管理的blog:http://www.relisoft.com/forums/index.php?s=ee4c0dc7cafef9f08c7c18a6e449b424&showforum=3，售后服務還不錯，呵呵，以我目前的水平看起來還挺累的，我想最好把C++ Primer和effective c++,more effective c++看完再看這本書會比較好，不過硬著頭皮看也有好處，就像有時候武俠小說里用非常規(guī)方法提高修為有時候也能起到意想不到的效果。言歸正傳，在這本書中多次用到哈希表，很多地方不明白，查了書整理一下。
散列表(hash table)的實現(xiàn)常稱為散列(hashing),散列是一種用于以常數(shù)平均時間執(zhí)行插入，刪除和查找的技術。但是，那些需要元素間任何排序信息的樹操作不會得到有效的支持。因此諸如findMin,findMax以及在線性時間內按順序打印整個表的操作都是散列所不支持的。
我們把表的大小記作TableSize,我們把每個鍵映射到從0到TableSize-1這個范圍中的某個數(shù)，并且將其放到適當?shù)膯卧小＿@個映射就稱為散列函數(shù)(hash function),理想情況下它應該運算簡單并且應該保證任何兩個不同的鍵映射到不同的單元。不過，這是不可能的。因此我們尋找一個散列函數(shù)，該函數(shù)要在單元之間均勻分配鍵。這就是散列的基本思想，剩下的問題則是要選擇一個函數(shù)，決定當兩個鍵散列到同一個值的時候(稱為(collision))應該做什么以及如何確定散列表的大小。
1.散列函數(shù)
如果輸入的鍵是整數(shù)，一般合理的方法就是直接返回"Key mod Tablesize",但Key具有某些不理想的性質，比如若表的大小是10而鍵的各位都是0。則此時上述標準的散列函數(shù)就不是一個好的選擇，好的辦法通常是保證表的大小是素數(shù)，當輸入的鍵是隨機整數(shù)時，散列函數(shù)不僅運算簡單而且鍵的分配也很均勻。
通常，鍵是字符串；在這種情形下，散列函數(shù)需要仔細選擇。
一種選擇方法是把字符串中字符的ASCII碼值加起來，下面的例程實現(xiàn)了這種策略。
1
int hash( const string &key, int tableSize )
2
{
3
int hashVal = 0;
4 for( int i=0; i<key.length(); i++ )
5 hashVal += key[i];
6 return hashVal % tableSize;
7
}
上述散列函數(shù)實現(xiàn)起來簡單而且能夠很快地算出答案。不過如果表很大，則函數(shù)就不會很好地分配鍵。例如，設TableSize=10007(10007是素數(shù))，并設所有的鍵至多8個字符長，由于ASCII字符的值最多是127，因此散列函數(shù)只能在0-1016之間取值，顯然這不是一種均勻的分配。
另一個散列函數(shù)如下表示，這個散列函數(shù)假設Key至少三個字符。值27表示英文字母表的字母個數(shù)外加一個空格，而729是27×27，該函數(shù)只考察前三個字符，但是如果它們是隨機的，而表的大小還是10007，那么我們就會得到一個合理的均衡分布。可是，英文不是隨機的。雖然3個字符（忽略空格）有26×26×26=17576種可能的組合，但查驗詞匯量足夠大的聯(lián)機詞典卻揭示出，3個字母的不同組合數(shù)實際上只有2851。即使這些組合沒有沖突，也不過只有表的28%被真正散列到。因此，雖然很容易計算，但是當散列表足夠大的時候這個函數(shù)還是不合適的。
1int hash( const string &key, int tableSize )
2{
3 return (key[0]+27*key[1]+729*key[2]) % tableSize
4}
下面的例程列出了第3種嘗試。這個散列函數(shù)涉及鍵中的所有字符，并且一般可以分布得很好，程序根據(jù)Horner法則計算一個37的多項式函數(shù)。這個散列函數(shù)利用了允許溢出這個事實。這可能會引進負數(shù)，因此在末尾有附加的測試，這個散列函數(shù)就表的分布而言未必是最好的，但是確實具有極其簡單的優(yōu)點而且速度也很快。如果鍵特別長，那么該散列函數(shù)計算起來將會花費過多的時間。在這種情況下通常做法是不使用所有的字符。此時鍵的長度和性質將影響選擇。例如，鍵可能是完整的街道地址，散列函數(shù)可以包括街道地址的幾個字符，或許也包括城市名和郵政編碼的幾個字符。有些程序設計人員通過只使用奇數(shù)位置上的字符來實現(xiàn)他們的散列函數(shù)，這里有這么一層想法：用計算散列函數(shù)節(jié)省下的時間來補償由此產(chǎn)生的對均勻分布的函數(shù)的輕微干擾。
1int hash( const string &key, int tableSize )
2{
3 int hashVal = 0;
4 for(int i=0;i<key.length();i++)
5 hashVal = 37 * hashVal + key[i];
6 hashVal %= tableSize;
7 if( hashVal <0 )
8 hashVal += tableSize;
9 return hashVal;
10}
剩下的主要編程細節(jié)是解決沖突。如果當一個元素在插入時與一個已經(jīng)插入的元素散列到相同的值，那么就產(chǎn)生一個沖突，這個沖突需要消除。
2.分離鏈接法
解決沖突的第一種方法通常稱為分離鏈接法(separate chaining),其做法是將散列到同一個值的所有元素保留到一個鏈表中，可以使用標準庫中表的實現(xiàn)方法。如果空間很緊，則更可取的方法是避免使用它們(因為這些表是雙向鏈表，浪費空間),為執(zhí)行search,我們使用散列函數(shù)來確定究竟該遍歷那個鏈表，然后查找相應的表。為執(zhí)行insert，我們檢查相應的表來確定是否該元素已經(jīng)在表中了(如果要插入重復元，那么通常要留出一個額外的數(shù)據(jù)成員，當出現(xiàn)匹配事件時這個數(shù)據(jù)成員增1),如果這個元素是個新的元素，那么它將被插入到表的前端，這不僅因為方便，而且還因為最后插入的元素最有可能不久再次被訪問，實現(xiàn)分離鏈接法所需要的類架構在下面的例程中給出。散列表結構存儲一個鏈表數(shù)組，這個數(shù)組在構造函數(shù)中指定。
1//分離鏈接散列表的類構架
2template <typename HashedObj>
3 class HashTable
4 {
5public:
6 explicit HashTable( int size = 101 );
7
8 bool contains( const HashedObj &x ) const;
9
10 void makeEmpty();
11 void insert( const HashedObj x);
12 void remove( const HashedObj x);
13
14 private:
15 vector<list<HashedObj> > theLists;// >>是c++的一個運算符，而且比>長，因此兩個>之間需要一個空格
16 int currentSize;
17
18 void rehash()
19 int myhash( const HashedObj &x ) const;
20};
21
22int hash( const string &key );
23int hash( int key );
24
25
這里不使用那些將對象和類的大小作為參數(shù)的散列函數(shù)，而是使用那些僅以對象為參數(shù)的散列函數(shù)，并且返回int。散列表類有一個私有的成員函數(shù)myhash,這個函數(shù)將結果分配到一個合適的數(shù)組索引中。
1int myhash( const HashedObj &x ) const
2{
3 int hashVal = hash(x);
4 hashVal %=theLists.size();
5 if( hashVal < 0)
6 hashVal += theLists.size();
7 return hashVal;
8}
9
10
下面的例程中列出了一個可以存儲在一般散列表中的Employee類，該類使用name成員作為鍵，Employee類通過提供相等性操作符和一個散列函數(shù)來實現(xiàn)HashedObj的需求。
1class Employee
2
{
3public:
4 const string & getname() const
5
{ return name; }
6 bool operator==( const Employee &rhs ) const
7 { return getName() == rhs.getName(); }
8 bool operator!=( const Employee & rhs } const
9 { return !(*this == rhs); }
10
11private:
12 string name;
13 double salary;
14 int seniority;
15};
16
17int hash( const Employ &item )
18{
19 return hash( item.getName() );
20}
實現(xiàn)makeEmpty,contains和remove的程序代碼如下
1void makeEmpty()
2 {
3 for( int i=0; i<theLists.size();i++ )
4 theLists[i].clear();
5}
6
7bool contains( const HashedObj &x ) const
8{
9 const list<HashedObj> & whichList = theLists[myhash(x)];
10 return find( whichList.begin(),whichList.end(),x) !=whichList.end();
11}
12
13bool remove( const HashedObj &x )
14{
15 list<HashedObj> &whichList = theLists[myhash(x)];
16 list<HashedObj>::iterator itr = find(whichList.begin(),whichList.end(),x);
17 if( itr == whichList.end() )
18 return false;
19 whichList.erase( itr );
20 --currentSize;
21 return true;
22}
下一個操作是插入例程。如果要插入的項已經(jīng)存在，那么什么都不做；否則將其放至表的前端。該元素可以放在表的任何地方；此處使用push_back是最方便的。whichList是一個引用變量
1bool insert ( const HashedObj &x )
2{
3 list<HashedObj> & whichList = theLists[ myhash(x) ];
4 if( find( whichList.begin(),whichList.end(),x )!=whichList.end() )
5 return false;
6 whichList.push_back(x);
7
8 if(++currentSize > theLists.size() )
9 rehash();
10
11 return true;
12}