Alex Rivera | Logout

What is the optimal capacity and load factor for a fixed-size HashMap?

Asked 2011-08-18T23:40:47.487
105

I'm trying to figure out the optimal capacity and load factor for a specific case. I think I got the gist of it, but I'd still be thankful for a confirmation from someone more knowledgable than me. :)

If I know that my HashMap will fill up to contain, say, 100 objects, and will spend most of the time having 100 objects, I'm guessing that the optimal values are initial capacity 100 and load factor 1? Or do I need capacity 101, or are there any other gotchas?

EDIT: OK, I set aside a few hours and did some testing. Here are the results:

  • Curiously, capacity, capacity+1, capacity+2, capacity-1 and even capacity-10 all yield exactly the same results. I would expect at least capacity-1 and capacity-10 to give worse results.
  • Using initial capacity (as opposed to using default value of 16) gives noticable put() improvement - up to 30% faster.
  • Using load factor of 1 gives equal performance for small number of objects, and better performance for larger number of objects (>100000). However, this does not improve proportionally to the number of objects; I suspect there is additional factor that affects the results.
  • get() performance is a bit different for different number of objects/capacity, but though it might slightly vary from case to case, generally it's not affected by initial capacity or load factor.

EDIT2: Adding some charts on my part as well. Here's the one illustrating difference between load factor 0.75 and 1, in cases where I initialize HashMap and fill it up to full capacity. On y scale is time in ms (lower is better), and x scale is size (number of objects). Since size changes linearly, the time required grows linearly as well.

So, let's see what I got. The following two charts show the difference in load factors. First chart shows what happens when HashMap is filled to capacity; load factor 0.75 performs worse because of resizing. However, it's not consistently worse, and there are

java hashmap
Edit
Report

1 Answer

2

From the HashMap JavaDoc:

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

So if you're expecting 100 entries, perhaps a load factor of 0.75 and an initial capacity of ceiling(100/0.75) would be best. That comes down to 134.

I have to admit, I'm not certain why lookup cost would be greater for a higher load factor. Just because the HashMap is more "crowded" doesn't mean that more objects will be placed in the same bucket, right? That only depends on their hash code, if I'm not mistaken. So assuming a decent hash code spread, shouldn't most cases still be O(1) regardless of load factor?

EDIT: I should read more before posting... Of course the hash code cannot directly map to some internal index. It must be reduced to a value that fits the current capacity. Meaning that the greater your initial capacity, the smaller you can expect the number of hash collisions to be. Choosing an initial capacity exactly the size (or +1) of your object set with a load factor of 1 will indeed make sure that your map is never resized. However, it will kill your lookup and insertion performance. A resize is still relatively quick and would only occur maybe once, while lookups are done on pretty much any relevant work with the map. As a result, optimizing for quick lookups is what you really want here. You can combine that with never having to resize by doing as the JavaDoc says: take your required capacit

answered 2011-08-18T23:58:15.450

Your Answer