are HashMaps with predefined capacity faster

hashmap, java

Solution

Predefining the expected size of any container-type class will provide faster storage time simply because the storage doesn't have to be dynamically re-allocated at runtime as often. Usually the backing storage is some sort of array, and when you go beyond the available capacity, the array has to be copied into a new larger array. This is an expensive operation that may have to happen multiple times if you store a large number of objects into a container that started at a very small capacity.

The performance of reading from the map shouldn't be affected either way. You could demonstrate this better by timing the `tm.put` part separately from the `tm.get` part.

Edit: To illustrate this point further, I modified the code to time `tm.put` separately from `tm.get`. Here are the results on my machine:

total time for TreeMap tm.put: 159
total time for TreeMap tm.get: 74
total time for Hashtable tm.put: 20
total time for Hashtable tm.get: 10
total time for HashMap tm.put: 42
total time for HashMap tm.get: 5
total time for Hashtable presized tm.put: 11
total time for Hashtable presized tm.get: 9
total time for HashMap presized tm.put: 6
total time for HashMap presized tm.get: 4

Notice that the difference between `Hashtable` regular and presized for `tm.put` is a factor of ~2. SImilarly, with `HashMap` the difference between regular and presized is a factor of ~7 for storing. However, looking at the reading side, both `Hashtable` and `Hashmap` have roughly the same timings for `tm.get` in both cases (`10 ms` vs `9 ms` for `Hashtable`, and `5 ms` vs `4 ms` for `HashMap`). Also notice that in the presized case, both putting and getting take roughly about the same amount of total time.

Problem

I came across an algorithm on the net http://www.coderanch.com/t/201836/Performance/java/Hashtable-vs-Hashmap and decided to test it ``` public class MapTest{ static int sizeOfTrial = 100000; static String[] keys = new String[sizeOfTrial]; static String[] vals = new String[sizeOfTrial]; public static void main(String[] args) { //init sizeOfTrial key/value pairs for (int i=0; i < sizeOfTrial; i++){ String s1 = "key"+ i; String s2 = "val"+ i; keys[i] = s1; vals[i] = s2; } test(new TreeMap(), "TreeMap"); test(new Hashtable(), "Hashtable"); test(new HashMap(), "HashMap"); test(new Hashtable(200000), "Hashtable presized"); test(new HashMap(200000), "HashMap presized"); } public static void test(Map tm, String name){ long t1 = System.currentTimeMillis(); for (int i=0; i < sizeOfTrial; i++){ tm.put(keys[i],vals[i]); } for (int i=0; i < sizeOfTrial; i++){ tm.get(keys[i]); } long t2 = System.currentTimeMillis(); System.out.println("total time for " + name + ": " + (t2-t1)); } } ``` and i got the following results ``` total time for TreeMap: 1744 total time for Hashtable: 446 total time for HashMap: 234 total time for Hashtable presized: 209 total time for HashMap presized: 196 ``` Is this JVM dependent and arbitrary or does it really provide faster access and storage time?

Original source