CODEWITHSUNDEEP
javadictionary
igr
igr

Reputation: 10604

Optimized java Map/Dictionary for small number of entries w/o removals

I have a specific usage of HashMap, where it just stores few entries (usually less then 5-10) for String keys. I just have to add entries, get them by key, and sometimes to iterate the entry set. Entries are never removed during the lifespan of the map. I have some operation where 5-6 such smaller maps are needed and allocated every time during single user usage, i.e. request.

I am using HashMap for this. However, I wonder if there is a better, optimized implementation of Map-alike structure that I might use for this? For example, one that would allocate less space and that might be faster for small number of elements. Or HashMap is simply good enough?

Note that I don't insist to follow Map interface for this.

My thoughts are going into direction of array-backed map, something like this implementation that caught my attention from JetBrains: SmartFMap (An immutable map optimized for storing few entries with relatively rare updates, as they say).

Does anyone know about such alternative implementations that would be a good HashMap replacement?

ADDON

My initial idea is what @Evgeniy Dorofeev said in his answer, to have sorted array of entries and use binary search, but with following modification. Since I need to add elements to this collection and to prevent re-creation of array I was thinking of using array with some empty spaces. First element is added eg in the middle of the array, second element is added in the middle of remaining half (below or under, depending on sorting order). If initial size of such array is good, we can (mostly) prevent recreation of this array and still be able to binary/radix search.

Upvotes: 4

Views: 1812

Answers (4)

Vladimir Nesterovsky
Vladimir Nesterovsky

Reputation: 649

You can use java.util.IdentityHashMap, provided you use identity keys. It's bit lighter than java.util.HashMap.

Upvotes: -1

Alexander Tokarev
Alexander Tokarev

Reputation: 2763

Consider using an ImmutableMap from Guava. Creation of Map using it is like a charm:

Map<String,String> map = ImmutableMap.of("key1", "value1", "key2", "value2");

There's another option for cases when you need to modify the entries of your map. You can use EnumMap from JDK. It's a little bit faster than HashMap.

Upvotes: 0

Maxime Ch&#233;ramy
Maxime Ch&#233;ramy

Reputation: 18821

Have you considered using a Trie?

This will provide almost the same complexity as your hashmap to get an item. But in some cases it will be faster. For example, with the following strings: hello, world, house, foo, bar, balloon. Getting the value associated to hello only requires to compare the 2 first characters, only one for world and 3 for bar and balloon. Using a hashmap you would compute a hash using all characters.

Upvotes: 3

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 135992

You can make a custom map based on array

    Object[][] map = new Object[3][];
    map[0] = new Object[] {k1, v1};
    map[1] = new Object[] {k2, v2};
    map[2] = new Object[] {k3, v3};
    Arrays.sort(map);

how to search

int i = Arrays.binarySearch(map, key);
Object value = map[i];

Upvotes: 1

Related Questions