将特殊目的字符串转换为整数的方法

Question

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

1. 键和值分别是长度256和1024的文本字符串。
2. 任何键通常看起来都是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中拆分密钥，则可以这样对其进行编码：

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

这个可以产生45位。所以你可以把你的键压缩为0到2^45-1之间的整数.这个接缝很大，特别是如果您只对k3和k4使用几个可能的值。

所以我会用k1 k2的6位来精确映射到索引，而不是依赖于k3 k4有多密集，这是k3和k4的某种树结构，而不是k5的精确映射。