Claves compuestas: una guía sobre cómo manejarlas

Las claves compuestas se producen cuando se requiere una combinación de datos para definir la "clave" para su búsqueda de mapa o caché. Un ejemplo de esto podría ser cuando necesita almacenar en caché valores basados en el nombre de un cliente y en la función de un usuario. En un caso como este, su caché debería poder almacenar valores únicos basados en cada uno de estos dos (o más) criterios.

Hay algunas formas diferentes de manejar las claves compuestas en el código.

Combine los criterios en una cadena

La primera respuesta a la que la mayoría recurre es combinar los criterios en una cadena para usarla como clave. Es simple y no requiere mucho esfuerzo:

 private String getMapKey(Long userId, String userLocale) { return userId + "." userLocale; }

Esta es una forma bastante básica de manejar el problema. El uso de una clave de cadena puede facilitar la depuración y las investigaciones, ya que la clave de caché está en un formato legible por humanos. Pero hay algunos problemas a tener en cuenta con este enfoque:

1. Requiere que se cree una nueva cadena en cada interacción con el mapa. Aunque esta asignación de cadenas es generalmente pequeña, si se accede al mapa con frecuencia, puede generar una gran cantidad de asignaciones que toman tiempo y deben recolectarse como basura. El tamaño de la asignación de cadenas también puede ser mayor dependiendo de qué tan grandes sean los componentes de su clave o cuántos tenga.

   
   

2. Debe asegurarse de que la clave compuesta que cree no pueda ser falsificada en otro valor de clave:

 public String getMapKey(Integer groupId, Integer accessType) { return groupId.toString() + accessType.toString(); }

En lo anterior, si tuviera groupId = 1 y accessType = 23, sería la misma clave de caché que groupId = 12 y accessType = 3. Al agregar un carácter separador entre las cadenas, puede evitar este tipo de superposición. Pero tenga cuidado con las partes opcionales de una clave:

 public String getMapKey(String userProvidedString, String extensionName) { return userProvidedString + (extensionName == null ? "" : ("." + extensionName)); }

En el ejemplo anterior, nombre de extensión es una parte opcional de la clave. Si el nombre de extensión es opcional, userProvidedString podría incluir un separador y un nombre de extensión válido y obtener acceso a datos de caché a los que no debería haber tenido acceso.

Cuando utilice cadenas, querrá pensar en cómo combina sus datos para evitar colisiones en las claves. Especialmente en torno a cualquier entrada generada por el usuario para la clave.

Usar mapas/cachés anidados

Otra opción es no combinar las claves en absoluto y, en su lugar, anidar sus estructuras de datos (Mapas de Mapas de Mapas):

 Map<Integer, Map<String, String>> groupAndLocaleMap = new HashMap<>(); groupAndLocaleMap.computeIfAbsent(userId, k -> new HashMap()).put(userLocale, mapValue);

Esto tiene la ventaja de no necesitar asignar memoria nueva al interactuar con los mapas, ya que los valores pasados para las claves ya están asignados. Y aunque necesitarás realizar varias búsquedas para llegar al valor final, los mapas serán más pequeños.

Pero la desventaja de este enfoque es que se vuelve más complicado cuanto más profundo es el anidamiento. Incluso con sólo dos niveles, la inicialización del mapa puede parecer confusa. Cuando comienzas a trabajar con 3 o más datos, esto puede hacer que tu código sea muy detallado. Además de eso, cada nivel requiere una verificación nula para evitar punteros nulos.

Es posible que algunas “partes clave” tampoco funcionen bien como clave de mapa. Las matrices o colecciones no tienen métodos iguales predeterminados que comparen su contenido. Por lo tanto, deberá implementarlos o utilizar otra alternativa.

El uso de mapas anidados también podría resultar menos eficiente en cuanto a espacio dependiendo de qué tan único sea cada nivel de sus claves.

Crear un objeto clave compuesto

