Maps/Operations and Performance - Revision history

Admin: Fix mislabeled CSV columns ("Per 1k" → "Per Op"); update OpenJDK link from Java 7 to current; add note about broken git links; clarify description (via update-page on MediaWiki MCP Server)

2026-06-08T04:36:52Z

Fix mislabeled CSV columns ("Per 1k" → "Per Op"); update OpenJDK link from Java 7 to current; add note about broken git links; clarify description (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 04:36, 8 June 2026
Line 1:		Line 1:
	=Notes=		=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.		According to OpenJDK source code, TreeMap should take O(log N) time for <code>containsKey</code>, <code>get</code>, <code>put</code>, and <code>remove</code> 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~~-mirror~~/~~jdk7u-~~jdk/blob/master/src/share/classes/java/util/TreeMap.java		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=		=Code=
Line 9:		Line 9:
	==Map timing classes==		==Map timing classes==

	There are three links on git.charlesreid1.com:		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		* TimingBuiltinMap — times the built-in HashMap and TreeMap types https://git.charlesreid1.com/cs/java/src/master/hash/timing/TimingBuiltinMap.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		* 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=		=Results=
Line 18:		Line 19:
	==Timing 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:		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]])		* Custom-written Chained Hash Map class (see [[Hash_Maps/ChainedHashMap]])
	* Built-in HashMap class		* Built-in HashMap class
Line 32:		Line 34:

	===CSV data===		===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).

	<pre>		<pre>
	*** Chained Hash Map ***		*** Chained Hash Map ***

	N, Walltime Insert Tot (ms), Walltime Insert Per 1k (ms), Walltime Rm Tot (ms), Walltime Rm Per 1k (ms)		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		100, 299.0000, 0.2990, 261.0000, 0.2610
	200, 327.0000, 0.3270, 226.0000, 0.2260		200, 327.0000, 0.3270, 226.0000, 0.2260
Line 53:		Line 57:
	*** Hash Map ***		*** Hash Map ***

	N, Walltime Insert Tot (ms), Walltime Insert Per 1k (ms), Walltime Rm Tot (ms), Walltime Rm Per 1k (ms)		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		100, 208.0000, 0.2080, 154.0000, 0.1540
	200, 236.0000, 0.2360, 154.0000, 0.1540		200, 236.0000, 0.2360, 154.0000, 0.1540
Line 70:		Line 74:
	*** Tree Map ***		*** Tree Map ***

	N, Walltime Insert Tot (ms), Walltime Insert Per 1k (ms), Walltime Rm Tot (ms), Walltime Rm Per 1k (ms)		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		100, 297.0000, 0.2970, 234.0000, 0.2340
	200, 299.0000, 0.2990, 232.0000, 0.2320		200, 299.0000, 0.2990, 232.0000, 0.2320

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:39:10Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:39, 9 October 2019
Line 10:		Line 10:

	There are three links on git.charlesreid1.com:		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		* 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://charlesreid1.com~~:3000~~/cs/java/src/master/hash/timing/TimingChained.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://charlesreid1.com~~:3000~~/cs/java/src/master/hash/timing/TimingCompare.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=		=Results=

Admin: /* Code */

2017-06-29T02:52:32Z

Code

← Older revision		Revision as of 02:52, 29 June 2017
Line 13:		Line 13:
	* TimingChained - times the custom designed chained hash table implementation https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingChained.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		* 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

			=Results=

	==Timing Results==		==Timing Results==

Admin: /* Timing Results */

2017-06-29T02:49:27Z

Timing Results

@@ Line 20: / Line 20: @@
 * Built-in HashMap class
 * Built-in TreeMap class
 <pre>
@@ Line 70: / Line 80: @@
 , 343.0000, 0.3430, 273.0000, 0.2730
 </pre>
 =Flags=

Admin at 02:33, 29 June 2017

2017-06-29T02:33:47Z

@@ Line 1: / Line 1: @@
 =Notes=
-Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java
+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.
 =Flags=

Admin at 02:20, 29 June 2017

2017-06-29T02:20:56Z

← Older revision		Revision as of 02:20, 29 June 2017
Line 3:		Line 3:
	Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java		Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java

	According to OpenJDK source code, TreeMap should take O(log N) time. So, the TreeMap ~~only LOOKS like it~~ is O(1)~~. Have to get to really large TreeMaps to get actual O(N) performance, I guess~~.		According to OpenJDK source code, TreeMap should take O(log N) time. However, the TreeMap is apparently O(1).

	https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TreeMap.java		It seems that you have to get to very large TreeMaps to get actual O(N) performance. (Meaning, it probably utilizes a large initial hash map size, incurring less overhead for access and maintenance but higher cost in storage/memory.)

			Here is a link to the TreeMap class: https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TreeMap.java

	=Flags=		=Flags=

Admin at 00:34, 28 June 2017

2017-06-28T00:34:14Z

← Older revision		Revision as of 00:34, 28 June 2017
Line 4:		Line 4:

	According to OpenJDK source code, TreeMap should take O(log N) time. So, the TreeMap only LOOKS like it is O(1). Have to get to really large TreeMaps to get actual O(N) performance, I guess.		According to OpenJDK source code, TreeMap should take O(log N) time. So, the TreeMap only LOOKS like it is O(1). Have to get to really large TreeMaps to get actual O(N) performance, I guess.

			https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TreeMap.java

	=Flags=		=Flags=

Admin at 00:33, 28 June 2017

2017-06-28T00:33:06Z

← Older revision		Revision as of 00:33, 28 June 2017
Line 1:		Line 1:
			=Notes=

	Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java		Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java

			According to OpenJDK source code, TreeMap should take O(log N) time. So, the TreeMap only LOOKS like it is O(1). Have to get to really large TreeMaps to get actual O(N) performance, I guess.

			=Flags=

	{{MapsFlag}}		{{MapsFlag}}

Admin: Created page with "Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java {{MapsFlag}} Category:Maps Category:Java"

2017-06-27T08:42:58Z

Created page with "Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java {{MapsFlag}} Category:Maps Category:Java"

New page

Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java

{{MapsFlag}}

[[Category:Maps]]
[[Category:Java]]