c - 将特殊用途字符串转换为整数的方法

Question

我需要一个内存中的键值对数据结构(400 MB 的数据)。我对键有以下限制:

1. 键和值都是长度为256和1024的文本字符串 分别。
2. 任何 key 通常看起来像 k1k2k3k4k5，每个 k(i) 本身都是 4-8 字节的字符串。某些 k(i) 可能存在也可能不存在。
3. 每个 k(i) 都有 6-8 种可能性。而 k3 和 k4 有 256000 种可能性。
4. 可以使用 prefix_key 迭代 DS。应针对此操作优化 DS。此操作分配一个迭代器，即它迭代整个 DS 并返回匹配 prefix_key 的键值列表(例如“k1k2k3.*”，如上定义的 k(i))。每次迭代都在此迭代器(列表)上迭代。释放迭代器会释放列表。

为字符串键提出 DS 会使键比较变得过于昂贵。因此排除了 DS 的某些选项(Hash、B+Tree)。

我的问题是我们如何创造性地将字符串键转换为整数键？解决方案需要具有以下属性:

对于键模式“k1k2k3.*”，它应该生成整数的上限和下限，以便基于这些界限在 DS 中仅查找少数条目。

我在 solution towards this 的背景下问这个问题

Answer 1

每个 k(i) 都有 6-8 种可能性。而 k3 和 k4 有 256000 种可能性。

如果你可以在 k1 k2 k3 k4 k5 中拆分 key ，你可以这样编码:

 3 bits for k1  
 3 bits for k2  
18 bits for k3  
18 bits for k4  
 3 bits for k5

这就是 45 位。 因此，您可以将 key 归结为 0 到 2^45-1 之间的整数。 这种接缝会很多，特别是如果您只使用 k3 和 k4 的几个可能值。

所以我会采用 k1 k2 的 6 位来精确映射到索引，而不是取决于 k3 k4 的密度，k3 和 k4 的某种树结构，而不是再次精确映射到 k5 的索引.