CMap的InitHashTable大小

Question

在我的程序，的CMap倍1.2 IIRC 6230這是優於我以前InitHashTable的尺寸（其是6203）的大小。

我把另一InitHashTable值是質數：9973

因此，這是正確的嗎？或者我應該選擇一個更接近6203的質數。或者，我可以選擇一個更大的質數？

Answer 1

這是CMap與VS2015的測試結果。它表明使用素數並沒有太大的區別，如果初始化比預期值高20％或更少，這並不重要。

有有或無質數或初始化沒有錯誤。我會假設在CMap的文檔中提到的「碰撞」與性能有關。

對於更大的數據集，你可以使用預期的數據大小。例如，如果預期的大小是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 

結果僅僅是一個粗略的估計

Answer 2

std::map使用紅黑樹和CMap爲哈希表實現。所以這些是兩個完全不同的容器。根據MSDN的最佳性能，哈希表大小應該是一個素數。爲了儘量減少衝突，規模應該比最大的預期數據集大約大20％。