有没有办法让这个哈希查找更快？

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 列重复向前重复 （还有其他重复项，但一个就足以防止单列哈希键）。

但是，通过使用第一列和第四列，我得到了值 Ju、Fr、Mc、Ai、 M、Je、Jy、Au、St、Oo、Ne 和 De，它们是唯一的。该文件中不会有无效值，因此我不必担心输入数据的存储桶不正确。

通过查看字符的十六进制代码，我发现只需与策略值进行 AND 运算即可获得较低的唯一值：

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

Answer 2

这是我能找到的 EBCDIC-US 的最小序列：

它在存储桶中有 24 个元素，仅使用 2 个操作来计算索引：

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

第二好，带有异或的 25 个项目：（

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

实际上，tab[]这里的长度应该是 32 个条目，因为 0x1f 可能会因输入错误而产生溢出）。

---

Pax 的更新：就其价值而言，第一个选项非常适合 EBCDIC 代码页 500：

## Month     str[1] str[2] Lookup
-- --------- ------ ------ ------
 0 January   a (81) n (95)      0
 1 February  e (85) b (82)      1
 2 March     a (81) r (99)      2
 3 April     p (97) r (99)      3
 4 May       a (81) y (a8)      4
 5 June      u (a4) n (95)      5
 6 July      u (a4) l (93)      6
 7 August    u (a4) g (87)      7
 8 September e (85) p (97)      8
 9 October   c (83) t (a3)      9
10 November  o (96) v (a5)     10
11 December  e (85) c (83)     11

Answer 3

这是针对 EBDIC (CCSID 500) 进行测试的，表 32 字节（比你的小，与 x4u 的大小相同）：

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

Answer 4

我将从您的较大流程的详细概况开始，以确保您不会进行过早的优化。

从表面上看，这看起来相当快，但如果内存真的很便宜，最好使用更稀疏的数组，让缓存完成一些工作。例如（在这里即兴思考），如果您只需将前两个字节中找到的 short 添加到接下来两个字节的 short 会怎样。这包括第一个和第四个字符，因此猜测它应该产生 12 个不同的值，并且它不涉及位字段提取，这可能无法很好地优化。然后，使匹配的 bucket[] 数组具有 64K 条目，其中只有 12 个条目被命中。
如果结果正确，这 12 个条目最终会占用一些 D 缓存，并且您已经用少量算术运算换取了缓存的更大数组的索引。

但是，请在尝试使算术更快的任何尝试之前和之后进行分析，并且不要在实际上不会节省时间的地方进行优化。 （我知道 Pax 知道这一点，但这是任何优化讨论中附加的强制性警告。）

Answer 5

好的，正如 SO 上的每个人一样，我全力以赴。;*) 正如我在上面的评论中所写，目标架构的低端具有 256 字节的缓存行大小，因此您最终可能会得到表查找中存在一些缓存垃圾（您的表超过 256 字节）。尝试使用一些廉价的小技巧来折叠桌子实际上可能会获得一些性能。

我一直在玩弄你的数据。您还可以选择第 2 列和第 3 列。不过，还没有找到一种方法来使其低于 8 位。

...和往常一样，进行配置文件，确保这是付出努力的最佳点，然后再次进行配置文件，确保速度更快。

...并且您一次阅读不止一行，对吧？固定记录大小很好，这样您就不必搜索分隔符（换行符），并且一次可以读取其中的一大块。

您可以使用以下方法减小数组大小：

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

将其从 16×26 更改为 16×13。

编辑

如果，正如其他帖子所建议的那样，您的字符串是对齐的，以便您可以将它们用作短整型，您可以添加第一个和第二个短整型，将两个字节异或在一起，您将得到一个唯一的 8 位密钥（实际上是 7 位）。也许也值得您花时间。不过这是 ASCII，因此可能不适用于 EBCDIC。在 ASCII 中，键是：

6e Jan
7f Feb
7b Mar
6a Apr
47 May
62 Jun
58 Jul
42 Aug
1a Sep
11 Oct
10 Nov
6d Dec

Answer 6

对我来说看起来足够好。问题是哈希函数本身是否足以成为瓶颈，以证明正在努力消除一两个简单的二进制运算是合理的。鉴于似乎涉及文件访问，我对此表示怀疑，当然，我不知道有关整个处理的任何细节。

编辑：

也许您可以看看是否发现任何一对字符在添加时产生唯一的低位（4、5 或 6）：

(str[1] + str[2]) & 0x1f

如果加法不起作用，可能是其他操作之一 & | ^。如果这没有帮助，也许使用三个字符。

Answer 7

在 ASCII 中，如果您采用 month[0] ^month[2] ^month[3] 那么您会得到一个最大值为 95（7 月）的唯一哈希值，这应该可以让您减少表大小相当大（最小值为 20（5 月），因此减法使其再次变小）。

在 EBCDIC 中可能情况并非如此，但可能会有类似的情况。

Answer 8

您真的需要哈希值和月份索引之间的映射来进行统计吗？如果您不返回月份而是返回散列并将其用于统计，则可以消除查找。在x4u的回答 哈希函数的最后一行可能看起来像这样

return ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f )

，您仍然可以进行求和，仅在最后对结果进行排序，而不是在循环内排序。