Tag Archives: collections

Map.containsKey/Set.contains

by Mikhail Vorontsov

Both java.util.Map.containsKey and java.util.Set.contains methods should not be often used in your code. Their functionality is covered by other Map/Set methods which you are likely to use after containsKey/contains call.

Sets

If you want to check if you have some key in your set, and, if it is not present, add it and do something else, you may write code like this:

1
2
3
4
5
if ( !set.contains( key ) )
{
    set.add( key );
    //some extra code here
}
if ( !set.contains( key ) )
{
    set.add( key );
    //some extra code here
}

Instead, it will be faster to use check from add method itself. It will return true if a given key was not present in the set before (you can treat true as “did something” and false as “did nothing”).

1
2
3
4
if ( set.add( key ) )
{
    //same extra code could be added here
}
if ( set.add( key ) )
{
    //same extra code could be added here
}

Continue reading

Bit sets

by Mikhail Vorontsov

From time to time you may need to map an integer key to one or a few flags (boolean values). Bit sets are the best data structure in such cases.

There is only one bit set implementation in the core Java: java.util.BitSet. Internally it is using a long[], each bit of which maps to one integer: bit 0 in the first long is mapped to key 0, bit 1 – to key 1 and so on. This means that if you want to map keys starting from some high number, like 100,000,000 to booleans, then an unchanged BitSet may not be a best choice, because it will allocate all bits for keys from 0 to highest bit you’ve ever set in your bit set. For a bit set with a single set bit at position 100,000,000 it means allocation of about 12.5M memory.

Problem of high base key can be avoided be adding and subtracting this base key on all bit set operations (but, of course, you’ll need to know this base key in advance). The same should be done if you need to map negative values to booleans: java.util.BitSet does not support negative keys.

The third problem to avoid is mapping of very large values, which are outside of int values range. Ordinary java.util.BitSet supports only int keys.

And the last, but not the least is partitioning problem – if you need to store a few values here and a few values there – you still need to allocate all the memory to store keys from 0 to a highest set bit.

Continue reading