c++ - 小型固定长度 key 的快速散列

Question

我正在尝试创建 8 个手动编码的快速哈希算法，这些算法具有尽可能多的并行性(即 CPU 流水线)，对于大小为 1..8 字节的固定长度 key 是合理的。我正在创建 8 个哈希函数，以便 key 大小是一个编译时间常数。我正在研究常见的哈希算法，并试图展开它们。与此同时，我想我应该四处打听一下，看看是否有人有链接或知道这样做的方法。

我们被散列的字符集通常只有 0..9 A..Z SPC，偶尔有二进制短或长。我知道 1 个字符的散列可能没有用，所以我会这样做，这样我们的代码就不会用这么小的散列键进行编译。完美不如速度重要。这意味着，如果我们消除了足够多的 CPU 成本来生成哈希，偶尔出现 2 倍项目的桶是可以的。多年来，我已经广泛分析了我们的代码，所以我知道如果我采取下一步措施使散列算法更好/更快，这将为我们公司节省多少钱。

我已经可以比我们的应用程序当前使用的哈希函数做得更好，下面是 UlHashOld(也可能会更改)，但我认为在 SO 的一些帮助下我可以做得更好。例如，与 UlHashOld 相比，我的 2 个字符的哈希函数将最大桶数减少了一半，但它仍然有许多未填充的桶。如果想让两个字符散列在执行字母数字键时更好地分散其位。我已经使用以下代码对此进行了测试:

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 .

第一个答案解决了在尝试散列时通常会遇到的一般性问题，它可能会给您一个良好的开端。

第二个处理(除其他事项外)将哈希算法微调到手头的输入。即使您不确切知道它会是什么样子，您也可以在您的实时/生产功能中实现统计信息收集(例如，添加哈希条目时的重新哈希次数)并有一个并行线程来测试索引大小的替代组合和重新散列常量，对所有输入值进行虚拟散列并比较重新散列的结果数。这样，即使在将算法投入生产后，也可以不断对其进行微调。

我的散列有一个扭曲，因为桶区域与主索引区域没有分开。不是“这是你应该实现散列的方式”，而是一种我认为更好的方法:逻辑和内部循环变得更加简单，即更快，这就是散列的全部意义所在。