MOD 6_ZYBOOKS 8_ALGORITHM ANALYSIS & HASHING TABLES Flashcards
(20 cards)
What is a hash table?
A hash table is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector).
Ex: Given an array with indices 0..9 to store integers from 0..500, the modulo (remainder) operator can be used to map 25 to index 5 (25 % 10 = 5), and 149 to index 9 (149 % 10 = 9).
A hash table’s main advantage is that searching (or inserting / removing) an item may require only O(1), in contrast to O(N) for searching a list or to O(log N) for binary search.
In a hash table, what is an item’s key?
In a hash table, an item’s key is the value used to map to an index. For all items that might possibly be stored in the hash table, every key is ideally unique, so that the hash table’s algorithms can search for a specific item by that key.
Each hash table array element is called a ____. A ____ function computes a bucket index from the item’s key.
Bucket, hash
A common hash function includes?
Modulo operator (%)
What is a collision? What techniques are used to handle collisions?
A collision occurs when an item being inserted into a hash table maps to the same bucket as an existing item in the hash table.
Ex: For a hash function of key % 10, 55 would be inserted in bucket 55 % 10 = 5; later inserting 75 would yield a collision because 75 % 10 is also 5.
Various techniques are used to handle collisions during insertions, such as chaining or open addressing.
What is chaining?
Chaining is a collision resolution technique where each bucket has a list of items (so bucket 5’s list would become 55, 75).
What is open addressing?
Open addressing is a collision resolution technique where collisions are resolved by looking for an empty bucket elsewhere in the table (so 75 might be stored in bucket 6).
Describe how Chaining handles hash table collisions.
Chaining handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket. The insert operation first uses the item’s key to determine the bucket, and then inserts the item in that bucket’s list. Searching also first determines the bucket, and then searches the bucket’s list. Likewise for removes.
VIEW: Hash table with chaining: Each bucket contains a list of items
What is linear probing?
A hash table with linear probing 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 distinguishes which two types of empty buckets?
An empty-since-start bucket has been empty since the hash table was created.
An empty-after-removal bucket had an item removed that caused the bucket to now be empty. The distinction will be important during searches, since searching only stops for empty-since-start, not for empty-after-removal.
What does a hash table INSERT algorithm do?
Using linear probing, a hash table insert algorithm uses the item’s key to determine the initial bucket, linearly probes (or checks) each bucket, and inserts the item in the next empty bucket (the empty kind doesn’t matter). If the probing reaches the last bucket, the probing continues at bucket 0. The insert algorithm returns true if the item was inserted, and returns false if all buckets are occupied.
What does a hash table REMOVE algorithm do?
Using linear probing, a hash table remove algorithm uses the sought item’s key to determine the initial bucket. The algorithm probes each bucket until either a matching item is found, an empty-since-start bucket is found, or all buckets have been probed. If the item is found, the item is removed, and the bucket is marked empty-after-removal.
What does a hash table SEARCH algorithm do?
In linear probing, a hash table search algorithm uses the sought item’s key to determine the initial bucket. The algorithm probes each bucket until either the matching item is found (returning the item), an empty-since-start bucket is found (returning null), or all buckets are probed without a match (returning null). If an empty-after-removal bucket is found, the search algorithm continues to probe the next bucket.
What is quadratic probing? What is a probing sequence?
VIEW: HashInsert with quadratic probing
The ____ algorithm uses the probing sequence until the key being searched for is found or an empty-since-start bucket is found. The ____ algorithm searches for the key to remove and, if found, marks the bucket as empty-after-removal.
Search, removal
VIEW: HashRemove and HashSearch with quadratic probing
What is double hashing?
Using double hashing, a hash table ____ algorithm probes (or checks) each bucket using the probing sequence defined by the two hash functions. The search continues until either the matching item is found (returning the item), an empty-since-start bucket is found (returning null), or all buckets are probed without a match (returning null).
A hash table ____ algorithm probes each bucket using the probing sequence, and inserts the item in the next empty bucket (the empty kind doesn’t matter).
A hash table ____ algorithm first searches for the item’s key. If the item is found, the item is removed, and the bucket is marked empty-after-removal.
Search, insert, removal
