请教一道数据结构的设计题

http://www.mitbbs.com/article_t/JobHunting/32999171.html

发信人: xiaoc10 (大棕子), 信区: JobHunting
标  题: 请教一道数据结构的设计题
发信站: BBS 未名空间站 (Mon Jun 29 16:05:01 2015, 美东)

下面这道题是在版上看到的一道题。请问大家有什么想法吗？

设计一个Map<Integer, Integer>，满足下面的时间复杂度。
add: O(1)  deletion: O(1)  lookup: O(1)  clear:O(1)  iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1)  deletion: O(1)  lookup: O(1)  clear: O(size of array)   iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1)  deletion: O(number of elements)  lookup:O(number of elements)  
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。

对于这题的提示，sequential array指的就是link list? 把每一对<Integer, Integer
>作为一个node不断的加入link list?
randomly accessed array 是说可以直接用<Integer, Integer>中的第一个Integer 作
为index吗？