implementar - recorrer hashmap java foreach

¿Es una buena idea almacenar datos como claves en HashMap con valores vacíos/nulos?

Question

Originalmente había escrito una ArrayList y almacenaba valores únicos (nombres de usuario, es decir, Strings ) en ella. Más tarde necesité usar ArrayList para buscar si existía un usuario en ella. Eso es O(n) para la búsqueda.

Mi líder técnico quería que cambiara eso a un HashMap y almacenara los nombres de usuario como claves en la matriz y los valores como Strings vacías.

Entonces, en Java:

hashmap.put("johndoe","");

Puedo ver si este usuario existe más tarde ejecutando -

hashmap.containsKey("johndoe"); 

Esto es O(1) ¿verdad?

Mi líder dijo que esta era una manera más eficiente de hacer esto y tenía sentido para mí, pero parecía un poco desagradable poner valores nulos / vacíos como valores en el mapa hash y almacenar elementos como claves.

Mi pregunta es, ¿es este un buen enfoque? La eficiencia supera a ArrayList#contains o una búsqueda de matriz en general. Funciona. Mi preocupación es que no he visto a nadie más hacer esto después de una búsqueda. Puede que me esté perdiendo un problema obvio en alguna parte, pero no puedo verlo.

Answer 1

Como tiene un conjunto de valores únicos, un Set es la estructura de datos adecuada. Puede poner sus valores dentro de HashSet , una implementación de la interfaz Set .

Mi líder dijo que esta era una manera más eficiente de hacer esto y tenía sentido para mí, pero parecía un poco desagradable poner valores nulos / vacíos como valores en el mapa hash y almacenar elementos como claves.

El consejo del plomo es defectuoso. Map no es la abstracción correcta para esto, Set . Un Map es apropiado para pares clave-valor. Pero no tienes valores, solo claves.

Ejemplo de uso:

Set<String> users = new HashSet<>(Arrays.asList("Alice", "Bob"));
System.out.println(users.contains("Alice"));
// -> prints true
System.out.println(users.contains("Jack"));
// -> prints false

Usar un Map sería incómodo, porque ¿cuál debería ser el tipo de los valores? Esa pregunta no tiene sentido en su caso de uso, ya que solo tiene claves, no pares clave-valor. Con un Set , no necesita preguntar eso, el uso es perfectamente natural.

Esto es O (1) ¿verdad?

Sí, buscar en un HashMap o un HashSet es O (1) peor caso amortizado, mientras que buscar en una List o una matriz es O (n) el peor caso.

Algunos comentarios señalan que un HashSet se implementa en términos de HashMap . Eso está bien, en ese nivel de abstracción . En el nivel de abstracción de la tarea en cuestión, almacenar una colección de nombres de usuario únicos, usar un conjunto es una elección natural, más natural que un mapa.

Answer 2

Esto es básicamente cómo se implementa HashSet , así que supongo que se puede decir que es un buen enfoque. También podría usar HashSet lugar de su HashMap con valores vacíos.

Por ejemplo :

La implementación de add de HashSet es

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

donde map es el HashMap respaldo y PRESENT es un valor ficticio.

Mi preocupación es que no he visto a nadie más hacer esto después de una búsqueda. Puede que me esté perdiendo un problema obvio en alguna parte, pero no puedo verlo.

Como mencioné, los desarrolladores del JDK están utilizando este mismo enfoque.