小型定長密鑰的快速散列

Question

我試圖用大小爲1..8個字節的固定長度的密鑰合理地創建8個具有儘可能多的並行性（即CPU流水線）的手動編碼快速散列算法。我創建了8個散列函數，以便密鑰大小是編譯時間常量。我正在尋找常見的哈希算法，並試圖展開它們。同時，我想我會問問周圍，看看有沒有人有鏈接或知道一個辦法。

我們設置的散列字符集通常只有0..9 A..Z SPC偶爾有二進制的短或長。我知道1 char散列可能是無用的，所以我會這樣做，所以我們的代碼不會用這個小的散列鍵進行編譯。完美並不像速度那麼重要。這意味着，如果我們消除了產生散列的足夠CPU成本，那麼偶爾有2倍的項目是可以的。我已經廣泛地描述了我們的代碼多年了，所以我知道如果我採取下一步讓哈希算法變得更好/更快，它將爲我們公司節省多少資金。

我已經可以做得比我們的應用程序當前使用的散列函數更好，下面的UIHashOld（它可能會被改變），但是我認爲在一些幫助下我可以使它更好一點。例如，與UlHashOld相比，我的2個字符的散列函數將最大桶數減半，但它仍然有一些未填充的桶。如果希望在執行字母數字鍵時獲得兩個char散列以更好地分散它的位。我用下面的代碼測試此：

template <int cb> class CFixLenKeyBase { 
protected: 
    char m_ach[cb]; 
public: 
    CFixLenKeyBase(LPCSTR sz) { memcpy(m_ach, sz, cb); } 
    UL UlHashOld() { 
     UL n = 0; 
     for (LPCSTR sz = m_ach, szEnd = sz + cb; sz < szEnd; sz++) 
      n = n^(n >> 25)^(n << 7)^*sz; 
     return n; 
    } 
}; 

template <int cb> class CFixLenKey : public CFixLenKeyBase<cb> { 
public: 
    CFixLenKey(LPCSTR sz) : CFixLenKeyBase(sz) { } 
}; 

template <> class CFixLenKey<1> : public CFixLenKeyBase<1> { 
public: 
    CFixLenKey(LPCSTR sz) : CFixLenKeyBase(sz) { } 
    UL UlHash(void) const { return *m_ach; } 
}; 

template <> class CFixLenKey<2> : public CFixLenKeyBase<2> { 
public: 
    CFixLenKey(LPCSTR sz) : CFixLenKeyBase(sz) { } 
    UL UlHash(void) const { 
     auto a = *(WORD*)m_ach; 
     return b = (a >> 6)^a; 
    } 
}; 

template <> class CFixLenKey<3> : public CFixLenKeyBase<3> { 
public: 
    CFixLenKey(LPCSTR sz) : CFixLenKeyBase(sz) { } 
    UL UlHash(void) const { 
     UL a = (*(UL*)m_ach)&0xFFFFFF; 
     UL b = (a >> 14)^(a >> 6); 
     UL c = (a >> 11)^(a << 5); 
     UL d = (a >> 19)^(a << 9); 
     return d^c^b; 
    } 
}; 

char a[36*36*36*36][4] = {0}; 

