我们希望通过利用在一个非常大的数组上直接寻址的方式来实现字典。开始时，该数组中可能包含废料，但要对整个数组进行初始化是不实际的，因为该数组的规模太大。请给出在大数组上实现直接寻址字典方案。每个存储的对象占用O(1)的空间；操作search，insert，delete的时间为O(1)；对数据结构初始化时间为O(1)。 （提示：可以利用另外一个栈，其大小等于实际存储在字典中的关键字数目，以帮助确定大型数组中某个给定的项是否是有效的）

solution:
We denote the huge array by T and, taking the hint from the book, we also have a
stack implemented by an array S. The size of S equals the number of keys actually
stored, so that S should be allocated at the dictionary’s maximum size. The stack
has an attribute top[S], so that only entries S[1 . . top[S]] are valid.
The idea of this scheme is that entries of T and S validate each other. If key k is
actually stored in T , then T [k] contains the index, say j , of a valid entry in S, and
S[ j ] contains the value k. Let us call this situation, in which 1 ≤ T [k] ≤ top[S],
S[T [k]] = k, and T [S[ j ]] = j, a validating cycle.
Assuming that we also need to store pointers to objects in our direct-address table,
we can store them in an array that is parallel to either T or S. Since S is smaller
than T , we’ll use an array S , allocated to be the same size as S, for these pointers.
Thus, if the dictionary contains an object x with key k, then there is a validating
cycle and S [T [k]] points to x.
The operations on the dictionary work as follows:
• Initialization: Simply set top[S] = 0, so that there are no valid entries in the
stack.
• SEARCH: Given key k, we check whether we have a validating cycle, i.e.,
whether 1 ≤ T [k] ≤ top[S] and S[T [k]] = k. If so, we return S [T [k]],
and otherwise we return NIL.
• INSERT: To insert object x with key k, assuming that this object is not already
in the dictionary, we increment top[S], set S[top[S]] ← k, set S [top[S]] ← x,
and set T [k] ← top[S].
• DELETE: To delete object x with key k, assuming that this object is in the
dictionary, we need to break the validating cycle. The trick is to also ensure
that we don’t leave a “hole” in the stack, and we solve this problem by moving
the top entry of the stack into the position that we are vacating—and then Þxing
up that entry’s validating cycle. That is, we execute the following sequence of
assignments:
S[T [k]] ← S[top[S]]
S [T [k]] ← S [top[S]]
T [S[T [k]]] ← T [k]
T [k] ← 0
top[S] ← top[S] − 1
Each of these operations—initialization, SEARCH, INSERT, and DELETE—takes
O(1) time.