CODEWITHSUNDEEP
javaperformancelistdictionary
Jun
Jun

Reputation: 301

A Java List as quick as like a Java Map?

I'd like to find a simplified Java Map, or List, where I do not care what the actual value at the values collection, but only care:

boolean containsKey(Object key): if the key exists
void remove(Object key): remove the entry of the key

On one hand, I'd like to save memory by using key set only (like a Java List), on the other hand, I'd to run above 2 methods in O(1) time. Order is also not in concern. So is this possible in Java? Thanks

Upvotes: 1

Views: 794

Answers (2)

Andrey Chaschev
Andrey Chaschev

Reputation: 16486

You could use LinkedHashSet for this. If you need a simple interface, you come up with a new one:

interface SimpleSet{
    boolean containsKey(Object key);
    boolean remove(Object key);
}

class MySimpleSet extends LinkedHashSet implements SimpleSet{
    //... necessary contructors ...

    @Override
    public boolean containsKey(Object key) {
        return contains(key);
    }
}

And declare it like this:

SimpleSet set = new MySimpleSet();

Update on memory consumption

LinkedHashSet takes ~40-50 bytes per stored element. So if it's too much, you could consider THashSet or TLinkedHashSet from Trove4j which is ~4-8 bytes per element judging by this article: Memory consumption of popular Java data types.

Upvotes: 1

Jeroen Vannevel
Jeroen Vannevel

Reputation: 44439

Use a HashSet. This will only have a single list of values, not a key-value pair like a Map has.

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

A quick search showed this:

enter image description here

Upvotes: 7

Related Questions