M*******a
发帖数: 1633 | 1 应该是遍历一下O(n)的时间复杂度，n应该是现有元素个数。 |
k***g
发帖数: 166 | |
s**x
发帖数: 7506 | 3 Linkedlist 呗，very simple.
Remember how LRU cache is implemented? A hash table plus linked list. |
z******g
发帖数: 271 | 4 C路过
But if I were to do it, I would make the iterator data structure contain the
bucket size, a bucket cursor and a reference to the underlying linked list
node. The worst case time complexity would be O(m + n) where m is the bucket
size. |
w**z
发帖数: 8232 | 5 一个一个bucket 走，每个bucket 都走一遍linkedlist
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/
【在 M*******a 的大作中提到】
: 应该是遍历一下O(n)的时间复杂度，n应该是现有元素个数。
|
M*******a
发帖数: 1633 | 6 我也这么想的，但是好像实现的有点overhead，相当于任何hashtable实际都是个
linked hashtable.
【在 s**x 的大作中提到】
: Linkedlist 呗，very simple.
: Remember how LRU cache is implemented? A hash table plus linked list.
|
M*******a
发帖数: 1633 | 7 这样的话貌似就不是O(n)的iterate了，假设这个hashtable初始的size为100，然后只
有2个元素，这样iterate的话是O(100)而不是O(2)
【在 w**z 的大作中提到】
: 一个一个bucket 走，每个bucket 都走一遍linkedlist
: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/
|
w**z
发帖数: 8232 | 8 HashMap 本来就不适合 iterate
【在 M*******a 的大作中提到】
: 这样的话貌似就不是O(n)的iterate了，假设这个hashtable初始的size为100，然后只
: 有2个元素，这样iterate的话是O(100)而不是O(2)
|
w**z
发帖数: 8232 | 9 LS说了， O(m + n)
【在 M*******a 的大作中提到】
: 这样的话貌似就不是O(n)的iterate了，假设这个hashtable初始的size为100，然后只
: 有2个元素，这样iterate的话是O(100)而不是O(2)
|
