From charlesreid1

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:

Results

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:

Plots

Error creating thumbnail: Unable to save thumbnail to destination
Error creating thumbnail: Unable to save thumbnail to destination
Error creating thumbnail: Unable to save thumbnail to destination

CSV data

 ***** 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

Flags