有没有办法让这个哈希查找更快？
我要求（非常）快速处理有限范围的字符串，统计它们的值。 输入文件的格式如下：
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 ，它们是唯一的。 此文件中没有无效值，因此我不必担心输入数据的存储桶不正确。
通过查看字符的hex代码，我发现通过与策略值进行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 ---------- --- --------- ----- 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[] = { // ASDFJMNO __, __, __, __, __, __, __, __, __, __, __, __, __, 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 #include // 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 %2d\n", months[i], hash(months[i])); return 0; }
表明它在function上是正确的：
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。
这是我能为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 ])]; }
第二好，有xor的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
我同意其他人的意见，认为没有太大的改进空间。 我可以建议的是一个较小的查找表，它使用相同数量的操作，这可能使它在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
这是针对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]; }
我将首先详细介绍您的大型流程，以确保您不会过早优化。
从表面看起来非常快，但如果内存非常便宜，那么只使用一个更稀疏的数组并让你的缓存做一些工作可能会更好。 例如（并在这里考虑袖口），如果您只是将前两个字节中找到的short路线添加到接下来的两个short ，该怎么办？ 这包括第一个和第四个字符，因此猜测它应该产生12个不同的值，并且它不涉及可能无法很好地优化的位字段提取。 然后，使匹配的bucket[]数组具有64K条目，其中只有12个被命中。 如果它运行正确，那么这12个条目最终会占用你的一些D缓存，并且你已经将一些算术运算交换成一个缓存的更大数组的索引。
但是，在尝试更快地进行算术之前和之后都要进行分析，并且不要在优化实际上不会节省时间的地方进行优化。 （我知道Pax知道这一点，但它是任何优化讨论的强制性警告。）
好吧，就像SO上的每个人一样，我都在为它代表…; *）正如我在上面的评论中写的那样，目标体系结构的低端有一个256字节的缓存行大小，所以你可能最终得到一些缓存在您的表查找中丢弃（您的表超过256个字节）。 尝试使用一些廉价的位技巧来折叠表可能实际上获得了一些性能。
我一直在玩你的数据。 您还可以选择第2列和第3列。但是还没有找到一种方法来获得低于8位的方法。
……和往常一样，配置文件，确保它是应用努力的最佳点，然后再次进行配置，确保它更快。
……而且你一次只读一行，对吧？ 固定记录大小很好，你不必搜索分隔符（换行符），你可以一次读取它们的大部分。
您可以使用以下命令减小数组大小：
#define __ -1 static unsigned int hash (const char *str) { static unsigned char alloc_to[] = { // ASDFJMNO __, __, __, __, __, __, __, __, __, __, __, __, __, 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。
编辑
如果像其他post所建议的那样，你的字符串是对齐的，那么你可以将它们用作短路，你可以添加第一个和第二个短，x或两个字节在一起，你将拥有一个唯一的8位密钥（好吧，七，实际上）。 也值得你这么做。 这是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
对我来说看起来不错。 问题是哈希函数本身是否足以成为certificate正在进行的消除一个或两个更简单的二进制操作的努力的瓶颈。 鉴于文件访问似乎涉及，我当然怀疑它，当然不知道有关整体处理的任何细节。
编辑：
也许你可以看到，如果你发现任何一对字符在添加时会产生唯一的低位（4,5或6）：
(str[1] + str[2]) & 0x1f
如果添加不起作用，可能是其他操作之一& | ^ & | ^ 。 如果这没有帮助，可能使用三个字符。
在ASCII中，如果您使用month[0] ^ month[2] ^ month[3]那么您将获得一个最大值为95（7月）的唯一哈希值，这样可以让您减少表格大小（和最小值为20（May），因此减法使其再次变小）。
在EBCDIC中可能不是这样，但类似的东西可能是。
你真的需要哈希和月份索引之间的映射来进行统计吗？ 您可以消除查找，而不是返回您返回哈希值的月份，并使用它来计算。 在x4u的答案中，哈希函数的最后一行可能看起来像
return ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f )
你仍然可以做总和，只在结束时排序结果，而不是在循环内。