Hash Tables Study Guide - Revision history

Admin: Fix multiple accuracy errors: dictionary problem definition, open addressing load factor, double hashing formula, table header/labels, spelling, and worst-case complexity (via update-page on MediaWiki MCP Server)

2026-06-08T03:56:56Z

Fix multiple accuracy errors: dictionary problem definition, open addressing load factor, double hashing formula, table header/labels, spelling, and worst-case complexity (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 03:56, 8 June 2026
Line 5:		Line 5:
	'''hash table''' - data structure that uses key or value based lookup system		'''hash table''' - data structure that uses key or value based lookup system

	'''dictionary problem''' - ~~searching for an item in a structure; if item is not found~~, ~~you learn nothing new~~		'''dictionary problem''' - the classic problem of designing efficient data structures that implement associative arrays (supporting insert, delete, and search operations)

	'''hash function''' - a mapping from input objects to a hash table entry		'''hash function''' - a mapping from input objects to a hash table entry
Line 47:		Line 47:
	'''load factor''' - alpha - ratio of number of items N to number of buckets M, cost is proportional to load factor		'''load factor''' - alpha - ratio of number of items N to number of buckets M, cost is proportional to load factor

	'''open addressing''' - requires load factor is 1, stores elements directly instead of in buckets		'''open addressing''' - requires load factor < 1 (the table must not be completely full, or probing may fail to terminate); stores elements directly instead of in buckets

	'''linear probing''' - used with open addressing, collision handling technique in which a full element leads to a neighbor search (deletion becomes tricky, mark removed ~~nodes~~)		'''linear probing''' - used with open addressing, collision handling technique in which a full element leads to a neighbor search (deletion becomes tricky, mark removed slots)

	'''quadratic probing''' - alternative that provides more desirable properties than linear probing		'''quadratic probing''' - alternative that provides more desirable properties than linear probing
Line 56:		Line 56:

	<math>		<math>
	h(k) + i \cdot h^{\prime}(k)		(h(k) + i \cdot h^{\prime}(k)) \mod N
	</math>		</math>

Line 166:		Line 166:
	=Complexity and Cost=		=Complexity and Cost=

	Note: alpha is the loading factor, N/M, where N is the ~~nubmer~~ of elements		Note: alpha is the loading factor, N/M, where N is the number of elements
	in the hash table, and M is the number of buckets.		in the hash table, and M is the number of buckets.

	{\| class="wikitable" cellpadding="100" width="66%"		{\| class="wikitable" cellpadding="100" width="66%"
	!colspan="4"\|Big-O Complexity of ~~Lists~~		!colspan="4"\|Big-O Complexity of Hash Tables
	\|-		\|-
	\|		\|
	\|<br /><br />		\|<br /><br />
	~~Unsorted List~~ Hash ~~Map~~ (expected)		Hash Table (expected)
	\|<br /><br />		\|<br /><br />
	~~Unsorted List~~ Hash ~~Map~~ (worst)		Hash Table (worst)
	\|<br /><br />		\|<br /><br />
	Chained Hash Map		Chained Hash Map
Line 201:		Line 201:
	\|size		\|size
	\|O(1)		\|O(1)
	\|O(n)		\|O(1)
	\|O(1)		\|O(1)

Line 207:		Line 207:
	\|empty		\|empty
	\|O(1)		\|O(1)
	\|O(n)		\|O(1)
	\|O(1)		\|O(1)

Admin: /* Linear Probing Hash Table */

2017-09-03T23:35:38Z

Linear Probing Hash Table

← Older revision		Revision as of 23:35, 3 September 2017
Line 140:		Line 140:
	==Linear Probing Hash Table==		==Linear Probing Hash Table==

	~~find bucket slot~~(j,k) method:		findBucketSlot(j,k) method:
	* Find key k in bucket j		* Find key k in bucket j
	* if true, found match, returning location		* if true, found match, returning location
	* if false, not match, returning 1st available slot		* if false, not match, returning 1st available slot

	~~get bucket~~(j,k) method:		getBucket(j,k) method:
	* ~~find slot~~(j,k)		* findBucketSlot(j,k)
	* if found:		* if found:
	** return table value		** return table value

	~~set bucket~~(j,k,v) method:		setBucket(j,k,v) method:
	* ~~find slot~~(j,k)		* findBucketSlot(j,k)
	* if found:		* if found:
	** ~~bucketj~~[k] = v		** bucket_j[k] = v
	* else:		* else:
	** new item(k,v)		** new item(k,v)
	** ~~bucketj~~ insert new item		** bucket_j insert new item
	** update size		** update size

	~~remove bucket~~(j,k) method:		removeBucket(j,k) method:
	* ~~find slot~~(j,k)		* findBucketSlot(j,k)
	* if found:		* if found:
	** mark as vacated using AVAIL constant		** mark as vacated using AVAIL constant

Admin: /* Chained Hash Map */

2017-09-03T22:36:41Z

Chained Hash Map

← Older revision		Revision as of 22:36, 3 September 2017
Line 127:		Line 127:

	get bucket(j,k) method:		get bucket(j,k) method:
			* bucket_j = buckets[j]
	* return bucket_j[k]		* return bucket_j[k]

	set bucket(j,k,v)		set bucket(j,k,v)
			* bucket_j = buckets[j]
	* bucket_j[k] = v		* bucket_j[k] = v

	remove bucket(j,k) method:		remove bucket(j,k) method:
			* bucket_j = buckets[j]
	* del bucket_j[k]		* del bucket_j[k]

Admin: /* Hash Map base class */

2017-09-03T22:35:13Z

Hash Map base class

← Older revision		Revision as of 22:35, 3 September 2017
Line 105:		Line 105:

	get(k) method:		get(k) method:
	* j = ~~find bucket~~(k)		* j = hashFunction(k)
	* ~~get bucket~~(j,k)		* return getBucket(j,k)
	* return item

	set(k,v) method:		set(k,v) method:
	* j = ~~find bucket~~		* j = hashFunction(k)
	* ~~set bucket~~(j,k,v)		* setBucket(j,k,v)
	* update item
	* update size		* update size

	delete(k) method:		delete(k) method:
	* j = ~~find bucket~~(k)		* j = hashFunction(k)
	* ~~delete bucket~~(j,k)		* delBucket(j,k)
	* update size		* update size

	~~find bucket(k):~~		get, set, and delete methods are all public
	* return hash code(k)

	~~get, set, and delete methods are all public~~		hashFunction method varies depending on hash function chosen

	~~find bucket method~~, ~~get bucket method~~, ~~set bucket method~~ are private and depend on the concrete implementation		getBucket, setBucket, delBucket are private and depend on the concrete implementation

	==Chained Hash Map==		==Chained Hash Map==

Admin: /* Implementations */

2017-09-03T22:28:26Z

Implementations

← Older revision		Revision as of 22:28, 3 September 2017
Line 98:		Line 98:
	Probing Hash Table methods:		Probing Hash Table methods:
	* overrides getBucket/setBucket/delBucket to use linear/quadratic probing to find open slots		* overrides getBucket/setBucket/delBucket to use linear/quadratic probing to find open slots
	* implements AVAILABLE sentinel		* implements non-empty AVAILABLE sentinel

	=Algorithms for Operations=		=Algorithms for Operations=

Admin: /* Implementations */

2017-09-03T22:28:11Z

Implementations

← Older revision		Revision as of 22:28, 3 September 2017
Line 92:		Line 92:
	* getBucket/setBucket/delBucket methods		* getBucket/setBucket/delBucket methods
	* resize method		* resize method

			Chaining Hash Table methods:
			* overrides getBucket/setBucket/delBucket to use "chained" linked lists for buckets

			Probing Hash Table methods:
			* overrides getBucket/setBucket/delBucket to use linear/quadratic probing to find open slots
			* implements AVAILABLE sentinel

	=Algorithms for Operations=		=Algorithms for Operations=

Admin: /* Implementations */

2017-09-03T22:26:31Z

Implementations

← Older revision		Revision as of 22:26, 3 September 2017
Line 79:		Line 79:
	=Implementations=		=Implementations=

	Hash Table ~~base~~:		Hash Table fields/members:
	* table for data		* table for data
	* number of entries		* number of entries
Line 86:		Line 86:
	** scale a		** scale a
	** shift b		** shift b

			Hash Table methods:
	* hash function (universal/MAD function)		* hash function (universal/MAD function)
	* get/set/~~delete method~~		* get/set/del methods
			* getBucket/setBucket/delBucket methods
	* resize method		* resize method

Admin: /* Hash Table ADT */

2017-09-03T22:25:21Z

Hash Table ADT

← Older revision		Revision as of 22:25, 3 September 2017
Line 64:		Line 64:

	Hash Tables provide the following methods:		Hash Tables provide the following methods:
	* hashFunction		* hashFunction (turns key into index 0 to N-1)
	* get		* get
	* set		* set

Admin: /* Hash Table ADT */

2017-09-03T22:24:58Z

Hash Table ADT

← Older revision		Revision as of 22:24, 3 September 2017
Line 64:		Line 64:

	Hash Tables provide the following methods:		Hash Tables provide the following methods:
			* hashFunction
	* get		* get
	* set		* set
	* ~~remove~~		* del
			* getBucket (deletes an item from a particular bucket)
			* setBucket (sets the value of an item in a particular bucket)
			* delBucket (removes an item from a particular bucket)
	* size		* size
	* empty		* empty

Admin: /* Chained Hash Map */

2017-09-03T22:10:48Z

Chained Hash Map

← Older revision		Revision as of 22:10, 3 September 2017
Line 116:		Line 116:

	get bucket(j,k) method:		get bucket(j,k) method:
	* get bucket j		* return bucket_j[k]
	* return ~~bucket j~~[k]

	set bucket(j,k,v)		set bucket(j,k,v)
	* ~~get bucket j~~		* bucket_j[k] = v
	* update bucketj[k] = v

	remove bucket(j,k) method:		remove bucket(j,k) method:
	* ~~get bucket j~~		* del bucket_j[k]
	* remove bucketj[k]

	==Linear Probing Hash Table==		==Linear Probing Hash Table==