Hash tables
No description yet. This curated deck is ready for daily study.
Card preview (12)
Define Hash table
A data structure that implements an associative array (dictionary)
How is data stored in an associative array?
As a collection of key-value pairs
What is hashing?
The position of the data within the array is determined by applying a hashing algorithm to the key
What is the hashing algorithm called?
A hash function
Pros of hash tables
Enable efficient searching Maintaining data in a hash table is very efficient
Why must you use an array to implement hash tables?
So you can access each position of the array directly by specifying the index of the position
What are the positions within an array called?
Buckets
What’s a bucket?
A single piece of data or complex data object stored alongside a key
Load factor =
N (number of occupied buckets) / K (Number of buckets)
What is the optimal load factor?
0.75
What are the main requirements of a hash function?
Always produces the same hash value for the same key Provides a uniform distribution of hash values- every value has an equal chance of being generated Minimises clustering- keys don’t produce the same hash value Be fast to compute
Define a collision
When 2 or more different keys produce the same hash value