MAP原理及其在MFC中的實(shí)現(xiàn)

MAP原理及其在MFC中的實(shí)現(xiàn)2009-12-2314:02一、Map的基本知識映射（Map），又稱為字典（Dictionary），是由關(guān)鍵字（Key）及其對應(yīng)的元素值（Value）所組成的元素單元（Element）的表單式集合。通常，對于Map而言，使用給定的Key，可以迅速地從單元集合中檢索到相應(yīng)的元素。因此，在需要對大量數(shù)據(jù)進(jìn)行查找操作而查找的性能又占據(jù)重要地位的場合，Map無疑是一種較理想的容器。譬如，在MFC中，使用Map來實(shí)現(xiàn)HandleMaps（句柄映射），以及其他的一些內(nèi)部數(shù)據(jù)結(jié)構(gòu)。同時(shí)，MFC也提供了公共Map類。使用公共Map類，MFC程序員可以輕易地高效地根據(jù)自身的需求實(shí)現(xiàn)程序中自定義的映射。通常，當(dāng)一個(gè)Map對象被刪除時(shí)，或者，當(dāng)其中的元素被移除時(shí)，關(guān)鍵字和元素值也將被完全刪除。從數(shù)據(jù)結(jié)構(gòu)的角度分析，有關(guān)Map的典型操作有：1、 向Map中插入具有給定關(guān)鍵字的元素單元。2、 在Map中查找具有給定關(guān)鍵字的元素單元。3、 在Map中刪除具有給定關(guān)鍵字的元素單元。4、 枚舉（遍歷）Map中的所有元素單元。MFC中的各種Map實(shí)現(xiàn)，都提供了實(shí)現(xiàn)上述操作的成員函數(shù)。為了方便討論，我們以CMap為代表，進(jìn)行講解。一旦你已經(jīng)向Map中插入了一個(gè)關(guān)鍵字-元素值組合對（Key-Valuepair）單元，就可以利用關(guān)鍵字訪問Map，從而有效地檢索、添加或者刪除元素單元，也可以遍歷Map中的所有單元。對MFC中的CMap等，除了關(guān)鍵字訪問方法之外，還有另一種不同的類型--POSITION，也可以作為訪問元素單元的輔助方式，可以使用一個(gè)POSITION來〃記住"一個(gè)元素單元或者對Map進(jìn)行枚舉操作。你可能認(rèn)為這種使用POSITION實(shí)現(xiàn)的遍歷等同于使用關(guān)鍵字來進(jìn)行的Map遍歷，事實(shí)上并非如此，確切的說，兩種檢索的等價(jià)性是不確定的。MFC中的提供了基于模板的CMap類。利用CMap模板類，可以處理特定的數(shù)據(jù)類型，例如用戶自定義的類或結(jié)構(gòu)體等。同時(shí)，MFC也提供了基于指定數(shù)據(jù)類型的非模板類，其中包括：類名關(guān)鍵字類型元素值類型CMapWordToPtrWORDSVoidpointersCMapPtrToWordVoidpointersWORDSCMapPtrToPtrVoidpointersVoidpointersCMapWordToObWORDSObjectsCMapStringToObStringsObjectsCMapStringToPtrStringsVoidpointersCMapStringToStringStringsString、Map的工作原理使用Map的最大優(yōu)勢是它的快速查找的優(yōu)秀性能，而取得最優(yōu)性能的關(guān)鍵在于盡量使得在檢索周期內(nèi)所需進(jìn)行的元素檢查（比對）次數(shù)達(dá)到最少。順序查找的性能是最差的，因?yàn)槿绻褂庙樞虿檎宜惴ㄔ诎琻個(gè)元素單元的Map中查找某個(gè)元素，可能（最壞情況下）需要進(jìn)行n次獨(dú)立的比較運(yùn)算。二元查找（折中查找）的性能表現(xiàn)要稍好一些，可是，一個(gè)不容忽視的問題是一二元查找要求待查序列為有序排列，這無疑會降低Map自身的操作靈活性。在我們的理解中，所謂的最佳算法應(yīng)當(dāng)是不論元素單元數(shù)目的多少，也不論元素是以什么順序進(jìn)行排列，查找過程都無需任何額外的比對操作，而能夠僅僅通過簡單的計(jì)算方法，就可以直接指向最終的相應(yīng)元素的快速、高效算法。這聽起來有些玄乎，但事實(shí)上，這種算法的確是有可能實(shí)現(xiàn)的（而且，我相信，Map可以做得到）。在MFC的CMap及其相關(guān)的Map類中，只要對Map進(jìn)行正確設(shè)置，Lookup函數(shù)通常能夠一次到位的查找到任意元素，而很少需要進(jìn)行兩次或者三次以上的查找比對。那么，這種高效的查找是如何實(shí)現(xiàn)的呢？不失一般性，以MFC中的CMap模板類為例。在Map被創(chuàng)建之后（通常是恰恰在第一個(gè)元素被插入之前的瞬間），系統(tǒng)會為一個(gè)指向CAssoc結(jié)構(gòu)體的指針數(shù)組的哈希表分配內(nèi)存。MFC使用CAssoc結(jié)構(gòu)體描述元素值和關(guān)鍵字的組合對。CAssoc結(jié)構(gòu)體描述如下：structCAssoc{CAssoc*pNext;UINTnHashValue;CStringkey;CStringvalue;};無論何時(shí)，只要有一個(gè)元素值-關(guān)鍵字單元被加入到Map中，就會隨之創(chuàng)建一個(gè)新的CAssoc結(jié)構(gòu)體，并根據(jù)單元中的關(guān)鍵字的實(shí)際值來計(jì)算出相應(yīng)的哈希值。同時(shí)，拷貝一個(gè)指向CAssoc結(jié)構(gòu)體的指針并將其插入到哈希表中索引值為i的位置中。其中，i的計(jì)算公式如下：i=nHashValue%nHushTableSize式中，nHashValue是由關(guān)鍵字Key的實(shí)際值計(jì)算出來的哈希值；nHashTableSize是哈希表中元素的數(shù)目（默認(rèn)情況下，哈希表的大小為17）。如果在哈希表中的索引值為i的位置已經(jīng)容納了一個(gè)CAssoc指針，那么MFC將建立一個(gè)單獨(dú)的CAssoc結(jié)構(gòu)體的鏈表（List）,鏈表中的第一個(gè)CAssoc結(jié)構(gòu)體的地址被存儲到哈希表中，而將第二個(gè)CAssoc結(jié)構(gòu)體的地址存儲到前一個(gè)CAssoc結(jié)構(gòu)體的pNext域，以此類推。下圖展示了哈希表的一種可能實(shí)現(xiàn)情況，在該哈希表中，共有10個(gè)元素，其中5個(gè)元素地址分別唯一的存儲，另外5個(gè)分別存儲在長度為2和3的兩個(gè)鏈表中。調(diào)用一個(gè)Map的Lookup（）函數(shù)時(shí),MFC根據(jù)輸入的關(guān)鍵字的實(shí)際值計(jì)算相應(yīng)的哈希值，然后使用前面提到的公式將哈希值轉(zhuǎn)換為索引值，并從哈希表中的相應(yīng)位置檢索CAssoc指針。理想情況下，該位置只包含一個(gè)CAssoc指針，而非CAssoc指針鏈表。如果事實(shí)情況真如同我們所期望的那樣，單一地址對應(yīng)單一CAssoc指針，那么，元素單元將能夠被一次查找到位，并直接讀出；如果從哈希表中檢索到的是CAssoc鏈表的指針頭地址，則MFC順序比對鏈表元素CAssoc結(jié)構(gòu)所包含的關(guān)鍵字，直至查找到正確結(jié)果。但是，正如我們先前所討論的那樣，只要正確設(shè)置Map，鏈表中的元素一般就不會超過三個(gè)，這就意味著，查找通?？梢栽谌卧乇葘Σ僮髦畠?nèi)完成。三、優(yōu)化查找效率在MFC的Map中，查找性能主要依賴于兩個(gè)因素：1、 哈希表的大小2、 盡可能產(chǎn)生唯一哈希值的優(yōu)異算法哈希表的大小對于Map的查找性能而言，是非常重要的。舉個(gè)簡單的例子，如果有一個(gè)Map要容納1000個(gè)元素單元，但是哈希表卻只能提供17個(gè)存放CAssoc指針的空間，那么，即使是最佳情況，哈希表中的每個(gè)CAssoc鏈表中也將包含58或59個(gè)CAssoc結(jié)構(gòu)體，自然，在這種情況下，查找性能將受到嚴(yán)重阻礙。哈希算法亦是影響查找效率的重要因素之一。如果所使用的哈希算法只能產(chǎn)生少量的不同哈希值(從而也只能產(chǎn)生少量的不同的哈希表索引值)，查找性能也同樣將被降低。優(yōu)化Map查找性能的最有效途徑是盡可能的增大哈希表以降低因索引值相同而產(chǎn)生沖突的可能。微軟推薦將哈希表的大小設(shè)置為Map中所存儲元素?cái)?shù)目的110%?120%,以使得Map的應(yīng)用性能在內(nèi)存消耗和查找效率之間取得相對平衡。在MFC中，指定哈希表大小，可調(diào)用InitHashTable()函數(shù)：map.InitHashTable(1200);式中，假設(shè)Map中要存儲1000個(gè)元素，按照微軟公司的推薦，將哈希表的大小擴(kuò)展到實(shí)際存儲元素?cái)?shù)目的120%，即設(shè)置Map大小為1200。從統(tǒng)計(jì)學(xué)上考慮，實(shí)用奇數(shù)作為哈希表的大小也將有助于減少沖突的發(fā)生。因此，初始化一個(gè)存儲1000個(gè)元素的哈希表的InitHashTableO函數(shù)可以如下形式使用：map.InitHashTable(1201);同時(shí)，在InitHashTable()函數(shù)的調(diào)用時(shí)機(jī)上，應(yīng)該注意的是，該函數(shù)應(yīng)當(dāng)在map包含有任何元素之前使。如果map中已經(jīng)包含了一個(gè)或者更多的元素，那么，重新改變map的大小，將會引發(fā)斷言(Assertion)錯(cuò)誤。盡管MFC中所使用的哈希算法能夠適應(yīng)于大多數(shù)場合，但如果您真的有所需要，或者，只要你愿意，用戶也可以使用自己的算法來取代原有的算法。對于一個(gè)輸入的關(guān)鍵字的值，要計(jì)算出它的哈希值，MFC通常調(diào)用一個(gè)全局模板函數(shù)HashKeyO，對于大多數(shù)數(shù)據(jù)類型而言，HashKey()函數(shù)是以下面的方式實(shí)現(xiàn)的：AFX_INLINEUINTAFXAPIHashKey(ARG_KEYkey){//一般情況的默認(rèn)算法。return((UINT)(void*)(DWORD)key)>>4;}但對于字符串而言，其具體的實(shí)現(xiàn)方式如下：UINTAFXAPIHashKey(LPCWSTRkey)//Unicode編碼字符串{UINTnHash=0;while(*key)nHash=(nHash<<5)+nHash+*key++;returnnHash;}UINTAFXAPIHashKey(LPCSTRkey)//ANSI編碼字符串{UINTnHash=0;while(*key)nHash=(nHash<<5)+nHash+*key++;returnnHash;}要實(shí)現(xiàn)對應(yīng)于特定數(shù)據(jù)類型的用戶自定義哈希算法，您可以使用上述的字符串版本的HashKey()函數(shù)作為參考，寫一個(gè)類似的特定類型的HashKey()函數(shù)。四、使用MFC中的CMap類有關(guān)MFC中的CMap類的概況，上面的文字段落中已經(jīng)陸續(xù)提及，在此不再贅言。下面，列出CMap類的基本成員函數(shù)，并通過一個(gè)簡短的程序片段來粗略地演示CMap類的使用方法。構(gòu)造函數(shù)：CMap構(gòu)造個(gè)關(guān)鍵字和元素值映射的集合類。操作：Lookup通過給定的關(guān)鍵字杳找相應(yīng)的元素值。SetAt向Map中插入個(gè)兀素單兀；右存在匹配鍵字，則替代之。operator[]向Map中插入一個(gè)兀素-SetAt的子操作RemoveKey移除由關(guān)鍵字標(biāo)示的元素單元RemoveAll移除Map中的所有元素單元GetStartPosition返回第一個(gè)元素單元的位置GetNextAssoc讀取下一個(gè)元素單元GetHashTableSize返回哈希表的大小(元素單元的數(shù)目)InitHashTable初始化哈希表，并指定它的大小狀態(tài)：GetCount返回Map中兀素的數(shù)目IsEmpty檢查Map是否為空（無元素單元）應(yīng)用實(shí)例如下：CMapmyMap;//初始化哈希表，并指定其大小(取奇數(shù))MyMap.initHashTable(257);//向myMap中添加元素單元。for(inti=0;i<200;i++)myMap.SetAt(i,CPoint(i,i));//刪除實(shí)際值為偶數(shù)的關(guān)鍵字所對應(yīng)的的元素單元。POSITIONpos=myMap.GetStartPosition();intnKey;CPointpt;while(pos!=NULL){myMap.GetNextAssoc(pos,nKey,pt);if((nKey%2)==