c - 有没有办法使这个哈希查找更快？

Question

我需要(非常)快速地处理有限范围内的字符串，计算它们的值。输入文件的格式为:

January    7
March     22
September 87
March     36

等等。因为线宽相同，所以我可以简单地在一行中读取 fread相当快，我已经开发了一个完美的哈希函数，但我想看看是否有人可以就如何让它更快提供任何建议。我将对每条建议进行概要分析，以了解其进展情况。

散列函数基于月份名称以允许将值快速分配到桶中。在这里忍受我。我首先计算出完美哈希的最少字符数:

January
February
March
April
May
June
July
August
September
October
November
December

请记住月份是 所有 九个字符，因为我有整个输入行。

遗憾的是，没有单个 列来标记月份的唯一性。第 1 列重复 J , 第 2 列重复 a , 第 3 列重复 r , 第 4 列重复 u和第 5 列重复 <space> (还有其他重复但一个足以防止单列哈希键)。

但是，通过使用第一列和第四列，我得到了值 Ju , Fr , Mc , Ai , M<space> , Je , Jy , Au , St , Oo , Ne和 De , 这是独一无二的。此文件中不会有无效值，因此我不必担心输入数据的桶不正确。

通过查看字符的十六进制代码，我发现我可以通过与战略值进行 ANDing 来获得较低的唯一值:

FirstChar  Hex  Binary     &0x0f
---------  ---  ---------  -----
   A       x41  0100 0001      1
   D       x44  0100 0100      4
   F       x46  0100 0110      6
   J       x4a  0100 1010     10
   M       x4d  0100 1101     13
   N       x4e  0100 1110     14
   O       x4f  0100 1111     15
   S       x53  0101 0011      3

SecondChar  Hex  Binary     &0x1f
----------  ---  ---------  -----
 <space>    x20  0010 0000      0
    c       x63  0110 0011      3
    e       x65  0110 0101      5
    i       x69  0110 1001      9
    o       x6f  0110 1111     15
    r       x72  0111 0010     18
    t       x74  0111 0100     20
    u       x75  0111 0101     21
    y       x79  0111 1001     25

这让我可以设置一个静态数组来创建一个(希望)快得令人眼花缭乱的哈希函数:

#define __ -1
static unsigned int hash (const char *str) {
    static unsigned char bucket[] = {
        //   A       S   D       F               J           M   N   O
        __, __, __, __, __, __, __, __, __, __, __, __, __,  4, __, __, // space
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __,  2, __, __, // c
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, 11, __, __, __, __, __,  5, __, __, __, 10, __, // e
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __,  3, __, __, __, __, __, __, __, __, __, __, __, __, __, __, // i
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __,  9, // o
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __,  1, __, __, __, __, __, __, __, __, __, // r
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __,  8, __, __, __, __, __, __, __, __, __, __, __, __, // t
        __,  7, __, __, __, __, __, __, __, __,  0, __, __, __, __, __, // u
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __,  6, __, __, __, __, __  // y
    };
    return bucket[((unsigned int)(str[3]&0x1f)<<4)|(str[0]&0xf)];
}

用代码测试:

#include <stdio.h>
#include <string.h>

// Hash function here.

static char *months[] = {
    "January  ", "February ", "March    ", "April    ", "May      ", "June     ",
    "July     ", "August   ", "September", "October  ", "November ", "December "
};

int main (void) {
    int i;
    for (i = 0; i < sizeof(months)/sizeof(*months); i++)
        printf ("%-10s -> %2d\n", months[i], hash(months[i]));
    return 0;
}

表明它在功能上是正确的:

January    ->  0
February   ->  1
March      ->  2
April      ->  3
May        ->  4
June       ->  5
July       ->  6
August     ->  7
September  ->  8
October    ->  9
November   -> 10
December   -> 11

但我想知道它是否可以变得更快。

有什么建议吗？如果我的哈希函数存在固有的问题，我愿意接受任何简单的优化，甚至完全重写。

---

我认为这不是那么重要，但最终版本将使用 EBCDIC。该理论仍然成立，但由于字符具有不同的代码点，因此 AND 操作可能会略有变化。我很乐意仅在 ASCII 方面提供任何帮助，因为我相信所提供的任何建议都可以很好地转换为 EBCDIC。

Answer 1

我同意其他人的看法，即没有太大的改进空间。我所能建议的是一个较小的查找表，它可以处理相同数量的操作，这可能会使它在 CPU 缓存中停留更长时间。此外，它不依赖于末尾的空格填充字符，它适用于大写和小写字符的任何混合。我发现针对需求中可能发生的变化添加一些合理的稳健性通常会在未来得到返回，尤其是当实现优化到小变化不再那么容易的程度时。

#define __ -1
static unsigned int hash (const char *str)
{
    static unsigned char tab[] = {
        __, __,  1, 11, __, __, __, __,  7, __, __, __, __,  6,  0,  5,
         8, __,  2,  3,  9, __, 10, __, __,  4, __, __, __, __, __, __
    };
    return tab[ ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f ) ];
}

这与您最初的想法类似，但空白较少:

Month  s[1]          s[2]          s[1].4  s[2].4-0  sum  lookup
-----  ------------  ------------  ------  --------  ---  ------
Jan    61:0110 0001  6e:0110 1110       0        14   14       0
Feb    65:0110 0101  62:0110 0010       0         2    2       1
Mar    61:0110 0001  72:0111 0010       0        18   18       2
Apr    70:0111 0000  72:0111 0010       1        18   19       3
May    61:0110 0001  79:0111 1001       0        25   25       4
Jun    75:0111 0101  6e:0110 1110       1        14   15       5
Jul    75:0111 0101  6c:0110 1100       1        12   13       6
Aug    75:0111 0101  67:0110 0111       1         7    8       7
Sep    65:0110 0101  70:0111 0000       0        16   16       8
Oct    63:0110 0011  74:0111 0100       0        20   20       9
Nov    6f:0110 1111  76:0111 0110       0        22   22      10
Dec    65:0110 0101  63:0110 0111       0         3    3      11
             ^             ^ ^^^^
bits:        4             4 3210