Maps - Revision history

Admin: Fix mathematical inaccuracy (maps are functions, not bijections); fix hash example syntax; fix Gödel reference; correct etymology of "hash" (via update-page on MediaWiki MCP Server)

2026-06-08T04:06:19Z

Fix mathematical inaccuracy (maps are functions, not bijections); fix hash example syntax; fix Gödel reference; correct etymology of "hash" (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 04:06, 8 June 2026
Line 1:		Line 1:
	See also: [[Dictionaries]]		See also: [[Dictionaries]]

	Maps are value-based data structures that create a ~~bijection~~ from one set onto another, such that one input key yields one corresponding output value.		Maps are value-based data structures that create a mapping from one set (the domain) onto another (the range), such that one input key yields one corresponding output value.

	=Notes=		=Notes=

	Using the term "map" in place of the term "dictionary" is a hat tip to the mathematical nature of a map. The mathematical definition of a function is, a mapping from one set (the domain) onto another (the range) such that one input corresponds to exactly one output~~. This is a bijective mapping between two sets~~. This is all that is required of a function - one input gives one output. Likewise, a programming map is ~~define~~ as a key-value data structure, in which an input key can be used to find the resulting value in O(1) time.		Using the term "map" in place of the term "dictionary" is a hat tip to the mathematical nature of a map. The mathematical definition of a function is, a mapping from one set (the domain) onto another (the range) such that one input corresponds to exactly one output. This is all that is required of a function - one input gives one output. Likewise, a programming map is defined as a key-value data structure, in which an input key can be used to find the resulting value in O(1) time.

			Note that a map is a function (each key maps to exactly one value), but it is not necessarily a bijection: multiple distinct keys may map to the same value, and not every value in the codomain need have a corresponding key. The term "bijection" would require a one-to-one correspondence in both directions, which maps do not guarantee.

	Maps can be implemented multiple ways. They can be stored as a simple unsorted array of key-value item objects. They can be stored in a sorted array of key-value items. They can be stored with a tree. They can be stored with a hash table. etc.		Maps can be implemented multiple ways. They can be stored as a simple unsorted array of key-value item objects. They can be stored in a sorted array of key-value items. They can be stored with a tree. They can be stored with a hash table. etc.
Line 33:		Line 35:
	* 0s and 1s are numbers, in binary, so we can convert them to numbers, in decimal.		* 0s and 1s are numbers, in binary, so we can convert them to numbers, in decimal.

	(Note the similarities between this approach and Gödel's approach with his [[Incompleteness ~~Theorem~~]] of assigning numbers to mathematical proofs/theories.)		(Note the similarities between this approach and Gödel's approach with his [[Incompleteness Theorems]] of assigning numbers to mathematical proofs/theories.)

	This gives us a way of turning arbitrary objects/data into arbitrary integers.		This gives us a way of turning arbitrary objects/data into arbitrary integers.

	<pre>		<pre>
	hash('\0B') == hash'\0\0C') == 64		hash('\0B') == hash('\0\0C') == 64
	</pre>		</pre>

Line 66:		Line 68:
	* If we pass a mutable type as a key, we are going to change the input to the hash table/map, and therefore change the output location, and therefore lose our data.		* If we pass a mutable type as a key, we are going to change the input to the hash table/map, and therefore change the output location, and therefore lose our data.
	* To prevent this, need to define an immutable list, or use an immutable object, or define a __hash__ function for any key types that we use that will return the same hash regardless of content.		* To prevent this, need to define an immutable list, or use an immutable object, or define a __hash__ function for any key types that we use that will return the same hash regardless of content.
	* Example: we might pass a customer object to a database application. The customer may change (e.g., phone number, address, etc.), but this should not affect hash of object, otherwise looks like entirely new "Customer". Could ~~luse~~ customer ID only when computing hash function.		* Example: we might pass a customer object to a database application. The customer may change (e.g., phone number, address, etc.), but this should not affect hash of object, otherwise looks like entirely new "Customer". Could use customer ID only when computing hash function.

	===Solving memory hog issue===		===Solving memory hog issue===
