String indexed collection in Java

Question

Using Java, assuming v1.6.

I have a collection where the unique index is a string and the non-unique value is an int. I need to perform thousands of lookups against this collection as fast as possible.

I currently am using a HashMap<String, Integer> but I am worried that the boxing/unboxing of the Integer to int is making this slower.

I had thought of using an ArrayList<String> coupled with an int[].

i.e. Instead of:

int value = (int) HashMap<String, Integer>.get("key");

I could do

int value = int[ArrayList<String>.indexOf("key")];

Any thoughts? Is there a faster way to do this?

p.s. I will only build the collection once and maybe modify it once but each time I will know the size so I can use String[] instead of ArrayList but not sure there's a faster way to replicate indexOf...

Answer 1

Unboxing is fast - no allocations are required. Boxing is a potentially slower, as it needs to allocate a new object (unless it uses a pooled one).

Are you sure you've really got a problem though? Don't complicate your code until you've actually proved that this is a significant hit. I very much doubt that it is.

There are collection libraries available for primitive types, but I would stick to the normal HashMap from the JRE until you've profiled and checked that this is causing a problem. If it really only is thousands of lookups, I very much doubt it'll be a problem at all. Likewise if you're lookup-based rather than addition-based (i.e. you fetch more often than you add) then the boxing cost won't be particularly significant, just unboxing, which is cheap.

I would suggest using intValue() rather than the cast to convert the value to an int though - it makes it clearer (IMO) what's going on.

EDIT: To answer the question in the comment, HashMap.get(key) will be faster than ArrayList.indexOf(key) when the collection is large enough. If you've actually only got five items, the list may well be faster. I assume that's not really the case though.

If you really, really don't want the boxing/unboxing, try Trove (TObjectHashMap). There's also COLT to consider, but I couldn't find the right type in there.

Answer 2

Any performance gain that you get from not having to box/unbox is significanlty erased by the for loop that you need to go with the indexOf method.

Use the HashMap. Also you don't need the (int) cast, the compiler will take care of it for you.

The array thing would be ok with a small number of items in the array, but then so is the HashMap...

The only way you could make it fast to look up in an array (and this is not a real suggestion as it has too many issues) is if you use the hashCode of the String to work with as the index into the array - don't even think about doing that though! (I only mention it because you might find something via google that talks about it... if they don't explain why it is bad don't read any more about it!)