x*****0
发帖数: 452 | 1 下面这道题是在版上看到的一道题。请问大家有什么想法吗？
设计一个Map，满足下面的时间复杂度。
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? 把每一对
>作为一个node不断的加入link list?
randomly accessed array 是说可以直接用中的第一个Integer 作
为index吗？ |
x*****0
发帖数: 452 | |
l******u
发帖数: 1174 | 3 不就用一个Array, 每个元素放两个指针，元素的index对应key的hash值。第一个指针
指向一个linked list的头，另一个指针指向这个list的尾；这个list里面的key都有相
同的hash. (尾指针可以省去）。不知这样符合要求吗？ |
k*****u
发帖数: 136 | 4 那clear为什么是o（1）？
【在 l******u 的大作中提到】
: 不就用一个Array, 每个元素放两个指针，元素的index对应key的hash值。第一个指针
: 指向一个linked list的头，另一个指针指向这个list的尾；这个list里面的key都有相
: 同的hash. (尾指针可以省去）。不知这样符合要求吗？
|
z******t
发帖数: 25 | 5 每个元素添加一个generation value，并维护一个global generation，每次插入一个
元素，给它赋值当前的global generation。每次clear被调用，则global generation
+ 1。访问任何元素的时候，如果发现其generation value不等于global generation，
则说明这个元素是无效的。增加这个机制可以是clear操作也达到O（1） |
x*****0
发帖数: 452 | 6 也就是说，clear的时候，只要global generation + 1 就把所有的元素打成无效了。
谢谢啊！太感激了。
generation
【在 z******t 的大作中提到】
: 每个元素添加一个generation value，并维护一个global generation，每次插入一个
: 元素，给它赋值当前的global generation。每次clear被调用，则global generation
: + 1。访问任何元素的时候，如果发现其generation value不等于global generation，
: 则说明这个元素是无效的。增加这个机制可以是clear操作也达到O（1）
|
e********c
发帖数: 66 | 7 也许设计只是个幌子， 真正是看你知不知道LinkedHashMap。 |
