部分多键映射的数据结构？

我的数据由映射到值的键组成，如下所示：

---------------------
Key          | Value
---------------------
(0, 0, 0, 0) | a
(0, 0, 0, 1) | b
(0, 1, 0, 1) | c
(0, 1, 1, 0) | d
....

我正在寻找一种可以有效地对键执行搜索查询的数据结构，其中查询可以是完整或部分指定键。例如：

(0, 0, 0, 1) -> a
(0, *, *, *) -> [a, b, c, d]
(0, 1, *, *) -> [c, d]

The idea that I've right now is to implement this using a regular tree, similar to this: Leaves nodes represent the values and non-leaves nodes are parts of the key (i.e. w,x,y and z nodes are first, second, third and forth part of the key, respectively.). A simple BFS algorithm could be used to answer any query. But the problem is that this tree is growing exponentially with each new part of the key.

什么数据结构/算法更适合解决这个问题？请注意，关键部分可以是数字或字符串。

数组。对真的！您将没有空间开销，没有“指针追逐”开销，并且计算索引只需要一点位数学，而处理器在这方面确实相当擅长。

假设您获得部分密钥作为mask and bits哪里的mask通配符位为 0，其他位为 1，并且bits通配符为 0，非通配符为任意值。

收集具有与该模式匹配的键的所有项目的算法是：

int key = bits;
do {
    yield items[key];
    key = (key | mask) + 1 & ~mask | bits;
} while (key != bits);

That key = (key | mask) + 1 & ~mask | bits这部分看起来很有趣，这就是它的工作原理。

The |（按位或）使所有非通配符为 1。这可确保增量继续携带非通配符的位。添加之后，本应“固定”的位被破坏（如果进位通过它们，则为 0，否则为 1），因此必须将它们屏蔽掉（& ~mask），然后设置回正确的值（| bits）。运算符的优先级使得它基本上可以在没有括号的情况下编写。您也可以将其写为

key = (((key | mask) + 1) & (~mask)) | bits;

这适用于任何类型的模式。如果您只需要“最后 x 位是可变的”，您可以进行一些优化：

int wildcards = 0;
int invmask = ~mask;
do {
    yield items[wildcards++ | bits];
} while (wildcards & invmask);

That just runs from 0 to 2^{number-of-wildcards} and then puts in the fixed bits in the top.

非二进制密钥

In the simplest non-binary case, the parts of the key are still some integral number of bits, that is, they range from 0 to 2ⁿ-1. You can use exactly the same code in that case, but the interpretation of the mask is different: instead of having a single 0 bit for a wildcard or a single 1 bit for a non-wildcard, it would have some other number of bits (corresponding to the width in bits of a key-part).

对于非二的幂，需要更多的技巧。问题在于，为了满足关键部分小于某个值的约束，必须比正常情况更早地生成进位。

例如，如果所有关键部分都可以是 0、1 或 2（但不能是 3），则可以执行以下操作（未测试）：

int key = bits;
int increment = (0x55555555 & ~mask) + 1;
do {
    yield items[key];
    int temp = (key | mask) + increment & ~mask;
    int fix = (temp | (temp >> 1)) & 0x55555555;
    key = temp - fix | bits;
} while (key != bits);

额外的increment是 1 加上“最接近的 2 次方与关键部分最大值之差”的掩码，在本例中，每个关键部分都是 1，因此每个“槽”（槽）中都有一个 1是 2 位宽，这是在这种情况下它们可以达到的最窄宽度）。它仅在通配符位置具有那些“偏移量”。

偏移关键部分，使其最高允许值映射到“全一”，确保进位通过它们传播。然而，这意味着它们通常处于无效状态（除非它接收到进位并变为零）。那么烦人的部分就来了：必须撤消偏移only对于没有归零的关键部分。

所以有fix它计算不为零的关键部分的掩码。如果关键部分更宽，那就更烦人了，如果关键部分的尺寸不一样，那就更糟糕了。

然后最后一部分，key = temp - fix | bits，撤消偏移并将非通配符放回原位。该减法不会破坏任何内容，因为仅从至少为 1 的 2 位组中减去 1，因此进位永远不会留下关键部分。

当然，这种索引方式确实浪费了一些空间，与二次幂的情况不同，因为数组中存在您永远无法索引的“洞”。