Line 72:		Line 74:
	To solve the issue of hash tables being memory hogs, we have a second step that we call hashing. (Prehashing is turning keys into numbers; hashing is turning numbers into tinier sets of numbers.) Like turning a potato into hash browns. Like turning tofu into tofu crumble. Like turning large boulders into sand.		To solve the issue of hash tables being memory hogs, we have a second step that we call hashing. (Prehashing is turning keys into numbers; hashing is turning numbers into tinier sets of numbers.) Like turning a potato into hash browns. Like turning tofu into tofu crumble. Like turning large boulders into sand.

	~~Arabic~~ hash ~~- grass~~		The word "hash" comes from the French ''hacher'' ("to chop into small pieces"), from Old French ''hache'' ("axe"), which is of Germanic origin and related to "hatchet."

	~~German hash - hashae -~~ hatchet

	Want to map a giant key space to a hash table with slots 0 to n-1. Need a hash function that will turn key 0 into position 0, key 1 into position 1, etc.		Want to map a giant key space to a hash table with slots 0 to n-1. Need a hash function that will turn key 0 into position 0, key 1 into position 1, etc.

Admin: /* Map Implementations */

2017-06-27T04:22:28Z

Map Implementations

← Older revision		Revision as of 04:22, 27 June 2017
Line 139:		Line 139:

	Map implementations using hash tables:		Map implementations using hash tables:
	* [[Maps/AbstractHashMap]] - abstract class defining further details of implementing a map using a hash table		* [[Hash Maps/AbstractHashMap]] - abstract class defining further details of implementing a map using a hash table
	* [[Maps/ChainHashMap]] - concrete implementation of hash map using a chained hash map		* [[Hash Maps/ChainHashMap]] - concrete implementation of hash map using a chained hash map
	* [[Maps/ProbeHashMap]] - concrete implementation of hash map using linear probing.		* [[Hash Maps/ProbeHashMap]] - concrete implementation of hash map using linear probing.

	=Flags=		=Flags=

	{{MapsFlag}}		{{MapsFlag}}

Admin: /* Map Implementations */

2017-06-27T04:21:27Z

Map Implementations

← Older revision		Revision as of 04:21, 27 June 2017
Line 139:		Line 139:

	Map implementations using hash tables:		Map implementations using hash tables:
	* ~~[[Maps/HashMapBase]] -~~ [[Maps/AbstractHashMap]] - abstract class defining further details of implementing a map using a hash table		* [[Maps/AbstractHashMap]] - abstract class defining further details of implementing a map using a hash table
	* [[Maps/ChainHashMap]] - concrete implementation of hash map using a chained hash map		* [[Maps/ChainHashMap]] - concrete implementation of hash map using a chained hash map
	* [[Maps/ProbeHashMap]] - concrete implementation of hash map using linear probing.		* [[Maps/ProbeHashMap]] - concrete implementation of hash map using linear probing.

Admin: /* Map Implementations */

2017-06-27T04:19:37Z

Map Implementations

← Older revision		Revision as of 04:19, 27 June 2017
Line 131:		Line 131:

	Map abstract data type:		Map abstract data type:
	* [[Maps/~~AbstractMap~~]]		* [[Maps/ADT]] - Map interface class
			* [[Maps/AbstractMap]] - AbstractMap abstract class
	Map ~~base~~ class ~~(implements most of the ADT above):~~
	* [[Maps/~~MapBase~~]]

	Map implementations using arrays:		Map implementations using arrays:
	* [[Maps/UnsortedArrayMap]]		* [[Maps/UnsortedArrayMap]] - concrete implementation of Map using unsorted ArrayList
	* [[Maps/SortedArrayMap]]		* [[Maps/SortedArrayMap]] - concrete implementation of Map using sorted ArrayList

	Map implementations using hash tables:		Map implementations using hash tables:
	* [[Maps/HashMapBase]]		* [[Maps/HashMapBase]] - [[Maps/AbstractHashMap]] - abstract class defining further details of implementing a map using a hash table
	* [[Maps/ChainHashMap]]		* [[Maps/ChainHashMap]] - concrete implementation of hash map using a chained hash map
	* [[Maps/ProbeHashMap]]		* [[Maps/ProbeHashMap]] - concrete implementation of hash map using linear probing.

	=Flags=		=Flags=

	{{MapsFlag}}		{{MapsFlag}}

