Verificación de existencia clave en HashMap

309

¿Es siempre necesario verificar la existencia de claves en HashMap?

Tengo un HashMap con unas 1000 entradas y estoy buscando mejorar la eficiencia. Si se accede a HashMap con mucha frecuencia, la comprobación de la existencia de la clave en cada acceso generará una gran sobrecarga. En cambio, si la clave no está presente y, por lo tanto, se produce una excepción, puedo detectar la excepción. (cuando sé que esto sucederá raramente). Esto reducirá los accesos a HashMap a la mitad.

Puede que esta no sea una buena práctica de programación, pero me ayudará a reducir la cantidad de accesos. ¿O me estoy perdiendo algo aquí?

[ Actualización ] No tengo valores nulos en el HashMap.

Atenea
fuente
8
"por lo tanto, se produce una excepción", ¿qué excepción? Esto no será de java.util.HashMap ...
serg10

Respuestas:

513

¿Alguna vez almacenó un valor nulo? Si no, simplemente puedes hacer:

Foo value = map.get(key);
if (value != null) {
    ...
} else {
    // No such key
}

De lo contrario, podría verificar la existencia si obtiene un valor nulo devuelto:

Foo value = map.get(key);
if (value != null) {
    ...
} else {
    // Key might be present...
    if (map.containsKey(key)) {
       // Okay, there's a key but the value is null
    } else {
       // Definitely no such key
    }
}
Jon Skeet
fuente
1
@Samuel: solo cuando nulo es un valor posible. Si definitivamente no tiene valores nulos en el mapa, simplemente getestá bien y evita hacer dos búsquedas cuando también necesita el valor.
Jon Skeet
Aunque esto es probablemente más claro como ejemplo, también podría escribir if(value!=null || map.containsKey(key))para la segunda parte. Al menos si quieres hacer lo mismo de cualquier manera, sin código repetido. Funcionará debido a cortocircuitos .
Cullub
66

No ganará nada comprobando que la clave existe. Este es el código de HashMap:

@Override
public boolean containsKey(Object key) {
    Entry<K, V> m = getEntry(key);
    return m != null;
}

@Override
public V get(Object key) {
    Entry<K, V> m = getEntry(key);
    if (m != null) {
        return m.value;
    }
    return null;
}

Simplemente verifique si el valor de retorno get()es diferente de null.

Este es el código fuente de HashMap.


Recursos:

Colin Hebert
fuente
2
¿Cuál es el punto de mostrar una implementación específica de estos métodos?
jarnbjo
2
Para explicar eso en la mayoría de los casos, verificar que la clave exista tomará aproximadamente el mismo tiempo que obtener el valor. Por lo tanto, no optimizará nada para verificar que la clave realmente exista antes de obtener el valor. Sé que es una generalización, pero puede ayudar a entender.
Colin Hebert
Un buen enlace es grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… (OpenJDK se deriva muy fuertemente del código de Sun) y parece que estoy equivocado. Estaba comparando la versión para Java5 con Java6; funcionan de manera diferente en esta área (pero ambos son correctos, al igual que los fragmentos que publicó).
Donal Fellows
2
Como se señaló en la respuesta aceptada, este caracol está completamente equivocado. Por supuesto, USTED gana algo al verificar la existencia de claves de la comparación de valores: puede diferenciar las claves no existentes de las claves que existen pero están asignadas a nulo como valor.
Johannes H.
43

Mejor manera es utilizar el containsKeymétodo de HashMap. Mañana alguien agregará nulo al Mapa. Debe diferenciar entre la presencia de clave y la clave tiene un valor nulo.

Programador muerto
fuente
Si. O subclasifique el HashMap para evitar el almacenamiento nulltotal.
RobAu
1
1+ para los tipos primitivos como valor no se requiere
conversión
También es más fluido escribir .containsKey () que verificar nulo. Deberíamos preocuparnos más por ser fáciles de leer, lo que ahorra tiempo a los desarrolladores, que por alguna optimización menor, en la mayoría de los casos. Al menos no optimizar antes de que sea necesario.
Max
23

