CMap InitHashTable 大小

Question

在我的程序中，CMap 的大小是 1.2 IIRC 6230 的倍数，优于我使用的大小 InitHashTable（即 6203）。

我输入另一个 InitHashTable 值，它是一个质数：9973

所以这是正确的吗？或者我应该选择一个更接近 6203 的质数。或者我可以选择一个更大的质数吗？

Answer 1

std::map 使用 红黑树 并且 CMap 实现为 hash-table.所以这是两个完全不同的容器。根据 MSDN 的最佳性能，散列 table 大小应该是质数。为了尽量减少冲突，大小应比最大的预期数据集大大约 20%。

Answer 2

这是 CMap 使用 VS2015 的测试结果。它表明使用素数并没有太大的区别，并且初始化是否比预期值高或低 20% 也无关紧要。

有无质数或初始化都没有错误。我假设 CMap 文档中对 "collision" 的引用与性能有关。

对于较大的数据集，您可以使用预期的数据大小。例如，如果预期大小为 6,000，则只需使用 map.InitHashTable(6000)。默认值为 17，较低的值会降低性能。

还有std::map的测试结果，不需要初始化，速度非常快。

void test()
{
    CString msg;

    //build test vector
    int size = 100000;
    std::vector<CString> vs;
    for (int i = 0; i < size; i++)
    {
        CString s;
        s.Format(L"str%d", i);
        vs.push_back(s);
    }

    {//using prime number, 20% larger than expected size
        int t = GetTickCount();
        int init_size = 120011;

        CMap<LPCTSTR, LPCTSTR, int, int> map;
        map.InitHashTable(init_size);
        for (int i = 0; i < size; i++)
            map[vs[i]] = i;

        msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", init_size, GetTickCount() - t);
    }

    {//using non-prime number and 20% less than expected size
        int t = GetTickCount();
        int init_size = 80000;

        CMap<LPCTSTR, LPCTSTR, int, int> map;
        map.InitHashTable(init_size);
        for (int i = 0; i < size; i++)
            map[vs[i]] = i;

        msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", init_size, GetTickCount() - t);
    }

    {//using non-prime number and default initialization (m_nHashTableSize=17)
        int t = GetTickCount();
        CMap<LPCTSTR, LPCTSTR, int, int> map;
        for (int i = 0; i < size; i++)
            map[vs[i]] = i;
        msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", 17, GetTickCount() - t);
    }

    {//std::map test
        int t = GetTickCount();
        std::map<CString, int> mp;
        for (int i = 0; i < size; i++)
            mp[vs[i]] = i;
        msg.AppendFormat(L"std::map time:%d\n", GetTickCount() - t);
    }

    //error test:
    int init_size = 1000; //only a fraction of expected size!
    CMap<LPCTSTR, LPCTSTR, int, int> map;
    map.InitHashTable(init_size);
    for (int i = 0; i < size; i++)
        map[vs[i]] = i;
    for (int i = 0; i < size; i++)
    {
        if (map[vs[i]] != i)
        {
            AfxMessageBox(L"errorTest - fail");
            return;
        }
    }
    msg.AppendFormat(L"no error");

    AfxMessageBox(msg);
}

测试结果：（开启优化发布模式）

CMap Initialized: 120011, time:31
CMap Initialized: 80000, time:47
CMap Initialized: 17, time:5110
std::map time:78
no error

结果只是粗略估计

CMap InitHashTable 大小

CMap InitHashTable size

visual-c++

mfc

hashtable