La última opción es, en lugar de combinar los valores clave en una cadena, crear un objeto personalizado para la clave:

 private class MapKey { private final int userId; private final String userLocale; public MapKey(int userId, String userLocale) { this.userId = userId; this.userLocale = userLocale; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MapKey mapKey = (MapKey) o; return userId == mapKey.userId && Objects.equals(userLocale, mapKey.userLocale); } @Override public int hashCode() { return Objects.hash(userId, userLocale); } }

Si bien cada interacción aún requiere una nueva asignación de memoria para un nuevo objeto. La asignación de claves de objeto es significativamente menor que la necesaria para una cadena compuesta. La razón de esto es que no es necesario reasignar las partes que componen la clave como cadenas. En cambio, sólo la clave del objeto envolvente requiere nueva memoria.

Un objeto de clave compuesta también puede permitir personalizaciones en las implementaciones de igualdad de claves y código hash. Como ignorar las mayúsculas en una cadena o usar una matriz o colección como parte de una clave.

Sin embargo, la desventaja aquí es que, nuevamente, requiere mucho más código que una cadena compuesta. Y requiere asegurarse de tener contratos iguales y de código hash válidos en la clase clave de su mapa.

Entonces, ¿cuál debería elegir?

En términos generales, sugeriría utilizar una clave de cadena compuesta. Es simple y fácil de entender, requiere la menor cantidad de código y es más fácil de depurar más adelante. Si bien es probable que sea el de rendimiento más lento, escribir código simple y legible es generalmente más importante que los beneficios que obtendría al utilizar una de las otras dos opciones. Recordar:

“La optimización prematura es la raíz de todos los males” Donald Knuth

Si no tiene evidencia o una razón para creer que su búsqueda de mapa/caché será un cuello de botella en el rendimiento, opte por la legibilidad.

Pero si ESTÁ en un escenario donde el rendimiento de su mapa o caché es muy alto, entonces podría ser bueno cambiar a una de las otras dos opciones. Veamos cómo se comparan los 3 entre sí en cuanto a rendimiento, así como con el tamaño de asignación de memoria.

Para probar los 3 escenarios anteriores, escribí código que replicaría la misma implementación de los 3 escenarios para una clave compuesta. La clave en sí consta de un valor entero, un valor de cadena y un valor largo. Las tres implementaciones utilizaron los mismos datos de prueba en cada ejecución para crear las claves.

Todas las ejecuciones se ejecutaron con 1 millón de registros en el mapa (se utilizó el mapa hash de Java). Se realizaron 3 ejecuciones construyendo la clave con diferentes combinaciones de tamaños de clave:

• 100 entradas, 100 cadenas, 100 largas: 1 millón de claves únicas

• 1 int, 1 string, 1.000.000 longs: 1 millón de claves únicas

• 1.000.000 de entradas, 1 cadena, 1 larga: 1 millón de claves únicas

  
  

Primero, veamos cuánto espacio ocupa cada mapa en el montón. Esto es importante porque afecta la cantidad de memoria que se necesita para ejecutar su aplicación.

Hay una nota obvia e interesante que hacer aquí: en el último escenario (1.000.000 de entradas), el tamaño de los mapas anidados es significativamente mayor que los demás. Esto se debe a que, en este escenario, los mapas anidados crean 1 mapa de primer nivel con 1 millón de entradas. Luego, para el segundo y tercer nivel, crea 1 millón de mapas con una sola entrada.

Todos esos mapas anidados almacenan gastos generales adicionales y en su mayoría están vacíos. Este es obviamente un caso extremo, pero quería mostrarlo para dejar claro un punto. Cuando se utiliza la implementación de mapas de nido, la unicidad (y el orden de esa unicidad) es muy importante.

Si invierte el orden a 1, 1, 1 millón, en realidad obtendrá el requisito de almacenamiento más bajo.

En los otros dos escenarios, el mapeo anidado es el más eficiente, con el objeto de clave personalizada en segundo lugar y las claves de cadena en último lugar.