¿Quieres decir que tienes un código como

if(map.containsKey(key)) doSomethingWith(map.get(key))

por todo el lugar ? Entonces simplemente debe verificar si map.get(key)devuelve nulo y eso es todo. Por cierto, HashMap no arroja excepciones para las claves faltantes, sino que devuelve nulo. El único caso donde containsKeyse necesita es cuando se almacenan valores nulos, para distinguir entre un valor nulo y un valor faltante, pero esto generalmente se considera una mala práctica.

jkff
fuente
8

Solo úsalo containsKey()para mayor claridad. Es rápido y mantiene el código limpio y legible. El punto de HashMaps es que la búsqueda de claves es rápido, basta con que el hashCode()y equals()se aplica correctamente.

Mikko Wilkman
fuente
4
if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))
Erlan
fuente
3

También puede usar el computeIfAbsent()método en la HashMapclase.

En el siguiente ejemplo, mapalmacena una lista de transacciones (enteros) que se aplican a la clave (el nombre de la cuenta bancaria). Para agregar 2 transacciones de 100y 200para checking_accountusted puede escribir:

HashMap<String, ArrayList<Integer>> map = new HashMap<>();
map.computeIfAbsent("checking_account", key -> new ArrayList<>())
   .add(100)
   .add(200);

De esta manera, no tiene que verificar si la clave checking_accountexiste o no.

  • Si no existe, se creará y devolverá uno mediante la expresión lambda.
  • Si existe, el valor de la clave será devuelto por computeIfAbsent().

Muy elegante! 👍

nazmul idris
fuente
0

Usualmente uso el idioma

Object value = map.get(key);
if (value == null) {
    value = createValue(key);
    map.put(key, value);
}

Esto significa que solo toca el mapa dos veces si falta la clave

Jon Freedman
fuente
0
  1. Si la clase de clave es suya, asegúrese de que se implementen los métodos hashCode () y equals ().
  2. Básicamente, el acceso a HashMap debe ser O (1) pero con una implementación incorrecta del método hashCode se convierte en O (n), porque el valor con la misma clave hash se almacenará como una lista vinculada.
Boris
fuente
0

La respuesta de Jon Skeet aborda bien los dos escenarios (mapa con nullvalor y no nullvalor) de manera eficiente.

Sobre las entradas de números y la preocupación de eficiencia, me gustaría agregar algo.

Tengo un HashMap con, digamos, 1.000 entradas y estoy buscando mejorar la eficiencia. Si se accede a HashMap con mucha frecuencia, la comprobación de la existencia de la clave en cada acceso generará una gran sobrecarga.

Un mapa con 1.000 entradas no es un mapa enorme.
Además de un mapa con 5.000 o 10.000 entradas.
Mapestán diseñados para hacer una recuperación rápida con tales dimensiones.

Ahora, se supone que hashCode()las teclas del mapa proporcionan una buena distribución.

Si puede usar un Integertipo de clave, hágalo.
Su hashCode()método es muy eficiente ya que las colisiones no son posibles para intvalores únicos :

public final class Integer extends Number implements Comparable<Integer> {
    ...
    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }

    public static int hashCode(int value) {
        return value;
    }
    ...
}

Si para la clave, tiene que usar otro tipo incorporado como, Stringpor ejemplo, que se usa a menudo Map, puede tener algunas colisiones, pero de 1 mil a algunos miles de objetos en el Map, debe tener muy pocos como String.hashCode()método Proporciona una buena distribución.

Si usa un tipo personalizado, anule hashCode()y corrija equals()correctamente y, en general, asegúrese de que hashCode()proporciona una distribución justa.
Puede consultar el artículo 9 de lo Java Effectiverefiere.
Aquí hay una publicación que detalla el camino.

davidxxx
fuente