int main(int argc, char* argv[]) 
{ 
    const int cBuckets = 256; 
    int aHisto[4][cBuckets] = { 0 }; 
    int aHistoOld[4][cBuckets] = { 0 }; 
    int aMax[4] = { 0 }; 
    int cElem = 36*36*36*36; 
    memcpy(a[0], "0000", 4); 
    for (int iElem=1 ; iElem<cElem ; ++iElem) { 
     auto& b = a[iElem]; 
     memcpy(b,a[iElem-1], 4); 
     int i = 3; 
     while (1) { 
      b[i]++; 
      if (b[i] == '9' + 1) { 
       b[i] = 'A'; 
      } else if (b[i] == 'Z' + 1) { 
       b[i] = '0'; 
       --i; 
      } else { 
       break; 
      } 
     } 
    } 
    int fMask = cBuckets - 1; 
    int ah[4] = {0}, ahOld[4] = {0}, aSame[4] = {0},aSameOld[4] = {0}; 
    for (int iElem=0 ; iElem<cElem ; ++iElem) { 
     int h, hOld, n, cb; 
     cb = 0; 
     CFixLenKey<1> A(a[iElem]); 
     if ((h = A.UlHash()) == ah[cb] && memcmp(a+iElem, a+iElem-1,cb)) 
      aSame[cb]++; 
     if ((hOld = A.UlHashOld()) == ahOld[cb] && memcmp(a+iElem, a+iElem-1,cb)) 
      aSameOld[cb]++; 
     ahOld[cb] = hOld; ah[cb]=h; 
     aHisto[cb][h&fMask]++; 
     aHistoOld[cb][hOld&fMask]++; 

     cb = 1; 
     CFixLenKey<2> B(a[iElem]); 
     if ((h = B.UlHash()) == ah[cb] && memcmp(a+iElem, a+iElem-1,cb)) 
      aSame[cb]++; 
     if ((hOld = B.UlHashOld()) == ahOld[cb] && memcmp(a+iElem, a+iElem-1,cb)) 
      aSameOld[cb]++; 
     ahOld[cb] = hOld; ah[cb]=h; 
     aHisto[cb][h&fMask]++; 
     aHistoOld[cb][hOld&fMask]++; 

     cb = 2; 
     CFixLenKey<3> C(a[iElem]); 
     if ((h = C.UlHash()) == ah[cb] && memcmp(a+iElem, a+iElem-1,cb)) 
      aSame[cb]++; 
     if ((hOld = C.UlHashOld()) == ahOld[cb] && memcmp(a+iElem, a+iElem-1,cb)) 
      aSameOld[cb]++; 
     ahOld[cb] = hOld; ah[cb]=h; 
     aHisto[cb][h&fMask]++; 
     aHistoOld[cb][hOld&fMask]++; 

    } 
    for (int cb=0 ; cb<4 ; ++cb) { 
     int nMin=aHisto[cb][0], nMax = nMin; 
     for (int i=0 ; i<fMask ; ++i) { 
      if (aHisto[cb][i] < nMin) 
       nMin = aHisto[cb][i]; 
      if (aHisto[cb][i] > nMax) 
       nMax = aHisto[cb][i]; 
     } 
     int nMinOld=aHistoOld[cb][0], nMaxOld = nMinOld; 
     for (int i=0 ; i<fMask ; ++i) { 
      if (aHistoOld[cb][i] < nMinOld) 
       nMinOld = aHistoOld[cb][i]; 
      if (aHistoOld[cb][i] > nMaxOld) 
       nMaxOld = aHistoOld[cb][i]; 
     } 

     printf("%d %03d %03d %03d %03d Same: %04d %04d\n", cb, nMin, nMax, nMinOld, nMaxOld, aSame[cb], aSameOld[cb]); 
     //for (int i=0 ; i<fMask ; ++i) { 
     // printf("%03d ", aHisto[cb][i]); 
     // if ((i&31) == 31) 
     //  printf("\n"); 
     //} 
     printf("\n"); 
    } 

    return 0; 
} 

Answer 1

我寫的散列here和here。

第一個答案涉及到通常遇到的散列問題時遇到的一般問題，它可能會給你一個良好的開端。

第二個涉及（除其他之外）對散列算法進行微調以適應當前的輸入。即使你並不確切地知道它會看起來像什麼樣子，你可以在你的實時/生產函數中實現統計數據收集（例如，在添加散列條目時重新排序的次數），並且有一個並行線程來測試索引大小的替代組合並重新散列常量，對所有輸入值進行虛擬散列並比較所產生的散列數。這樣，即使在算法投入生產後，也可以不斷地對算法進行微調。

我的散列有一個轉折，因爲存儲區域並不與主索引區域分開。不是「這是你應該實現散列的方式」，而是一種我認爲更優越的方法：邏輯和內部循環變得更加簡單，這就是哈希的全部內容。