A continuación, veamos el tiempo que lleva crear cada uno de estos mapas desde cero:

Nuevamente, vemos que los mapas anidados tienen el peor desempeño en el escenario 1 millón-1–1 para la asignación de memoria, pero incluso así, superan a los demás en tiempo de CPU. En lo anterior, también podemos ver cómo la clave String tiene el peor rendimiento en todos los casos, mientras que el uso de un objeto de clave personalizado es ligeramente más lento y requiere más asignación de memoria que las claves anidadas.

Por último, veamos el escenario de mayor rendimiento y qué tan efectivo es la lectura. Ejecutamos 1 millón de operaciones de lectura (1 por cada clave creada); No incluimos ninguna clave inexistente.

Aquí es donde realmente vemos cuán lenta es la búsqueda de claves basada en cadenas. Es, con diferencia, la más lenta y asigna la mayor cantidad de memoria de cualquiera de las 3 opciones. El objeto clave personalizado funciona "cerca" de la implementación de mapas anidados, pero sigue siendo consistentemente más lento por un pequeño margen.

Sin embargo, en las asignaciones de memoria de búsqueda, observe qué tan bien brillan los mapas anidados. No, eso no es un problema técnico en el gráfico; Buscar un valor en los mapas anidados no requiere asignaciones de memoria adicionales para realizar la búsqueda. ¿Cómo es eso posible?

Bueno, al combinar los objetos compuestos en una clave de cadena, es necesario asignar memoria para un nuevo objeto de cadena cada vez:

 private String lookup(int key1, String key2, long key3) { return map.get(key1 + "." + key2 + "." + key3); }

Cuando se utiliza una clave compuesta, aún es necesario asignar memoria para un nuevo objeto clave. Pero debido a que los miembros de ese objeto ya están creados y referenciados, todavía asigna mucho menos que una nueva cadena:

 private String lookup(int key1, String key2, long key3) { return map.get(new MapKey(key1, key2, key3)); }

Pero la implementación de mapas anidados no requiere una nueva asignación de memoria en la búsqueda. Estás reutilizando las partes proporcionadas como claves para cada uno de los mapas anidados:

 private String lookup(int key1, String key2, long key3) { return map.get(key1).get(key2).get(key3); }

Entonces, según lo anterior, ¿cuál es el de mayor rendimiento?

Es fácil ver que los mapas anidados salen ganando en casi todos los escenarios. Si busca un rendimiento bruto en la mayoría de los casos de uso, probablemente sea la mejor opción. Sin embargo, debes realizar tus propias pruebas para confirmar tus casos de uso.

El objeto clave constituye una muy buena opción de uso general cuando los mapas anidados se vuelven poco prácticos o imposibles de usar para su implementación. Y la clave de cadena compuesta, aunque más fácil de implementar, casi siempre será la más lenta.

El último punto a considerar cuando se busca implementar claves compuestas es que puede combinar lo anterior. Por ejemplo, podría usar mapas anidados para el primer nivel o dos y luego usar un objeto clave compuesto para simplificar los niveles más profundos.

Esto aún podría mantener sus datos particionados para búsquedas rápidas y al mismo tiempo optimizar el almacenamiento y el rendimiento de las búsquedas. Y mantenga su código legible también.

TLDR;

La mayoría de las veces, hazlo simple. Combine sus claves compuestas en una clave de cadena para almacenarlas en un mapa o caché si esa es la opción más sencilla y el rendimiento no es una preocupación importante.

En escenarios donde el rendimiento es crítico, asegúrese de realizar sus propias pruebas. Pero el uso de mapas anidados será lo más eficaz en la mayoría de los casos. También es probable que tenga los requisitos de almacenamiento más pequeños. Y las claves compuestas siguen siendo una alternativa eficaz cuando las asignaciones de anidamiento se vuelven poco prácticas.

También publicado aquí