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 initializing the data structure should take \(O(1)\) time. (Hint: Use an additional array, treated somewhat like a 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.)
Let’s call our huge array \(A\). Let \(S\) be an empty stack which we will populate with keys that we know hold actual values within \(A\). Finally, let \(m\) be a map array that is the same size as the universe of keys with each value as \(NIL\) to begin with.
SEARCH(A, k)
1 if m[k] == NIL:
2 return NIL
3 else if S[m[k]] == k:
4 return A[k]
5 else:
6 return NIL
The validation step on lines 3 and 4 is not strictly necessary unless we expect there to be some garbage data introduced outside of the operations defined in this solution. The key point here is we’re confirming the existence of proper entries in both \(m\) and \(S\) before extracting the appropriate value from \(A\). All of this happens in constant time.
INSERT(A, x)
1 if m[x.key] == NIL:
2 S.push(x.key)
3 m[x.key] = S.length - 1
4 A[x.key] = x.value
When inserting a value, we always want to update the huge array with that new value. We also need to maintain accuracy in \(S\) and \(m\) but this is only necessary if there is not currently a value held by \(m\) in position \(x.key\). If a value already exists there then we can simply use the existing mapping as it still indicates a valid value coming from the huge array. Every operation here takes constant time to perform.
DELETE(A, x)
01 if m[x.key] == NIL:
02 return
03 else:
04 i = m[x.key]
05 j = S.length - 1
06 S[i] = S[j]
07 m[S[i]] = i
08 S.pop()
09 m[x.key] = NIL
10 A[x.key] = NIL
When deleting we need to ensure that \(S\) is still accurate and we do so by placing the element to be removed in the top position (lines 6-8) and then popping it off. Afterwards we remove all related data from \(m\) and \(A\). Every operation here happens in constant time.