a*********2
发帖数: 187 | 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)
所以我们需要把这两个方法整合起来。
*******************************************************
很显然这道题要用到hash table,但是一般而言，hash table的clear(删除整个table)
需要O(n), 怎么做到O(1)的clear呢？ |
p*****2
发帖数: 21240 | 2 这个HashMap为什么不行？clear再生成一个新的instance不行吗？留给GC解决。 |
a*********2
发帖数: 187 | 3 Hashmap的存储必须要是连续空间，才可以直接clear掉吧？ 如果有conflict，每个
cell里面是一个linkedlist，那应该得一个cell一个cell的clear，不能直接clear掉
hashtable吧？
【在 p*****2 的大作中提到】
: 这个HashMap为什么不行？clear再生成一个新的instance不行吗？留给GC解决。
|
t********5
发帖数: 522 | 4 我也觉得直接remove reference让referenceCount = 0就行了 |
p*****2
发帖数: 21240 | 5 直接扔掉就行了
【在 a*********2 的大作中提到】
: Hashmap的存储必须要是连续空间，才可以直接clear掉吧？ 如果有conflict，每个
: cell里面是一个linkedlist，那应该得一个cell一个cell的clear，不能直接clear掉
: hashtable吧？
|
c*****m
发帖数: 271 | 6 这个想法真可以
【在 p*****2 的大作中提到】
: 这个HashMap为什么不行？clear再生成一个新的instance不行吗？留给GC解决。
|
