二、 Map的工作原理

　　使用Map的最大优势是它的快速查找的优秀性能，而取得最优性能的关键在于尽量使得在检索周期内所需进行的元素检查（比对）次数达到最少。顺序查找的性能是最差的，因为如果使用顺序查找算法在包含n个元素单元的Map中查找某个元素，可能（最坏情况下）需要进行n次独立的比较运算。

　　二元查找（折中查找）的性能表现要稍好一些，可是，一个不容忽视的问题是--二元查找要求待查序列为有序排列，这无疑会降低Map自身的操作灵活性。在我们的理解中，所谓的最佳算法应当是不论元素单元数目的多少，也不论元素是以什么顺序进行排列，查找过程都无需任何额外的比对操作，而能够仅仅通过简单的计算方法，就可以直接指向最终的相应元素的快速、高效算法。这听起来有些玄乎，但事实上，这种算法的确是有可能实现的（而且，我相信，Map可以做得到）。

　　在MFC的CMap及其相关的Map类中，只要对Map进行正确设置，Lookup函数通常能够一次到位的查找到任意元素，而很少需要进行两次或者三次以上的查找比对。

　　那么，这种高效的查找是如何实现的呢？

　　不失一般性，以MFC中的CMap模板类为例。在Map被创建之后（通常是恰恰在第一个元素被插入之前的瞬间），系统会为一个指向CAssoc结构体的指针数组的哈希表分配内存。MFC使用CAssoc结构体描述元素值和关键字的组合对。

　　CAssoc结构体描述如下：

　　 无论何时，只要有一个元素值-关键字单元被加入到Map中，就会随之创建一个新的CAssoc结构体，并根据单元中的关键字的实际值来计算出相应的哈希值。同时，拷贝一个指向CAssoc结构体的指针并将其插入到哈希表中索引值为i的位置中。其中，i的计算公式如下：

　　i=nHashValue%nHushTableSize

　　式中，nHashValue是由关键字Key的实际值计算出来的哈希值；nHashTableSize是哈希表中元素的数目（默认情况下，哈希表的大小为17）。

　　如果在哈希表中的索引值为i的位置已经容纳了一个CAssoc指针，那么MFC将建立一个单独的CAssoc结构体的链表（List）,链表中的第一个CAssoc结构体的地址被存储到哈希表中，而将第二个CAssoc结构体的地址存储到前一个CAssoc结构体的pNext域，以此类推。下图展示了哈希表的一种可能实现情况，在该哈希表中，共有10个元素，其中5个元素地址分别唯一的存储，另外5个分别存储在长度为2和3的两个链表中。

　　调用一个Map的Lookup()函数时，MFC根据输入的关键字的实际值计算相应的哈希值，然后使用前面提到的公式将哈希值转换为索引值，并从哈希表中的相应位置检索CAssoc指针。

　　理想情况下，该位置只包含一个CAssoc指针，而非CAssoc指针链表。如果事实情况真如同我们所期望的那样，单一地址对应单一CAssoc指针，那么，元素单元将能够被一次查找到位，并直接读出；如果从哈希表中检索到的是CAssoc链表的指针头地址，则MFC顺序比对链表元素CAssoc结构所包含的关键字，直至查找到正确结果。但是，正如我们先前所讨论的那样，只要正确设置Map，链表中的元素一般就不会超过三个，这就意味着，查找通常可以在三次元素比对操作之内完成。

 
　
说明：本教程来源互联网或网友上传或出版商，仅为学习研究或媒体推广，wanshiok.com不保证资料的完整性。

 2/2   首页 上一页 1 2