大数组的直接寻址
题目
我们希望通过利用在一个非常大的数组上直接寻址的方式来实现字典。开始时，该数组中可能包含废料，但要对整个数组进行初始化是不实际的，因为该组的规模太大。请给出在大数组上实现直接寻址字典的方案。每个存储的对象占用O(1)空间；操作SEARCH、INSERT和DELETE的时间为O(1)；对数据结构初始化的时间为O(1)。
思考
- 对一个很大的数组，受到数组大小的影响，实现数组初始化是相当困难的。因此，在数组中很多位置上的数据有可能是垃圾数据，并不是对我们有用的，由于没有初始化，我们很难判定对应的索引上的值是否有效。
- 在书中给出了提示，利用一个附加数组，处理方式类似与栈，其大小等于市集存储在字典中的关键字数目，以帮助确定大数组中某个给定的项是否有效。
其本质意思就是说，建立两层索引，第一层由索引确定的值作为第二层的索引，若果该索引确实存在，就证明给定的项存在
具体说明就是，大数组为Array，哈希函数为hash，栈为St
假设一个项key,查找进行的操作就是,首先进行 value = hash(key),此value就是此key在Array的位置，根据此索引得到一个值index = Array[value],再根据此index在St中寻找，如果栈中有此索引，那么这个值就存在，且St(index) == key,总的来说就是 St[Array[hash[key]]] == key;