Formas de convertir cadenas de purpoes especiales a enteros

Necesito tener una estructura de datos en memoria del par clave-valor (400 MB de datos). Tengo las siguientes restricciones en las teclas:

  1. Tanto la clave como los valores son cadenas de texto de longitud 256 y 1024 respectivamente.
  2. Cualquier clave generalmente se parece a k1k2k3k4k5, cada k (i) es una cadena de 4-8 bytes en sí misma. Algunos k (i) pueden o no estar allí en las teclas.
  3. Cada k (i) tiene 6-8 posibilidades. Sin embargo, k3 y k4 tienen 256000 posibilidades.
  4. Uno podría iterar el DS con prefix_key. DS debe estar optimizado para esta operación. Esta operación asigna un iterador, es decir, itera todo el DS y devuelve una lista de valores-clave que coinciden con prefix_key (por ejemplo, “k1k2k3. *”, K (i) definido como anteriormente). Cada iteración se repite en este iterador (lista). Liberar el iterador libera la lista.

Crear DS para las claves de cadena hace que las comparaciones de claves sean demasiado caras. Y así, ciertas opciones para el DS (Hash, B + Tree) se descartan.

Mi pregunta es: ¿con qué creatividad podemos convertir las claves de cadena en claves enteras? La solución debe tener la siguiente propiedad:

Para un patrón de clave “k1k2k3. *”, Se debe generar un límite superior e inferior en los números enteros, de modo que, en función de estos límites, solo se busque un número reducido de entradas en el DS.

Estoy haciendo esta pregunta en el contexto de la solución hacia este

Cada k (i) tiene 6-8 posibilidades. Sin embargo, k3 y k4 tienen 256000 posibilidades.

Si puede dividir la clave en k1 k2 k3 k4 k5, puede codificarla así:

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

esto hace 45bits. Por lo tanto, puede reducir su clave a un número entero entre 0 y 2 ^ 45-1. Esto parece ser mucho, especialmente si solo usa algunos de los valores posibles para k3 y k4.

Así que tomaría los 6 bits de k1 k2 para una asignación exacta a un índice y luego, dependiendo de qué tan densa sea k3 k4, algún tipo de estructura de árbol para k3 y k4 y luego una asignación exacta a un índice para k5 nuevamente.