Direct Addressing on Huge Array

Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 223, Problem 11.1-4

Problem:
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.

Solution:
Simply speaking, given an uninitialized huge array, implement a dictionary.
Besides the huge array, one more array can be used to store the actual objects (or their pointers). Call these 2 arrays H and S, respectively. Initially, the arrays contains no records and define a variable n = 0. For a certain key k, if k already exists in the dictionary, we want to keep this relationship: H[k] = i and S[i] = k (or S[i] points to the object with key k). Therefore, H[ S[i] ] = i and S[ H[k] ] = k should both hold for a valid record.

Now we design the dictionary operations:
Initialize: build an empty stack.
Search: given a key k, test 1 ≤ H[k] ≤ n && S[ H[k] ] == k, if true, found and return S[ H[k] ]; otherwise, not found.
Insert: if key k already exists, replace it; otherwise push k into S, say, S[n+1] ← k and n ← n+1, and update the dictionary by H[k] ← n (already incremented).
Delete: delete the object with key k. First search to make sure the record is in the dictionary. If found, after simply deleting the record, there will be a gap in the entry with index H[k] in array S. Need fill in this gap while maintaining the correct relationship between H and S. This involves the following steps:

• S[ H[k] ] ← S[n]
• H[ S[n] ] ← H[k]
• H[k] ← NULL
• S[n] ← NULL
• n ← n-1

All these operations can be done in time O(1).

References:

http://ripcrixalis.blog.com/2011/02/08/hello-world/

http://www.cs.duke.edu/courses/summer02/cps130/Homeworks/Solutions/H11-solution.pdf