Maps/Operations and Performance

Notes

According to OpenJDK source code, TreeMap should take O(log N) time. This is verified by the results below - the cost of insert/remove grows with N, but very slowly.

Here is a link to the TreeMap class implemented in the Java API (link is to OpenJDK mirror on Github): https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TreeMap.java

Code

Map timing classes

There are three links on git.charlesreid1.com:

• TimingBuiltinMap - times the built-in HashMap and TreeMap types https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingBuiltinMap.java
• TimingChained - times the custom designed chained hash table implementation https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingChained.java
• TimingCompare - times the built-in map types and compares them with the custom designed hash table implementations https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingCompare.java

Timing Results

Here is the raw output of the comparison program above. This program gathers statistics over 10,000 runs to determine the amortized cost of 1,000 insert or remove operations in ms. These costs are compared for each of three map types:

• Custom-written Chained Hash Map class (see Hash_Maps/ChainedHashMap)
• Built-in HashMap class
• Built-in TreeMap class

 ***** Chained Hash Map *****

N, Walltime Insert Tot (ms), Walltime Insert Per 1k (ms), Walltime Rm Tot (ms), Walltime Rm Per 1k (ms)
100, 299.0000, 0.2990, 261.0000, 0.2610
200, 327.0000, 0.3270, 226.0000, 0.2260
300, 349.0000, 0.3490, 278.0000, 0.2780
400, 449.0000, 0.4490, 339.0000, 0.3390
500, 465.0000, 0.4650, 384.0000, 0.3840
600, 449.0000, 0.4490, 424.0000, 0.4240
700, 479.0000, 0.4790, 463.0000, 0.4630
800, 558.0000, 0.5580, 517.0000, 0.5170
900, 583.0000, 0.5830, 531.0000, 0.5310
1000, 707.0000, 0.7070, 574.0000, 0.5740




 ***** Hash Map *****

N, Walltime Insert Tot (ms), Walltime Insert Per 1k (ms), Walltime Rm Tot (ms), Walltime Rm Per 1k (ms)
100, 208.0000, 0.2080, 154.0000, 0.1540
200, 236.0000, 0.2360, 154.0000, 0.1540
300, 214.0000, 0.2140, 136.0000, 0.1360
400, 194.0000, 0.1940, 136.0000, 0.1360
500, 193.0000, 0.1930, 137.0000, 0.1370
600, 182.0000, 0.1820, 137.0000, 0.1370
700, 193.0000, 0.1930, 157.0000, 0.1570
800, 204.0000, 0.2040, 157.0000, 0.1570
900, 195.0000, 0.1950, 158.0000, 0.1580
1000, 167.0000, 0.1670, 134.0000, 0.1340




 ***** Tree Map *****

N, Walltime Insert Tot (ms), Walltime Insert Per 1k (ms), Walltime Rm Tot (ms), Walltime Rm Per 1k (ms)
100, 297.0000, 0.2970, 234.0000, 0.2340
200, 299.0000, 0.2990, 232.0000, 0.2320
300, 317.0000, 0.3170, 259.0000, 0.2590
400, 320.0000, 0.3200, 253.0000, 0.2530
500, 279.0000, 0.2790, 271.0000, 0.2710
600, 343.0000, 0.3430, 282.0000, 0.2820
700, 313.0000, 0.3130, 247.0000, 0.2470
800, 347.0000, 0.3470, 287.0000, 0.2870
900, 326.0000, 0.3260, 289.0000, 0.2890
1000, 343.0000, 0.3430, 273.0000, 0.2730