Implement a dictionary by using direct addressing on a huge array

For the following question from Introduction to Algorithms book, "We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct address dictionary on a huge array. Each stored object should use $$O(1)$$ space; the operations SEARCH, INSERT, and DELETE should take $$O(1)$$ time each; and the initialization of the data structure should take $$O(1)$$ time. (Hint: Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)"

Problem: can you please help explaining the wording of the question in your own words? No solution is needed.

• Are you sure about the additional stack? To me it doesn't sound as an efficient data structure for supporting lookups in a hash table. Aug 29, 2021 at 13:18
• @Chaos. Thanks for reply. Yes, this is from the book!
– Avv
Aug 29, 2021 at 13:20
• Ok, i see what they did there. Aug 29, 2021 at 13:22
• Glad you liked my answer! :) Aug 29, 2021 at 13:32

2 Answers

"We wish to implement a dictionary by means of an hashing function that maps all its possible inputs to a huge but finite set of natural numbers of size $$k$$. The function is implemented by values of an array witnessing the presence/lack of any element. The array is expensive to setup, so we ask that the algorithm does not clear it. (It is used for holding pointers to present elements.) Describe an algorithm for granting, constant time operations, constant space usage for items storage (pointers to objects) and constant initialisation time. ( Hint. Employ and additional stack for avoiding false positives on insert/removal and lookup operations.)"

False positives are due to the presence of garbage. Possibly the most nebulous part is the usage of the stack. Since it is bounded in size (at most $$k$$), you will have to scan from it at most $$k$$ elements. Since it's size is bounded you can have lookups in O($$k$$) and that's constant time.

• How is $O(k)$ constant time? nobody said anything about the size of $k$ being bounded. Aug 29, 2021 at 13:48
• Direct hashing requires $k$ to be known and constant and as such bounded. It can be set at compile time (actual constant) o before the algorithm is run (configuration value). What matters is that it does not change during execution. Aug 29, 2021 at 13:50
• What is $k$ in your definition? I thought you meant it is the number of items in the map Aug 29, 2021 at 13:51
• It is the size of the range of the hash function, also the size of the array. Well, it depends on how you actually definite the hash function but it at least must be the size of the array. Aug 29, 2021 at 13:53
• The size of the array is said to be "huge" and thus it is impractical to go through the entire array. Did I misunderstand you? Aug 29, 2021 at 13:55

Here is another hint: how would you find whether an element is valid in $$O(1)$$ in this auxiliary stack? Try to somehow "connect" the index at the original huge array, to the place in the stack that says that this element is indeed valid. Don't be afraid to use another auxiliary array for this!

• Initializing the auxiliary stack won't be $O(1)$. Is it? Aug 29, 2021 at 14:01
• @InuyashaYagami Without clearing the data in it, there is a way to do this. since its a stack - we know exactly which elements are valid: all elements with an index less than the current number of items in the stack. Aug 29, 2021 at 15:08
• @Avra I think you got it right - something along the lines that you wrote in the first comment should work. If something wasn't initialized then it will either map to outside the stack size (and hence is invalid) or will map to an element within the stack, which will point back to a different value, hence we know it is not really valid. Aug 29, 2021 at 15:12
• @InuyashaYagami we don't need to. There is a way to do it without this initialization. If you want, I can post it as a full answer (but it doesn't look like the OP wanted a full answer anyways) Aug 29, 2021 at 18:24
• tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall09/Homeworks/… Aug 30, 2021 at 5:21