Why are maps sometimes referred to as "associative stores"?
Given the hash function
h(k) = k % tableSize
show the result after inserting elements with the following key values, in the order shown:
42, 64, 33, 12, 24, 55, 20, 9
Indicate the position of the keys if open addressing is used with linear probing for collision resolution.
Indicate the position of the keys if open addressing is used with quadratic probing for collision resolution.
Indicate the position of the keys if open addressing is used with double hashing for collision resolution, where the secondary hash function is
h'(k) = 7 - ( k % 7 )
Indicate the position of the keys if separate chaining is used for collision resolution.
How do we typically handle the problem that deleting an element from a mapping represented as a hash table using open addressing might stop the get(k) method from finding elements that collided with the element that was just removed?
The definition of the dictionary ADT given in the textbook specifies that the find(k) operation returns an arbitrary entry (k, v) whose key is equal to k. If the definition were changed to specify that find(k) returns the first entry (k, v) whose key is equal to k that was inserted into the dictionary, which data structure would best support this specification? What modification to the standard algorithms of that data structure would be required to guarantee the correct operation of this revised version of the find(k) operation?
Binary search of an ordered search table runs in O(log n) time. Is that bound an average-case or a worst-case bound? Is it probabilistic (i.e., "expected") or deterministic?
What is the difference between dichotomous and trichotomous binary search? Which one is "better"? Why?
What are the advantages and disadvantages of skip lists compared with the use of binary search on an ordered search table (which is implemented with an ordered array list)?