Admin: /* Hash Table Expansion */

2017-06-27T04:08:06Z

Hash Table Expansion

@@ Line 94: / Line 94: @@
 ==Hash Table Expansion==
-Once we have our hash table implemented, we'll want to start adding lots of items. But then, we have to strike a balance.
+{{Main|Hash Maps/Dynamic Resizing}}
 ==Maps ADT==

Admin: /* Collision Handling with Chaining */

2017-06-27T04:07:14Z

Collision Handling with Chaining

@@ Line 90: / Line 90: @@
 ==Collision Handling with Chaining==
-Chaining is a way of using linked lists to deal with the problem of turning a huge keyspace with a tiny number of keys into actual usable slots in an array.
+{{Main|Hash Maps/Collision Handling with Chaining}}
 ==Hash Table Expansion==

Admin: /* Hash Table Expansion */

2017-06-22T03:45:59Z

Hash Table Expansion

← Older revision		Revision as of 03:45, 22 June 2017
Line 193:		Line 193:
	* Only a few - log N - operations are expensive		* Only a few - log N - operations are expensive

	Similarly, deletions should happen when we get to n < m/4 quarter ~~sized~~ table		Similarly, deletions should happen when we get to n < m/4 quarter-full table
	* Should shrink table size by half		* Should shrink table size by half
	* As we saw before, shrinking table size by quarter, we can have single table size or add/remove operation that costs O(N)		* As we saw before, shrinking table size by quarter, we can have single table size or add/remove operation that costs O(N)
	* Cost of n inserts		* Cost of n inserts
			* Slow operation if we shrink by half when table is empty by half:
			* slow operation is 2^k <--insert/delete--> (2^k) + 1
			* This is a Theta(n) operation
			* When you are a quarter full, you shrink by half
			* Amortized time is Theta(1)
			* Little bit tricky to prove...

	===Amortization===		===Amortization===

Admin: /* Amortization */

2017-06-22T03:39:59Z

Amortization

← Older revision		Revision as of 03:39, 22 June 2017
Line 201:		Line 201:

	An operation takes "T(n) amortized" if k operations take <math> \leq k \cdot T(n)</math> time		An operation takes "T(n) amortized" if k operations take <math> \leq k \cdot T(n)</math> time

			k inserts take theta(k) time, so this is O(1) amortized insert

	==Maps ADT==		==Maps ADT==

Admin: /* Amortization */

2017-06-22T03:37:21Z

Amortization

← Older revision		Revision as of 03:37, 22 June 2017
Line 199:		Line 199:

	===Amortization===		===Amortization===

			An operation takes "T(n) amortized" if k operations take <math> \leq k \cdot T(n)</math> time

	==Maps ADT==		==Maps ADT==

Admin: /* Hash Table Expansion */

2017-06-22T03:36:00Z

Hash Table Expansion

← Older revision		Revision as of 03:36, 22 June 2017
Line 196:		Line 196:
	* Should shrink table size by half		* Should shrink table size by half
	* As we saw before, shrinking table size by quarter, we can have single table size or add/remove operation that costs O(N)		* As we saw before, shrinking table size by quarter, we can have single table size or add/remove operation that costs O(N)
	* Cost of n inserts		* Cost of n inserts



			===Amortization===

	==Maps ADT==		==Maps ADT==