CODEWITHSUNDEEP
javadictionaryhashmap
Suzan Cioc
Suzan Cioc

Reputation: 30097

Is it possible/required to speed up HashMap operations on same entry?

Suppose I wish to check HashMap entry and then replace it:

if( check( hashMap.get(key) ) ) {
    hashMap.put(key, newValue);
}

this will cause search procedure inside HashMap to run two times: once while get and another one while put. This looks ineffective. Is it possible to modify value of already found entry of Map?

UPDATE

I know I can make a wrapper and I know I have problems to mutate entry. But the question is WHY? May be HashMap remembers last search to improve repeated one? Why there are no methods to do such operation?

Upvotes: 1

Views: 369

Answers (4)

Erik Nedwidek
Erik Nedwidek

Reputation: 6184

Too much information for a comment on your question. Check the documentation for Hashmap.

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

Constant time means that it always requires the same amount of time to do the get and put operations [O(1)]. The amount of time that is going to be required is going to be linear based on how many times you need to loop [O(n)].

Upvotes: 2

kutschkem
kutschkem

Reputation: 8163

Take a look at trove ( http://trove4j.sourceforge.net/ ), their maps do have several methods that might be what you want:

  • adjustOrPut
  • putIfAbsent

I don't know how this is implemented internally, but i would guess that since trove is made to be highly performant, there will be only one lookup.

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1500385

EDIT: I've just discovered that you can modify the entry, via Map.Entry.setValue (and the HashMap implementation is mutable). It's a pain to get the entry for a particular key though, and I can't remember ever seeing anyone do this. You can get a set of the entries, but you can't get the entry for a single key, as far as I can tell.

There's one evil way of doing it - declare your own subclass of HashMap within the java.util package, and create a public method which just delegates to the package-private existing method:

package java.util;

// Please don't actually do this...
public class BadMap<K, V> extends HashMap<K, V> {
    public Map.Entry<K, V> getEntryPublic(K key) {
        return getEntry(key);
    }
}

That's pretty nasty though.

You wouldn't normally modify the entry - but of course you can change data within the value, if that's a mutable type.

I very much doubt that this is actually a performance bottleneck though, unless you're doing this a heck of a lot. You should profile your application to prove to yourself that this is a real problem before you start trying to fine-tune something which is probably not an issue.

If it does turn out to be an issue, you could change (say) a Map<Integer, String> into a Map<Integer, AtomicReference<String>> and use the AtomicReference<T> as a simple mutable wrapper type.

Upvotes: 3

Peter Lawrey
Peter Lawrey

Reputation: 533492

You can change the entry if it is mutable. One example of where you might do this is

private final Map<String, List<String>> map = new LinkedHashMap<>();

public void put(String key, String value) {
    List<String> list = map.get(key);
    if (list == null)
        map.put(key, list = new ArrayList<>());
    list.add(value);
}

This allows you to update a value, but you can't find and replace a value in one operation.

Upvotes: 1

Related Questions