A hash table is a widely used structure for storing and retrieving key–value pairs. This lesson introduces the map abstraction, how a hash table locates data, why collisions occur, and how load factor relates to performance.
An associative array, also called a dictionary or map, stores pairs consisting of a key and an associated value. Keys are unique, and a map supports operations such as insertion, lookup, and deletion. For example, a contact list might map a person’s name to a phone number.
All flashcards
What is an associative array?
An abstract data type that stores key–value pairs, with unique keys, and supports operations such as lookup, insertion, and deletion.
What is a hash map?
A map or associative array implemented using a hash table.
Define a hash collision.
A collision occurs when two different keys produce the same index in a hash table.
How is load factor calculated, and what does it indicate?
Load factor is α=n/m, where n is the number of stored elements and m the number of buckets. It indicates how full the table is and helps predict collision or probe costs.
What is the universe U in the definition of a hash function?
It is the set of possible keys that the hash function accepts. The function maps these keys to valid table indices.
Quiz questions
What abstract data type does a hash table commonly implement?Answer: A map that associates unique keys with values.
When does a hash collision occur?Answer: When different keys map to the same table index.
A hash table has 20 buckets and stores 10 key–value pairs. What is its load factor?Answer: α=10/20=0.5.
Why is average O(1) performance not a guarantee that every hash-table operation takes constant time?Answer: Collisions and resizing can make individual operations take longer.
Based on the Wikipedia article Hash table, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.