P*B
2 楼
看看有什么明天10x的
k*g
3 楼
C++路过
s*x
4 楼
Linkedlist 呗，very simple.
Remember how LRU cache is implemented? A hash table plus linked list.
Remember how LRU cache is implemented? A hash table plus linked list.
z*g
5 楼
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.
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
6 楼
一个一个bucket 走，每个bucket 都走一遍linkedlist
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/
【在 M*******a 的大作中提到】
: 应该是遍历一下O(n)的时间复杂度，n应该是现有元素个数。
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/
【在 M*******a 的大作中提到】
: 应该是遍历一下O(n)的时间复杂度，n应该是现有元素个数。
M*a
7 楼
我也这么想的，但是好像实现的有点overhead，相当于任何hashtable实际都是个
linked hashtable.
【在 s**x 的大作中提到】
: Linkedlist 呗，very simple.
: Remember how LRU cache is implemented? A hash table plus linked list.
linked hashtable.
【在 s**x 的大作中提到】
: Linkedlist 呗，very simple.
: Remember how LRU cache is implemented? A hash table plus linked list.
M*a
8 楼
这样的话貌似就不是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/
有2个元素，这样iterate的话是O(100)而不是O(2)
【在 w**z 的大作中提到】
: 一个一个bucket 走，每个bucket 都走一遍linkedlist
: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/
w*z
9 楼
HashMap 本来就不适合 iterate
【在 M*******a 的大作中提到】
: 这样的话貌似就不是O(n)的iterate了，假设这个hashtable初始的size为100，然后只
: 有2个元素，这样iterate的话是O(100)而不是O(2)
【在 M*******a 的大作中提到】
: 这样的话貌似就不是O(n)的iterate了，假设这个hashtable初始的size为100，然后只
: 有2个元素，这样iterate的话是O(100)而不是O(2)
w*z
10 楼
LS说了， O(m + n)
【在 M*******a 的大作中提到】
: 这样的话貌似就不是O(n)的iterate了，假设这个hashtable初始的size为100，然后只
: 有2个元素，这样iterate的话是O(100)而不是O(2)
【在 M*******a 的大作中提到】
: 这样的话貌似就不是O(n)的iterate了，假设这个hashtable初始的size为100，然后只
: 有2个元素，这样iterate的话是O(100)而不是O(2)
相关阅读