Accès getEntry caché (clé d'objet) dans HashMap

Question

J'ai un problème similaire à celui discuté here, mais avec une utilisation pratique plus forte.

Par exemple, j'ai un Map<String, Integer>, et j'ai une fonction, qui est donné une clé et dans le cas où la valeur entière cartographié est négatif, met NULL à la carte:

Map<String, Integer> map = new HashMap<String, Integer>(); 

public void nullifyIfNegative(String key) { 
    Integer value = map.get(key); 

    if (value != null && value.intValue() < 0) { 
     map.put(key, null); 
    } 
} 

I ce cas, la recherche (et donc, hashCode calcul pour la clé) est fait deux fois: un pour la recherche et un pour le remplacement. Il serait agréable d'avoir une autre méthode (qui est déjà en HashMap) et permet de rendre plus efficace:

public void nullifyIfNegative(String key) { 
    Map.Entry<String, Integer> entry = map.getEntry(key); 

    if (entry != null && entry.getValue().intValue() < 0) { 
     entry.setValue(null); 
    } 
} 

Les cas mêmes préoccupations, lorsque vous voulez manipuler des objets immuables, qui peuvent être des valeurs de carte:

• Map<String, String>: Je souhaite ajouter quelque chose à la valeur de chaîne.
• Map<String, int[]>: Je souhaite insérer un nombre dans le tableau.

Ainsi, le cas est assez commun. Solutions qui pourraient fonctionner, mais pas pour moi:

• Réflexion. Est bon, mais je ne peux pas sacrifier la performance juste pour cette belle fonctionnalité.
• Utilisez org.apache.commons.collections.map.AbstractHashedMap (il a au moins la méthode protected getEntry()), mais malheureusement, les collections-communes ne supportent pas les génériques.
• , mais cette bibliothèque (AFAIK) est obsolète (non synchronisée avec la dernière version de bibliothèque d'Apache) et (ce qui est critique) n'est pas disponible dans le référentiel central maven.
• Utilisez des wrappers de valeur, ce qui signifie "making values ​​mutable" (par exemple, utilisez des entiers mutables [par exemple org.apache.commons.lang.mutable.MutableInt] ou des collections au lieu de tableaux). Cette solution conduit à la perte de mémoire, que je voudrais éviter.
• Essayez d'étendre java.util.HashMap avec la mise en œuvre de classe personnalisée (qui devrait être dans le paquet java.util) et le mettre à endorsed folder (comme java.lang.ClassLoader refusera de le charger dans Class<?> defineClass(String name, byte[] b, int off, int len), voir les sources), mais je ne veux pas patcher JDK et ressemble à la liste des paquets qui peuvent être approuvés, n'inclut pas java.util.

La question similaire est déjà soulevée sur sun.com bugtracker, mais je voudrais savoir, quelle est l'opinion de la communauté et ce qui peut être la sortie prendre à l'esprit la mémoire maximale & l'efficacité du rendement.

Si vous êtes d'accord, c'est une fonctionnalité agréable et bénéficiaire, s'il vous plaît, votez ce bug!

Answer 1

Pas joli, mais vous pouvez utiliser un objet léger pour contenir une référence à la valeur réelle pour éviter les secondes recherches.

HashMap<String, String[]> map = ...; 

// append value to the current value of key 
String key = "key"; 
String value = "value"; 

// I use an array to hold a reference - even uglier than the whole idea itself ;) 
String[] ref = new String[1]; // lightweigt object 
String[] prev = map.put(key, ref); 
ref[0] = (prev != null) ? prev[0] + value : value; 

Je vous inquiétez pas sur les performances de recherche de hachage trop bien (Steve B's answer est assez bon en indiquant pourquoi). Surtout avec les clés String, je ne m'inquiéterais pas trop de hashCode() car son résultat est mis en cache. Vous pourriez vous inquiéter de equals() mais comme il pourrait être appelé plus d'une fois par recherche. Mais pour les chaînes courtes (qui sont souvent utilisées comme des touches), c'est négligeable aussi.

Answer 2

D'un point de vue logique, vous avez raison de dire que le simple getEntry vous permettrait d'économiser une recherche de hachage. En pratique, à moins que vous ayez un cas d'utilisation spécifique où vous avez des raisons de vous inquiéter de la baisse de performance (ce qui semble peu probable, la recherche de hachage est commune, O (1), et bien optimisée) probablement négligeable.

Pourquoi n'écrivez-vous pas un test?Créez une table de hachage avec quelques dizaines de millions d'objets, ou un ordre de grandeur supérieur à celui que votre application est susceptible de créer, et calculez la moyenne d'un get() sur un million d'itérations (indice: cela va être un très petit nombre).

Un problème plus important avec ce que vous faites est la synchronisation. Vous devez savoir que si vous effectuez des modifications conditionnelles sur une carte, vous risquez de rencontrer des problèmes, même si vous utilisez une carte Synchronisée, car vous devrez verrouiller l'accès à la clé couvrant la portée des deux get () et set() opérations.

Answer 3

Il n'y a pas de gain de performance de cette proposition, car la performance de Map dans le cas moyen est O (1). Mais permettre l'accès à l'entrée brute dans un tel cas posera un autre problème. Il sera possible de changer de clé à l'entrée (même si c'est seulement possible par réflexion) et donc de casser l'ordre du tableau interne.