CODEWITHSUNDEEP
javahashmap
jW.
jW.

Reputation: 9310

Performance of HashMap with different initial capacity and load factor

Here is my situation. I am using two java.util.HashMap to store some frequently used data in a Java web app running on Tomcat. I know the exact number of entries into each Hashmap. The keys will be strings, and ints respectively.

My question is, what is the best way to set the initial capacity and loadfactor?

Should I set the capacity equal to the number of elements it will have and the load capacity to 1.0? I would like the absolute best performance without using too much memory. I am afraid however, that the table would not fill optimally. With a table of the exact size needed, won't there be key collision, causing a (usually short) scan to find the correct element?

Assuming (and this is a stretch) that the hash function is a simple mod 5 of the integer keys, wouldn't that mean that keys 5, 10, 15 would hit the same bucket and then cause a seek to fill the buckets next to them? Would a larger initial capacity increase performance?

Also, if there is a better datastructure than a hashmap for this, I am completely open to that as well.

Upvotes: 22

Views: 20259

Answers (5)

Stephen C
Stephen C

Reputation: 719576

Assuming that your hash function is "good", the best thing to do is to set the initial size to the expected number of elements, assuming that you can get a good estimate cheaply. It is a good idea to do this because when a HashMap resizes it has to recalculate the hash values for every key in the table.

Leave the load factor at 0.75. The value of 0.75 has been chosen empirically as a good compromise between hash lookup performance and space usage for the primary hash array. As you push the load factor up, the average lookup time will increase significantly.

If you want to dig into the mathematics of hash table behaviour: Donald Knuth (1998). The Art of Computer Programming'. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 0-201-89685-0.

Upvotes: 5

Fortyrunner
Fortyrunner

Reputation: 12792

I find it best not to fiddle around with default settings unless I really really need to.

Hotspot does a great job of doing optimizations for you.

In any case; I would use a profiler (Say Netbeans Profiler) to measure the problem first.

We routinely store maps with 10000s of elements and if you have a good equals and hashcode implementation (and strings and Integers do!) this will be better than any load changes you may make.

Upvotes: 3

Cowan
Cowan

Reputation: 37553

Assuming (and this is a stretch) that the hash function is a simple mod 5 of the integer keys

It's not. From HashMap.java:

static int hash(int h) {
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

I'm not even going to pretend I understand that, but it looks like that's designed to handle just that situation.

Note also that the number of buckets is also always a power of 2, no matter what size you ask for.

Upvotes: 2

Avi
Avi

Reputation: 20152

In the absence of a perfect hashing function for your data, and assuming that this is really not a micro-optimization of something that really doesn't matter, I would try the following:

Assume the default load capacity (.75) used by HashMap is a good value in most situations. That being the case, you can use it, and set the initial capacity of your HashMap based on your own knowledge of how many items it will hold - set it so that initial-capacity x .75 = number of items (round up).

If it were a larger map, in a situation where high-speed lookup was really critical, I would suggest using some sort of trie rather than a hash map. For long strings, in large maps, you can save space, and some time, by using a more string-oriented data structure, such as a trie.

Upvotes: 13

Tom Hawtin - tackline
Tom Hawtin - tackline

Reputation: 147164

Entries are allocated to buckets in a random-like way. So even if you as many buckets as entries, some of the buckets will have collisions.

If you have more buckets, you'll have fewer collisions. However, more buckets means spreading out in memory and therefore slower. Generally a load factor in the range 0.7-0.8 is roughly optimal, so it is probably not worth changing.

As ever, it's probably worth profiling before you get hung up on microtuning these things.

Upvotes: 1

Related Questions