如何使用gperf为一系列值创建散列？

Question

我有一系列像这样的十六进制数字

0xabcd****
0xabdc**89
0x****abcd
0xde****ab
# 50 or so more entries like these
# where * is any hex number

我需要一个哈希函数，它将接受一个4字节的值，并为成员关系生成Y/N答案。

我试过使用gperf，但不幸的是，它并没有将*解释为通配符。以前有人遇到过这个问题吗？我的代码是C。

Answer 1

如果我可以相信我的算法，每个****都有16^4个可能的值，因此四个外卡规范枚举3 * 16^4 + 16^2值--大约20万左右--有点超出了gperf的范围(它的文档说一个“大”密钥集是15,000)。

通配符对我来说意味着正则表达式，为什么不试试呢？下面是一个尝试，它将“4字节值”定义为uint32_t，并向regex(3)机器提供这样一个值的文本编码。这可能不是你要找的东西，但由于它是有趣的鹅卵石，给你。

#include <sys/types.h>
#include <regex.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

static regex_t the_re;

int
matcher_init(void)
{
    static const char the_re_string[] = "(abcd....|abdc..89|....abcd|de....ab|"
                                         /* OP's 4, plus 46 more... */
                                         "..d80a..|..7bc5..|c6..514a|..b7585a|"
                                         "4732ecc4|7c22e4da|5a5e..63|....e866|"
                                         "..fdc367|ac....b4|70249edc|..e97e32|"
                                         "....94d8|....fa6c|4591..ff|..e4..67|"
                                         "aab285..|....f81b|15bb22ba|3cf4....|"
                                         "57d3ad86|..bd..1e|..ec67b7|..693aaf|"
                                         "323c..18|cab237cb|d4b2c6b4|2a15..2f|"
                                         "....d196|..5e..10|....b1f1|b54e9838|"
                                         "..0cf1..|5c1a..fb|....f34d|19..d34c|"
                                         "..cacb48|..4c2d09|48..bc..|f98cc7..|"
                                         "ac..2b1a|..beb5..|98..03..|..61c35e|"
                                         "....1245|61..5ca8)";
    int res;

    if ((res = regcomp(&the_re, the_re_string, REG_EXTENDED|REG_NOSUB)) != 0) {
        char ebuf[256];

        (void) regerror(res, &the_re, ebuf, sizeof ebuf);
        (void) fprintf(stderr, "regcomp failed: %s\n", ebuf);

        return -1;
    }

    return 0;
}

int
matcher_matches(uint32_t u)
{
    char ubuf[9];

    (void) sprintf(ubuf, "%08x", u);

    return regexec(&the_re, ubuf, 0, 0, 0) == 0;
}

int
main(void)
{
    int i;
    unsigned tf, iterations, matches;
    time_t start;

    uint32_t tvals[] = {
                0xabcd0000, 0xabdc0089, 0x0000abcd, 0xde0000ab,
                0x00d80a00, 0x007bc500, 0xc600514a, 0x00b7585a,
                0x4732ecc4, 0x7c22e4da, 0x5a5e0063, 0x0000e866,
                0x00fdc367, 0xac0000b4, 0x70249edc, 0x00e97e32,
                0x000094d8, 0x0000fa6c, 0x459100ff, 0x00e40067,
                0xaab28500, 0x0000f81b, 0x15bb22ba, 0x3cf40000,
                0x57d3ad86, 0x00bd001e, 0x00ec67b7, 0x00693aaf,
                0x323c0018, 0xcab237cb, 0xd4b2c6b4, 0x2a15002f,
                0x0000d196, 0x005e0010, 0x0000b1f1, 0xb54e9838,
                0x000cf100, 0x5c1a00fb, 0x0000f34d, 0x1900d34c,
                0x00cacb48, 0x004c2d09, 0x4800bc00, 0xf98cc700,
                0xac002b1a, 0x00beb500, 0x98000300, 0x0061c35e,
                0x00001245, 0x61005ca8 };

    if (matcher_init() == -1) {
        return 1;
    }

    /* test known values */

    tf = 0;

    for (i = 0; i < sizeof(tvals) / sizeof(tvals[0]); i++) {
        if (!matcher_matches(tvals[i])) {
            (void) printf("0x%08x should match; didn't...\n", tvals[i]);
            tf = 1;
        }
    }

    if (tf) {
        return 1;
    }

    /* some random probes */

    srand((time(0) << 16) | (getpid() & 0xFFFF));

    iterations = matches = 0;

    (void) time(&start);

    for (i = 0; i < 1000000; i++) {
        uint32_t u = (uint32_t) ((rand() << 16) | (rand() & 0xFFFF));

        /* printf("Test: 0x%08x\n", u); */

        if (matcher_matches(u)) {
            (void) printf("Match: %08x\n", u);
            (void) fflush(stdout);
            matches++;
        }

        iterations++;
    }

    printf("iterations: %d; matches: %d (%u seconds)\n",
                        iterations, matches,
                        (unsigned) (time(0) - start));

    return 0;
}

