En Java, ¿qué precauciones se deben tomar al usar un conjunto como clave en un mapa?

Question

No estoy seguro de cuáles son las opiniones predominantes sobre el uso de objetos dinámicos como Conjuntos como teclas en Mapas.

Sé que las implementaciones típicas de mapas (por ejemplo, HashMap) usan un hashcode para decidir en qué segmento colocar la entrada y que si hashcode debe cambiar de alguna manera (tal vez porque el contenido del conjunto debe cambiar, entonces eso podría estropear el HashMap haciendo que el cubo se compute incorrectamente (en comparación con la forma en que el Set se insertó inicialmente en el HashMap).

Sin embargo, si me aseguro de que el contenido del Conjunto no cambie en absoluto, ¿esta opción es viable? Aun así, ¿este enfoque generalmente se considera propenso a errores debido a la naturaleza inherentemente volátil de los conjuntos (incluso si se toman precauciones para garantizar que no se modifiquen)?

Parece que Java permite designar argumentos de función como finales; esta es quizás una precaución menor que podría tomarse?

¿La gente hace incluso cosas como esta en la práctica comercial/de código abierto? (Ponga Lista, Conjunto, Mapa, o similar como claves en Mapas?)

Creo que debería describir algo de lo que estoy tratando de lograr con esto, para que la motivación se vuelva más clara y tal vez las implementaciones alternativas podría ser sugerido

Lo que estoy tratando de lograr es tener algo de este tipo:

class TaggedMap<T, V> { 
    Map<Set<T>, V> _map; 
    Map<T, Set<Set<T>>> _keys; 
} 

... en esencia, para ser capaz de "etiquetar" ciertos datos (V) con ciertas teclas (T) y escribir otras funciones auxiliares para acceder/modificar los datos y hacer otras cosas sofisticadas con él (es decir, devolver una lista de todas las entradas que cumplan algunos criterios de claves). La función de _keys es servir como una especie de índice, para facilitar la búsqueda de los valores sin tener que pasar por todas las entradas de _map.

En mi caso, tengo la intención de utilizar específicamente T = String, V = Integer. Alguien que hablé de esto había sugerido la sustitución de una cadena para el conjunto, es decir, algo así como:

class TaggedMap<V> { 
    Map<String, V> _map; 
    Map<T, Set<String>> _keys; 
} 

donde la clave en _MAP es del tipo "key1; clave2; key3" con teclas separadas por delimitador. Pero me preguntaba si podría lograr una versión más general de esto en lugar de tener que aplicar una cadena con delimitadores entre las claves.

Otra cosa que me preguntaba era si había alguna manera de hacer esto como una extensión de mapa. Estaba imaginando algo como:

class TaggedMap<Set<T>, V> implements Map<Set<T>, V> { 
    Map<Set<T>, V> _map; 
    Map<T, Set<Set<T>>> _keys; 
} 

Sin embargo, yo no era capaz de conseguir esto para compilar, probablemente debido a mi entender inferiores de los genéricos. Con esto como un objetivo, ¿alguien puede corregir la declaración anterior para que funcione de acuerdo con el espíritu de lo que he descrito o sugerir algunas ligeras modificaciones estructurales? En particular, me pregunto acerca de la cláusula "implementa Map, V>", si es posible declarar una implementación de interfaz tan compleja.

Answer 1

Tiene razón en que si se asegura que

1. Los Set contenidos no se modifican, y
2. El Set s en sí mismos no son modificados

que es perfectamente seguro para utilizarlos como llaves en un Map.

Es difícil garantizar que (1) no se infrinja accidentalmente. Una opción podría ser diseñar específicamente la clase almacenada dentro del Set para que todas las instancias de esa clase sean inmutables. Esto evitaría que alguien accidentalmente cambie una de las claves Set, por lo que (1) no sería posible. Por ejemplo, si utiliza un Set<String> como clave, no necesita preocuparse por el String s dentro del Set que cambia debido a una modificación externa.

Puede hacer que (2) sea bastante fácil utilizando el método Collections.unmodifiableSet, que devuelve una vista envuelta de Set que no se puede modificar. Esto se puede hacer con cualquier Set, lo que significa que probablemente sea una muy buena idea usar algo como esto para sus llaves.

Espero que esto ayude! Y si su nombre de usuario significa lo que creo que es, ¡buena suerte aprendiendo todos los idiomas! :-)

Answer 2

Como mencionas, los conjuntos pueden cambiar, e incluso si evitas que el conjunto cambie (es decir, los elementos que contiene), los elementos mismos pueden cambiar. Esos factores en el código hash.

¿Puede describir lo que está tratando de hacer en términos de nivel superior?

Answer 3

@ La respuesta de templatetypedef es básicamente correcta. Solo puede usar con seguridad un Set como clave en alguna estructura de datos si el estado del conjunto no puede cambiar mientras es una clave. Si el estado del conjunto cambia, las invariantes de la estructura de datos son violadas y las operaciones en él darán resultados incorrectos.

Las envolturas creadas usando Collections.unmodifiableSet pueden ayudar, pero hay un escondite oculto. Si el conjunto original todavía es directamente alcanzable, la aplicación podría modificarlo; p.ej.

public void addToMap(Set key, Object value); 
    someMap.put(Collections.unmodifiableSet(key), value); 
} 

// but ... 

Set someKey = ... 
addToMap(someKey, "Hi mum"); 
... 
someKey.add("something"); // Ooops ... 

Para garantizar que esto no puede suceder, es necesario hacer una copia profunda del conjunto antes de que lo envuelve. Eso podría ser costoso.

---

Otro problema con el uso de un Set como clave es que puede ser costoso. Hay dos enfoques generales para implementar asignaciones de clave/valor; usando el método hashcode o usando un método compareTo que implementa un pedido. Ambos son costosos para los conjuntos.