click below
click below
Normal Size Small Size show me how
Hash Tables
Question | Answer |
---|---|
A ___________ is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector). | hash table |
In a hash table, an item's ___________ is the value used to map to an index. | key |
Each hash table array element is called a ___________. | bucket |
A ___________ computes a bucket index from the item's key. | hash function |
A common hash function uses the ___________ , which computes the integer remainder when dividing two numbers. | modulo operator % |
A ___________ occurs when an item being inserted into a hash table maps to the same bucket as an existing item in the hash table. | collision |
____ handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket. | Chaining |
A hash table with ___________ handles a collision by starting at the key's mapped bucket, and then linearly searches subsequent buckets until an empty bucket is found. | linear probing |
___________ is a collision resolution technique where collisions are resolved by looking for an empty bucket elsewhere in the table. | open addressing |
An ___________ bucket has been empty since the hash table was created. | empty-since-start |
An ___________ bucket had an item removed that caused the bucket to now be empty. | empty-after-removal |
A hash table with ___________ handles a collision by starting at the key's mapped bucket, and then quadratically searches subsequent buckets until an empty bucket is found. | quadratic probing |
Iterating through sequential i values to obtain the desired table index is called the ___________. | probing sequence |