第一章 素?cái)?shù)判定法現(xiàn)狀
現(xiàn)在，確定性素?cái)?shù)判定法已經(jīng)有很多種，常用的有試除法、威廉斯方法、艾德利曼和魯梅利法。它們的適用范圍各不相同，威廉斯方法比較適合10^20到10^50之間的數(shù)，艾德利曼和魯梅利法適合大于10^50的數(shù)，對(duì)于32位機(jī)器數(shù)，由于都小于10^10，所以一般都用試除法來(lái)判定。
也許有人會(huì)問(wèn)：“你為什么沒(méi)有提馬寧德拉.阿格拉瓦法呢？不是有人說(shuō)它是目前最快的素?cái)?shù)判定法嗎？” 其實(shí)這是一個(gè)很大的誤解，阿格拉瓦法雖然是log(n)的多項(xiàng)式級(jí)算法，但目前只有理論上的意義，根本無(wú)法實(shí)用，因?yàn)樗臅r(shí)間復(fù)雜度是O(log(n)^12)，這個(gè)多項(xiàng)式的次數(shù)太高了。就拿最慢的試除法跟它來(lái)比吧，試除法的時(shí)間復(fù)雜度為O(n^(1/2)*log(n)^2)，當(dāng)n = 16時(shí)，log(n)^12 = 16777216，而n^(1/2)*log(n)^2 = 64，你看相差有多么大！如果要讓兩者速度相當(dāng)，即log(n)^12 = n^(1/2)*log(n)^2，得出n = 10^43.1214，此時(shí)需要進(jìn)行的運(yùn)算次數(shù)為log(n)^12 = 10^25.873（注意：本文中log（）函數(shù)缺省以2為底），這樣的運(yùn)算次數(shù)在一臺(tái)主頻3GHz的計(jì)算機(jī)上運(yùn)行也要10^8.89707年才能運(yùn)行完，看來(lái)我們這輩子是別指望看到阿格拉瓦法比試除法快的這一天啦！
除了這些確定性素?cái)?shù)判定法外，還有基于概率的非確定性素?cái)?shù)判定法，最常用的就是米勒-拉賓法。
對(duì)于32位機(jī)器數(shù)（四則運(yùn)算均為常數(shù)時(shí)間完成），試除法的時(shí)間復(fù)雜度是O(n^(1/2))，而米勒-拉賓法的時(shí)間復(fù)雜度只有O(log(n))。所以后者要比前者快得多，但是由于米勒-拉賓法的非確定性，往往我們?cè)谛枰_定解時(shí)仍然要依靠速度較慢的試除法。那是否可以通過(guò)擴(kuò)展米勒-拉賓法，來(lái)找到一種更快的確定性素?cái)?shù)判定法呢？結(jié)論是肯定的，本文就帶你一起尋找這樣一種方法。
第二章 2-偽素?cái)?shù)表的生成
既然要擴(kuò)展米勒-拉賓法，那首先我們應(yīng)該知道為什么米勒-拉賓法是個(gè)非確定性素?cái)?shù)判定法？答案很簡(jiǎn)單，由于偽素?cái)?shù)的存在。由于米勒-拉賓法使用費(fèi)爾馬小定理的逆命題進(jìn)行判斷，而該逆命題對(duì)極少數(shù)合數(shù)并不成立，從而產(chǎn)生誤判，這些使費(fèi)爾馬小定理的逆命題不成立的合數(shù)就是偽素?cái)?shù)。為了研究偽素?cái)?shù)，我們首先需要生成偽素?cái)?shù)表，原理很簡(jiǎn)單，就是先用篩法得出一定范圍內(nèi)的所有素?cái)?shù)，然后逐一判定該范圍內(nèi)所有合數(shù)是否使以2為底數(shù)的費(fèi)爾馬小定理的逆命題不成立，從而得出該范圍內(nèi)的2-偽素?cái)?shù)表。我的程序運(yùn)行了100分鐘，得出了32位機(jī)器數(shù)范圍內(nèi)的2-偽素?cái)?shù)表，如下：
341
561
645
1105
1387
1729
1905
2047
2465
2701
...
...
...
4286813749
4288664869
4289470021
4289641621
4289884201
4289906089
4293088801
4293329041
4294868509
4294901761
（共10403個(gè)，由于篇幅所限，中間部分省略。）
第三章 尋找2-偽素?cái)?shù)的最小可判定底數(shù)
對(duì)于2-偽素?cái)?shù)表的每一個(gè)偽素?cái)?shù)，尋找最小的可以判定它們是合數(shù)的底數(shù)，我把這個(gè)底數(shù)稱之為最小可判定底數(shù)。特別地，對(duì)于絕對(duì)偽素?cái)?shù)，它的最小質(zhì)因子即是它的最小可判定底數(shù)。由于已經(jīng)證明了絕對(duì)偽素?cái)?shù)至少有三個(gè)質(zhì)因子，所以這個(gè)最小質(zhì)因子一定不大于n^(1/3)。下面就是我找到的最小可判定底數(shù)列表：
341 3
561 3
645 3
1105 5
1387 3
1729 7
1905 3
2047 3
2465 5
2701 5
...
...
...
4286813749 3
4288664869 3
4289470021 5
4289641621 3
4289884201 3
4289906089 3
4293088801 3
4293329041 3
4294868509 7
4294901761 3
通過(guò)統(tǒng)計(jì)這個(gè)列表，我發(fā)現(xiàn)了一個(gè)規(guī)律，那就是所有的最小可判定底數(shù)都不大于n^(1/3)，由前述可知，對(duì)于絕對(duì)偽素?cái)?shù)，這個(gè)結(jié)論顯然成立。而對(duì)于非絕對(duì)偽素?cái)?shù)，雖然直觀上覺(jué)得它應(yīng)該比絕對(duì)偽素?cái)?shù)好判定出來(lái)，但是我無(wú)法證明出它的最小可判定底數(shù)都不大于n^(1/3)。不過(guò)沒(méi)關(guān)系，這個(gè)問(wèn)題就作為一個(gè)猜想留給數(shù)學(xué)家來(lái)解決吧，更重要的是我已經(jīng)通過(guò)實(shí)驗(yàn)證明了在32位機(jī)器數(shù)范圍內(nèi)這個(gè)結(jié)論成立。
我們還有沒(méi)有更好的方法來(lái)進(jìn)一步減小最小可判定底數(shù)的范圍呢？有的！我們可以在計(jì)算平方數(shù)時(shí)進(jìn)行二次檢測(cè)，下面是進(jìn)行了二次檢測(cè)后重新計(jì)算的最小可判定底數(shù)列表：
341 2
561 2
645 2
1105 2
1387 2
1729 2
1905 2
2047 3
2465 2
2701 2
...
...
...
4286813749 2
4288664869 2
4289470021 2
4289641621 2
4289884201 2
4289906089 2
4293088801 2
4293329041 2
4294868509 2
4294901761 3
很顯然，二次檢測(cè)是有效果的，經(jīng)過(guò)統(tǒng)計(jì)，我發(fā)現(xiàn)了新的規(guī)律，那就是經(jīng)過(guò)二次檢測(cè)后所有的最小可判定底數(shù)都不大于n^(1/6)，真的是開(kāi)了一個(gè)平方呀，哈哈！這個(gè)結(jié)論的數(shù)學(xué)證明仍然作為一個(gè)猜想留給數(shù)學(xué)家們吧。我把這兩個(gè)猜想叫做費(fèi)爾馬小定理可判定上界猜想。而我已經(jīng)完成了對(duì)32位機(jī)器數(shù)范圍內(nèi)的證明。
通過(guò)上面總結(jié)的規(guī)律，我們已經(jīng)可以設(shè)計(jì)出一個(gè)對(duì)32位機(jī)器數(shù)進(jìn)行素?cái)?shù)判定的 O(n^(1/6)*log(n)) 的確定性方法。但是這還不夠，我們還可以優(yōu)化，因?yàn)榇藭r(shí)的最小可判定底數(shù)列表去重后只剩下了5個(gè)數(shù)（都是素?cái)?shù)）：{2,3,5,7,11}。天哪，就是前5個(gè)素?cái)?shù)，這也太容易記憶了吧。
不過(guò)在實(shí)現(xiàn)算法時(shí)，需要注意這些結(jié)論都是在2-偽素?cái)?shù)表基礎(chǔ)上得來(lái)的，也就是說(shuō)不管如何對(duì)2的判定步驟必不可少，即使當(dāng)2>n^(1/6)時(shí)。
還有一些優(yōu)化可以使用，經(jīng)過(guò)實(shí)驗(yàn)，當(dāng)n>=7^6時(shí)，可以不進(jìn)行n^(1/6)上界限制，而固定地用{2,5,7,11}去判定，也是100%正確的。這樣就可以把判定次數(shù)降為4次以下，而每次判定只需要進(jìn)行4log(n)次乘除法（把取余運(yùn)算也看作除法），所以總的計(jì)算次數(shù)不會(huì)超過(guò)16log(n)。經(jīng)過(guò)實(shí)驗(yàn)，最大的計(jì)算次數(shù)在n=4294967291時(shí)出現(xiàn)，為496次。
自己寫(xiě)了個(gè)隨機(jī)化素?cái)?shù)判定算法：
1 #include <iostream>
2 #include <cmath>
3 #include <algorithm>
4
5 using namespace std;
6 typedef unsigned __int64 longlong_t;
7
8 bool _IsLikePrime(longlong_t n, longlong_t base)
9 {
10 longlong_t power = n-1;
11 longlong_t result = 1;
12 longlong_t x = result;
13 longlong_t bits = 0;
14 longlong_t power1 = power;
15 //統(tǒng)計(jì)二進(jìn)制位數(shù)
16 while (power1 > 0)
17 {
18 power1 >>= 1;
19 bits++;
20 }
21 //從高位到低位依次處理power的二進(jìn)制位
22 while(bits > 0)
23 {
24 bits--;
25 result = (x*x)%n;
26 //二次檢測(cè)
27 if(result==1&&x!=1&&x!=n-1)
28 return false;
29
30 if ((power&((longlong_t)1<<bits)) != 0)
31 result = (result*base)%n;
32
33 x = result;
34 }
35 //費(fèi)爾馬小定理逆命題判定
36 return result == 1;
37 }
38 inline bool JudgePrime(int n,int s)
39 {
40 srand(20);
41 for(int i=0;i<s;i++){
42 int a=rand()%(n-1)+1;
43 if(!_IsLikePrime(n,a))
44 return false;
45 }
46 return true;
47 }
48 int main()
49 {
50 int n;
51 while(scanf("%d",&n)!=EOF){
52 int num=0;
53 int cnt=0;
54 for(int i=0;i<n;i++){
55 scanf("%d",&num);
56 if(JudgePrime(num,20))
57 cnt++;
58 }
59 printf("%d\n",cnt);
60 }
61 return 0;
62 }
s越大，穩(wěn)定性越好，但效率會(huì)低點(diǎn)。原作者有更好的判定算法，對(duì)作者表示感謝。。
1
#include <iostream>
2#include <string>
3#include <algorithm>
4#include <hash_map>
5
6using namespace std;
7
8
struct hashable
{
9
string i;
10
hashable(string iv):i(iv){}
11 operator size_t()const{
12 int ret=i.size();
13 for(int k=0;k!=i.size();++k){
14 ret*=10;
15 ret+=i[k]-'A';
16
}
17 return ret;
18 }
19 bool operator< (hashable r)const {
20 return i<r.i;
21 }
22
};
23int main()
24{
25 hash_map<hashable,string> hm;
26 hashable a("1");
27 hm[a]="T";
28 cout<<hm[a]<<endl;
29}
對(duì)自定義類型到string的示例
Reference Type 和 Pointer Type
所謂左值（lValue）：是用來(lái)代表某個(gè)對(duì)象的一個(gè)東西。如果p是指向類型為T的某個(gè)對(duì)象，那么表達(dá)式*p不能只是返回類型為T的對(duì)象，而必須是返回一個(gè)lValue（左值）。
平時(shí)總是拿起*p就直接賦值（對(duì)于簡(jiǎn)單基本類型，例如int *p = &I ; *p=3），沒(méi)想什么*p返回左值那么多。但是當(dāng)在自定義類中重栽*運(yùn)算符的時(shí)候，我們就要特別小心，要注意到這點(diǎn)，返回為T& 才對(duì)。
言規(guī)正傳
iterator_traits的某些機(jī)制所蘊(yùn)涵的意義十分微妙而深遠(yuǎn)，不過(guò)它的實(shí)現(xiàn)卻不是很復(fù)雜，不過(guò)這些東西看起來(lái)比較容易看懂，真正能夠靈活使用就需要花時(shí)間領(lǐng)悟了，為什么會(huì)采取這種方法解決問(wèn)題，和其它的方法對(duì)比有什么好處和提高？這種明白這些問(wèn)題才算掌握了trait的實(shí)質(zhì)。
template< class Iterator>
struct iterator_traits
{
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference ;
};
template< class T>
struct iterator_traits
{
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference ;
};
template< class T>
struct iterator_traits
{
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference ;
};
當(dāng)你定義一個(gè)自己的算法，你需要關(guān)注這個(gè)機(jī)制，下面兩個(gè)理由就是你可能要用到iterator_traits：
① 你必須返回某值，或者是申明臨時(shí)變量，而其它型別與iterator的value type 或者different type或者reference type 或者pointer type一致。
② 你的算法類似與advance，必須根據(jù)iterator的分類來(lái)決定不同的實(shí)現(xiàn)方法（提高效率，在編譯時(shí)候進(jìn)行判斷而不是在運(yùn)行的時(shí)候進(jìn)行判斷），沒(méi)有traits機(jī)制，你只好在‘一般化但是沒(méi)效率’或者‘有效率但是過(guò)度狹隘’中進(jìn)行抉擇。
當(dāng)定義一個(gè)Iterator 類，就得在改類中定義五個(gè)嵌套的類型，如上面的五個(gè)所示。要不然就得針對(duì)你的Iterator類，明白的令iterator_traits為Iterator特化，就像iterator_traits要明白的針對(duì)指針而特化一樣。第一種做法總是比較簡(jiǎn)單，尤其是STL的一個(gè)輔助類，base class iterator，讓事情變得更簡(jiǎn)單了。
template< class Category,
class Value,
class Distance =ptrdiff_t,
class Pointer = Value*,
class Reference = Value &
>
struct iterator
{
typedef Category iterator_category;
typedef Value value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
為了確保iterator_traits能夠?qū)π碌?/span>iterator class有適當(dāng)?shù)亩x，最簡(jiǎn)單的方法就是從iterator類派生自己的iterator。基類iterator不含任何成員函數(shù)和成員變量，所以繼承不存在額外的開(kāi)銷。
說(shuō)來(lái)慚愧，使用了很久Visual Stdio 2003了，只知道MFC升級(jí)到了7.0，ATL也升級(jí)到了7.0，對(duì)于這兩個(gè)經(jīng)典的類庫(kù)做了一些研究，但一直沒(méi)有注意C++標(biāo)準(zhǔn)庫(kù)的變化。
今天嘗試的使用了stdext::hash_map這個(gè)庫(kù)，果然不錯(cuò)。下面寫(xiě)下一些心得。
hash_map類在頭文件hash_map中，和所有其它的C++標(biāo)準(zhǔn)庫(kù)一樣，頭文件沒(méi)有擴(kuò)展名。如下聲明：
#include <hash_map>
using namespace std;
using namespace stdext;
hash_map是一個(gè)聚合類，它繼承自_Hash類，包括一個(gè)vector，一個(gè)list和一個(gè)pair，其中vector用于保存桶，list用于進(jìn)行沖突處理，pair用于保存key->value結(jié)構(gòu)，簡(jiǎn)要地偽碼如下：
class hash_map<class _Tkey, class _Tval>
{
private:
typedef pair<_Tkey, _Tval> hash_pair;
typedef list<hash_pair> hash_list;
typedef vector<hash_list> hash_table;
};
當(dāng)然，這只是一個(gè)簡(jiǎn)單模型，C++標(biāo)準(zhǔn)庫(kù)的泛型模版一向以嵌套復(fù)雜而聞名，初學(xué)時(shí)看類庫(kù)，無(wú)疑天書(shū)啊。微軟的hash_map類還聚合了hash_compare仿函數(shù)類，hash_compare類里有聚合了less仿函數(shù)類，亂七八糟的。
下面說(shuō)說(shuō)使用方法：
一、簡(jiǎn)單變量作為索引：整形、實(shí)性、指針型
其實(shí)指針型也就是整形，算法一樣。但是hash_map會(huì)對(duì)char*, const char*, wchar_t*, const wchar_t*做特殊處理。
這種情況最簡(jiǎn)單，下面代碼是整形示例：
hash_map<int, int> IntHash;
IntHash[1] = 123;
IntHash[2] = 456;
int val = IntHash[1];
int val = IntHash[2];
實(shí)型和指針型用法和整形一樣，原理如下：
1、使用簡(jiǎn)單類型作索引聲明hash_map的時(shí)候，不需要聲明模版的后兩個(gè)參數(shù)（最后一個(gè)參數(shù)指名hash_map節(jié)點(diǎn)的存儲(chǔ)方式，默認(rèn)為pair，我覺(jué)得這就挺好，沒(méi)必要修改），使用默認(rèn)值就好。
2、對(duì)于除過(guò)字符串的其它簡(jiǎn)單類型，hash_map使用模版函數(shù) size_t hash_value(const _Kty& _Keyval) 計(jì)算hash值，計(jì)算方法是經(jīng)典的掩碼異或法，自動(dòng)溢出得到索引hash值。微軟的工程師也許開(kāi)了一個(gè)玩笑，這個(gè)掩碼被定義為0xdeadbeef(死牛肉，抑或是某個(gè)程序員的外號(hào)）。
3、對(duì)于字符串指針作索引的時(shí)候，使用定類型函數(shù)inline size_t hash_value(const char *_Str)或inline size_t hash_value(const wchar_t *_Str)計(jì)算hash值，計(jì)算方法是取出每一個(gè)字符求和，自動(dòng)溢出得到hash值。對(duì)于字符串型的hash索引，要注意需要自定義less仿函數(shù)。
因?yàn)槲覀冇欣碛烧J(rèn)為，人們使用hash表進(jìn)行快速查找的預(yù)期成本要比在hash表中插入的預(yù)期成本低得多，所以插入可以比查找昂貴些；基于這個(gè)假設(shè)，hash_map在有沖突時(shí)，插入鏈表是進(jìn)行排序插入的，這樣在進(jìn)行查詢沖突解決的時(shí)候就能夠更快捷的找到需要的索引。
但是，基于泛型編程的原則，hash_map也有理由認(rèn)為每一種類型都支持使用"<"來(lái)判別兩個(gè)類型值的大小，這種設(shè)計(jì)恰好讓字符串類型無(wú)所適從，眾所周知，兩個(gè)字符串指針的大小并不代表字符串值的大小。見(jiàn)如下代碼：
hash_map<const char*, int> CharHash;
CharHash["a"] = 123;
CharHash["b"] = 456;
char szInput[64] = "";
scanf("%s", szInput);
int val = CharHash[szInput];
最終的結(jié)果就是無(wú)論輸入任何字符串，都無(wú)法找到對(duì)應(yīng)的整數(shù)值。因?yàn)檩斎氲淖址羔樖莝zInput指針，和"a"或"b"字符串常量指針的大小是絕對(duì)不會(huì)相同。解決方法如下：
首先寫(xiě)一個(gè)仿函數(shù)CharLess，繼承自仿函數(shù)基類binary_function（當(dāng)然也可以不繼承，這樣寫(xiě)只是符合標(biāo)準(zhǔn)，而且寫(xiě)起來(lái)比較方便，不用被類似于指針的指針和指針的引用搞暈。
struct CharLess : public binary_function<const char*, const char*, bool>
{
public:
result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
{
return(stricmp(_Left, _Right) < 0 ? true : false);
}
};
很好，有了這個(gè)仿函數(shù)，就可以正確的使用字符串指針型hash_map了。如下：
hash_map<const char*, int, hash_compare<const char*, CharLess> > CharHash;
CharHash["a"] = 123;
CharHash["b"] = 456;
char szInput[64] = "";
scanf("%s", szInput);
int val = CharHash[szInput];
現(xiàn)在就可以正常工作了。至此，簡(jiǎn)單類型的使用方法介紹完畢。
二、用戶自定義類型：比如對(duì)象類型，結(jié)構(gòu)體。
這種情況比價(jià)復(fù)雜，我們先說(shuō)簡(jiǎn)單的，對(duì)于C++標(biāo)準(zhǔn)庫(kù)的string類。
慶幸的是，微軟為basic_string（string類的基類）提供了hash方法，這使得使用string對(duì)象做索引簡(jiǎn)單了許多。值得注意（也值得郁悶）的是，雖然支持string的hash，string類卻沒(méi)有重載比較運(yùn)算符，所以標(biāo)準(zhǔn)的hash_compare仿函數(shù)依舊無(wú)法工作。我們繼續(xù)重寫(xiě)less仿函數(shù)。
struct string_less : public binary_function<const string, const string, bool>
{
public:
result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
{
return(_Left.compare(_Right) < 0 ? true : fase);
}
};
好了，我們可以書(shū)寫(xiě)如下代碼：
hash_map<string, int, hash_compare<string, string_less> > StringHash;
StringHash["a"] = 123;
StringHash["b"] = 456;
string strKey = "a";
int val = CharHash[strKey];
這樣就可以了。
對(duì)于另外的一個(gè)常用的字符串類CString（我認(rèn)為微軟的CString比標(biāo)準(zhǔn)庫(kù)的string設(shè)計(jì)要灑脫一些）更加復(fù)雜一些。很顯然，標(biāo)準(zhǔn)庫(kù)里不包含對(duì)于CString的支持，但CString卻重載了比較運(yùn)算符（郁悶）。我們必須重寫(xiě)hash_compare仿函數(shù)。值得一提的是，在Virtual Stdio 2003中，CString不再是MFC的成員，而成為ATL的成員，使用#include <atlstr.h>就可以使用。我沒(méi)有采用重寫(xiě)hash_compare仿函數(shù)的策略，而僅僅是繼承了它，在模版庫(kù)中的繼承是沒(méi)有性能損耗的，而且能讓我偷一點(diǎn)懶。
首先重寫(xiě)一個(gè)hash_value函數(shù)：
inline size_t CString_hash_value(const CString& str)
{
size_t value = _HASH_SEED;
size_t size = str.GetLength();
if (size > 0) {
size_t temp = (size / 16) + 1;
size -= temp;
for (size_t idx = 0; idx <= size; idx += temp) {
value += (size_t)str[(int)idx];
}
}
return(value);
}
其次重寫(xiě)hash_compare仿函數(shù)：
class CString_hash_compare : public hash_compare<CString>
{
public:
size_t operator()(const CString& _Key) const
{
return((size_t)CString_hash_value(_Key));
}
bool operator()(const CString& _Keyval1, const CString& _Keyval2) const
{
return (comp(_Keyval1, _Keyval2));
}
};
上面的重載忽略了基類對(duì)于less仿函數(shù)的引入，因?yàn)镃String具備比較運(yùn)算符，我們可以使用默認(rèn)的less仿函數(shù)，在這里映射為comp。好了，我們可以聲明新的hash_map對(duì)象如下：
hash_map<CString, int, CString_hash_compare> CStringHash;
其余的操作一樣一樣的。
下來(lái)就說(shuō)說(shuō)對(duì)于自定義對(duì)象的使用方法：首先定義
struct IHashable
{
virtual unsigned long hash_value() const = 0;
virtual bool operator < (const IHashable& val) const = 0;
virtual IHashable& operator = (const IHashable& val) = 0;
};
讓我們自寫(xiě)的類都派生自這里，有一個(gè)標(biāo)準(zhǔn)，接下來(lái)定義我們的類：
class CTest : public IHashable
{
public:
int m_value;
CString m_message;
public:
CTest() : m_value(0)
{
}
CTest(const CTest& obj)
{
m_value = obj.m_value;
m_message = obj.m_message;
}
public:
virtual IHashable& operator = (const IHashable& val)
{
m_value = ((CTest&)val).m_value;
m_message = ((CTest&)val).m_message;
return(*this);
}
virtual unsigned long hash_value() const
{
// 這里使用類中的m_value域計(jì)算hash值，也可以使用更復(fù)雜的函數(shù)計(jì)算所有域總的hash值
return(m_value ^ 0xdeadbeef
}
virtual bool operator < (const IHashable& val) const
{
return(m_value < ((CTest&)val).m_value);
}
};
用這個(gè)類的對(duì)象做為hash索引準(zhǔn)備工作如下，因?yàn)榻涌谥幸?guī)定了比較運(yùn)算符，所以這里可以使用標(biāo)準(zhǔn)的less仿函數(shù)，所以這里忽略：
template<class _Tkey>
class MyHashCompare : public hash_compare<_Tkey>
{
public:
size_t operator()(const _Tkey& _Key) const
{
return(_Key.hash_value());
}
bool operator()(const _Tkey& _Keyval1, const _Tkey& _Keyval2) const
{
return (comp(_Keyval1, _Keyval2));
}
};
下來(lái)就這樣寫(xiě)：
CTest test;
test.m_value = 123;
test.m_message = "This is a test";
MyHash[test] = 2005;
int val = MyHash[test];
可以看到正確的數(shù)字被返回。
三、關(guān)于hash_map的思考：
1、性能分析：采用了內(nèi)聯(lián)代碼和模版技術(shù)的hash_map在效率上應(yīng)該是非常優(yōu)秀的，但我們還需要注意如下幾點(diǎn)：
* 經(jīng)過(guò)查看代碼，字符串索引會(huì)比簡(jiǎn)單類型索引速度慢，自定義類型索引的性能則和我們選擇hash的內(nèi)容有很大關(guān)系，簡(jiǎn)單為主，這是使用hash_map的基本原則。
* 可以通過(guò)重寫(xiě)hash_compair仿函數(shù)，更改里面關(guān)于桶數(shù)量的定義，如果取值合適，也可以得到更優(yōu)的性能。如果桶數(shù)量大于10，則牢記它應(yīng)該是一個(gè)質(zhì)數(shù)。
* 在自定義類型是，重載的等號(hào)（或者拷貝構(gòu)造）有可能成為性能瓶頸，使用對(duì)象指針最為索引將是一個(gè)好的想法，但這就必須重寫(xiě)less仿函數(shù)，理由同使用字符串指針作為索引。
想自己開(kāi)始學(xué)語(yǔ)言的時(shí)候，因?yàn)楦静恢朗裁磿?shū)好，所以看到基本是一些國(guó)內(nèi)的，水平一般的書(shū)，如果你剛開(kāi)始學(xué)c or c++,推薦c++創(chuàng)始人寫(xiě)的<<the c++ programming language>>,即使是學(xué)有所成的人，再看此書(shū)也有很大收獲我想，慢慢品味，會(huì)有收獲的。。。以后我會(huì)將自己學(xué)習(xí)此書(shū)的筆記寫(xiě)在此，各位路過(guò)的大牛指點(diǎn)指點(diǎn)。。。^_^