Maps/Operations and Performance

Notes

According to OpenJDK source code, TreeMap should take O(log N) time for containsKey, get, put, and remove operations. This is verified by the results below — the cost of insert/remove grows with N, but very slowly (logarithmically).

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

Code

Map timing classes

There are three links on git.charlesreid1.com (note: these links may be unavailable as of 2025):

• TimingBuiltinMap — times the built-in HashMap and TreeMap types https://git.charlesreid1.com/cs/java/src/master/hash/timing/TimingBuiltinMap.java
• TimingChained — times the custom designed chained hash table implementation https://git.charlesreid1.com/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://git.charlesreid1.com/cs/java/src/master/hash/timing/TimingCompare.java

Results

Timing Results

Here is the raw output of the comparison program above. This program gathers statistics over multiple runs to determine the amortized per-operation cost of insert and 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

Plots

CSV data

The "Tot" column is the total wall-clock time across all runs for the given map size N. The "Per Op" column is the amortized per-operation cost (Tot divided by the total number of operations).

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

N, Walltime Insert Tot (ms), Walltime Insert Per Op (ms), Walltime Rm Tot (ms), Walltime Rm Per Op (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 Op (ms), Walltime Rm Tot (ms), Walltime Rm Per Op (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 Op (ms), Walltime Rm Tot (ms), Walltime Rm Per Op (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