4

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.

igr
  • 10,199
  • 13
  • 65
  • 111
  • 3
    why do you want micro-optimization when you don't have more than 10 items. unless you are dealing with millions of data records, what you are thinking is not worthy. it may not even help you get 1ns optimization – RaceBase Jan 19 '14 at 07:22
  • 1
    For me it's fun, challenging and I might learn something new. I like to question defaults. And if I find code that is 1ns faster and takes 1 bytes less memory, I will go with it - thats just me :) – igr Jan 19 '14 at 09:04

4 Answers4

3

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.

Maxime Chéramy
  • 17,761
  • 8
  • 54
  • 75
  • According to [this](http://bannister.us/weblog/2009/12/23/trie-in-java-revisited/), Trie can not outperform java collections. – igr Mar 16 '14 at 19:40
1

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];
Evgeniy Dorofeev
  • 133,369
  • 30
  • 199
  • 275
  • See my addon. That was my initial idea, except I don't know in the front how many items there will be, so I need to have `put` (insert) functionality. See my addon how to prevent array relocation. – igr Jan 19 '14 at 09:11
  • Also related to [this question](http://stackoverflow.com/questions/360040/which-is-faster-hash-lookup-or-binary-search). In other words, would this be faster then lookup? – igr Jan 19 '14 at 09:14
  • 1
    I don't think this solution would be faster, the only advantage is it would consume less memory. – Maxime Chéramy Jan 19 '14 at 09:15
0

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.

Alexander Tokarev
  • 2,743
  • 2
  • 20
  • 21
  • Thanx, however, I don't need immutable map, as I need to insert elements. EnumMap can't be the choice as well, as keys are not enums, just Strings. – igr Jan 19 '14 at 15:21
  • I checked, and Guava's ImmutableMap makes an usual linear for each lookup. So it might be good enough if you can make an immutable map. – Sergey Ponomarev Jan 03 '17 at 13:46
-1

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

Vladimir Nesterovsky
  • 619
  • 8
  • 14
  • Note that IdentityHashMap tries to make equals by reference, not by value of keys. So it's not applicable to strings, only of you try to make string interning which may slow down performance. – Sergey Ponomarev Jan 03 '17 at 13:40
  • Once you use literal strings as keys you can be sure they have the same identity. E.g. this plays very well if you have an IdentityHashMap as a private storage of a some big sparse bean, where getters and setters use literal constants as keys. – Vladimir Nesterovsky Jan 04 '17 at 06:53