对此的答复使我想起了问题本身，经过思考，我想到了一种更直截了当的方式。为什么更好的答案不会先出现，我永远也不会知道。

无论如何，不要使用正则表达式，只使用一个值和一个掩码。上面的代码丢失了它的matcher_init调用(以及与regex相关的所有内容)，matcher_matches调用支持可能如下所示。查找值与我为第一个答案生成的额外的46相匹配，因此第一个答案的main中相同的测试代码将继续工作。

我想，您可以对struct数组进行排序，以便在掩码中设置的位数较少的条目首先出现，并获得较小的性能增益，但即使是这样，第二次尝试也比基于正则表达式的条目快5倍。

static struct {
    uint32_t val, mask;
} vm [] = {
    { 0xabcd0000, 0xffff0000 },
    { 0xabdc0089, 0xffff00ff },
    { 0x0000abcd, 0x0000ffff },
    { 0xde0000ab, 0xff0000ff },
    { 0x00d80a00, 0x00ffff00 },
    { 0x007bc500, 0x00ffff00 },
    { 0xc600514a, 0xff00ffff },
    { 0x00b7585a, 0x00ffffff },
    { 0x4732ecc4, 0xffffffff },
    { 0x7c22e4da, 0xffffffff },
    { 0x5a5e0063, 0xffff00ff },
    { 0x0000e866, 0x0000ffff },
    { 0x00fdc367, 0x00ffffff },
    { 0xac0000b4, 0xff0000ff },
    { 0x70249edc, 0xffffffff },
    { 0x00e97e32, 0x00ffffff },
    { 0x000094d8, 0x0000ffff },
    { 0x0000fa6c, 0x0000ffff },
    { 0x459100ff, 0xffff00ff },
    { 0x00e40067, 0x00ff00ff },
    { 0xaab28500, 0xffffff00 },
    { 0x0000f81b, 0x0000ffff },
    { 0x15bb22ba, 0xffffffff },
    { 0x3cf40000, 0xffff0000 },
    { 0x57d3ad86, 0xffffffff },
    { 0x00bd001e, 0x00ff00ff },
    { 0x00ec67b7, 0x00ffffff },
    { 0x00693aaf, 0x00ffffff },
    { 0x323c0018, 0xffff00ff },
    { 0xcab237cb, 0xffffffff },
    { 0xd4b2c6b4, 0xffffffff },
    { 0x2a15002f, 0xffff00ff },
    { 0x0000d196, 0x0000ffff },
    { 0x005e0010, 0x00ff00ff },
    { 0x0000b1f1, 0x0000ffff },
    { 0xb54e9838, 0xffffffff },
    { 0x000cf100, 0x00ffff00 },
    { 0x5c1a00fb, 0xffff00ff },
    { 0x0000f34d, 0x0000ffff },
    { 0x1900d34c, 0xff00ffff },
    { 0x00cacb48, 0x00ffffff },
    { 0x004c2d09, 0x00ffffff },
    { 0x4800bc00, 0xff00ff00 },
    { 0xf98cc700, 0xffffff00 },
    { 0xac002b1a, 0xff00ffff },
    { 0x00beb500, 0x00ffff00 },
    { 0x98000300, 0xff00ff00 },
    { 0x0061c35e, 0x00ffffff },
    { 0x00001245, 0x0000ffff },
    { 0x61005ca8, 0xff00ffff }
};

int
matcher_matches(uint32_t u)
{
    size_t i;

    for (i = 0; i < sizeof(vm) / sizeof(vm[0]); i++) {
        if ((u & vm[i].mask) == vm[i].val) {
            return 1;
        }
    }
    return 0;
}

通配符现在是结构的mask字段中的零，相应的位“不关心”值(设置为零)在val字段中。

Answer 2

由于您不愿意枚举gperf的值(而且看起来gperf无论如何也不能处理这么多输入)，所以您不能在任务中使用gperf，所以您的问题的答案是您不能使用gperf来创建您的哈希。

我的建议是忘记完美散列(除了使用gperf之外，您没有描述完美散列的任何要求)。这些值本身是很好的分布，可以作为散列值使用。