VC++ MFC 编程--CMap的使用

标签：MFC key -- CString C++ HashKey CMap UINT 哈希

本文翻译自: CMap How-to - CodeProject

介绍

像我这样的程序员，在CMap之前学习了STL::map，总是认为CMap很难使用，并且总是尝试以STL::map的方式使用CMap。在本文中，我将解释CMap，以及如何将它用于您自己的自定义类。在本文的最后，我将展示一个如何正确使用CMap与CString*的例子(注意，我的意思是CString指针，而不是CString:>)

CMap 内部

首先要注意的是，CMap实际上是一个散列映射，而不是像STL::map那样的树映射(通常是红黑树)。下面显示的是CMap的内部结构。

CMap 的声明

很多人对CMap的声明CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>感到困惑，为什么不只是CMap<KEY, VALUE>呢?

实际上，CMap中的最终数据容器是CPair, CPair的内部是{KEY, VALUE}。因此，CMap将真正存储一个KEY，而不是ARG_KEY。然而，如果你检查MFC源代码，几乎所有在CMap内部传递的内部参数都是用ARG_KEY和ARG_VALUE调用的，因此，使用KEY&作为ARG_KEY似乎总是正确的，除非:

您正在使用int、char等基本类型，其中按值传递与按引用传递没有区别(可能更快)。
如果你使用CString作为KEY，你应该使用LPCTSTR作为ARG_KEY，而不是CString&，我们将在后面讨论更多。

那么我应该怎么做才能使我的CMap正确的工作?

正如我前面提到的，CMap是一个哈希映射，哈希映射将尝试从键中获取“哈希值(hash value)” —— 一个UINT，并使用该哈希值作为哈希表中的索引(实际上它是哈希值 % 哈希表大小)。如果多个键具有相同的哈希值，它们将被链接到一个链表中。因此，您要做的第一件事就是提供一个 hash 函数。

CMap将调用一个模板函数HashKey()来执行哈希。LPCSTR和LPCWSTR的默认实现和专用版本如下:

// C++
// inside <afxtemp.h>
template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
    // default identity hash - works for most primitive values
    return (DWORD)(((DWORD_PTR)key)>>4);
}

// inside <strcore.cpp>
// specialized implementation for LPCWSTR
#if _MSC_VER >= 1100
template<> UINT AFXAPI HashKey<LPCWSTR> (LPCWSTR key)
#else
UINT AFXAPI HashKey(LPCWSTR key)
#endif
{
    UINT nHash = 0;
    while (*key)
        nHash = (nHash<<5) + nHash + *key++;
    return nHash;
}

// specialized implementation for LPCSTR
#if _MSC_VER >= 1100
template<> UINT AFXAPI HashKey<LPCSTR> (LPCSTR key)
#else
UINT AFXAPI HashKey(LPCSTR key)
#endif
{
    UINT nHash = 0;
    while (*key)
        nHash = (nHash<<5) + nHash + *key++;
    return nHash;
}

正如你所看到的，默认行为是“假设”键是一个指针，并将其转换为DWORD，这就是为什么你会得到“错误C2440: '类型转换':不能从'ClassXXX'转换为'DWORD_PTR'”，如果你不为你的ClassX提供一个专门的HashKey()。

而且因为MFC只有专门的实现LPCSTR和LPCWSTR，而不是CStringA和CStringW，如果你想在CMap中使用CString，你必须声明CMap<CString, LPCTSTR....>。

好了，现在你知道CMap是如何计算哈希值的了，但是由于多个键可能有相同的哈希值，CMap需要遍历整个链表来找到一个键“content”完全相同的键，而不仅仅是相同的“哈希值”。当CMap进行匹配时，它将调用另一个模板化函数CompareElements()。

// inside <afxtemp.h>
// noted: when called from CMap,
//        TYPE=KEY, ARG_TYPE=ARG_TYPE
// and note pElement1 is TYPE*, not TYPE
template<class TYPE, class ARG_TYPE>
BOOL AFXAPI CompareElements(const TYPE* pElement1, 
                            const ARG_TYPE* pElement2)
{
    ASSERT(AfxIsValidAddress(pElement1, 
           sizeof(TYPE), FALSE));
    ASSERT(AfxIsValidAddress(pElement2, 
           sizeof(ARG_TYPE), FALSE));

    // for CMap<CString, LPCTSTR...>
    // we are comparing CString == LPCTSTR
    return *pElement1 == *pElement2;
}

因此，如果您想在自己的自定义ClassX中使用CMap，则必须为HashKey()和CompareElements()提供专门的实现。

示例: CMap with CString*

作为一个例子，下面是你需要做的，使CMap与CString*一起工作，当然，使用字符串内容作为键，而不是指针的地址。

template<> 
UINT AFXAPI HashKey<CString*> (CString* key)
{
    return (NULL == key) ? 0 : HashKey((LPCTSTR)(*key));
}

// I don't know why, but CompareElements can't work with CString*
// have to define this
typedef CString* LPCString;

template<>
BOOL AFXAPI CompareElements<LPCString, LPCString> 
     (const LPCString* pElement1, const LPCString* pElement2)
{
    if ( *pElement1 == *pElement2 ) {
        // true even if pE1==pE2==NULL
        return true;
    } else if ( NULL != *pElement1 && NULL != *pElement2 ) {
        // both are not NULL
        return **pElement1 == **pElement2;
    } else {
        // either one is NULL
        return false;
    }
}

主程序如下:

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
    CMap<CString*, CString*, int, int> map;
    CString name1 = "Microsoft";
    CString name2 = "Microsoft";
    map[&name1] = 100;
    int x = map[&name2];

    printf("%s = %d\n", (LPCTSTR)name1, x);*/
    return 0;
}

--------- console output ---------
Microsoft = 100

请注意，即使没有专门的HashKey()和CompareElements()，程序也可以编译无误，但是当然，输出将是0，可能不是您想要的。

我关于CMap的最后一点说明

CMap是一个散列映射，而STL::map是一个树状映射，比较两者在性能上没有任何意义(这就像比较苹果和橘子一样!)但是，如果要按排序顺序检索键，则必须使用STL::map。
HashKey()的设计对整体性能至关重要。您应该提供一个HashKey()，它具有低碰撞率(不同的键通常具有不同的哈希值)并且易于计算(不是字符串的MD5等)。这并不容易。
当使用CMap(以及STL::hash_map)时，总是要注意哈希表的大小。正如MSDN引用的那样，“哈希表的大小应该是素数。为了最大限度地减少碰撞，大小应该比最大的预期数据集大大约20%” 。默认情况下，CMap哈希表大小为17，对于大约10个键来说应该是可以的。您可以使用InitHashTable(UINT nashsize)更改哈希表的大小，并且只能在第一个元素添加到映射之前这样做。你可以在这里找到更多质数。(不要混淆CMap(UINT nBlockSize))，nBlockSize是获取多个CAssoc来加速新节点的创建。)

参考文献

标签：MFC,key,--,CString,C++,HashKey,CMap,UINT,哈希
From： https://www.cnblogs.com/it89/p/17742403.html