知道一个key的value, 能不能O(1)从HashMap里拿出对应key和value - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Java - 爪哇娇娃

知道一个key的value, 能不能O(1)从HashMap里拿出对应key和value

知道一个key的value, 能不能O(1)从HashMap里拿出对应key和value# Java - 爪哇娇娃

f*32013-11-11 08:11

1 楼

在做leetcode LRU，自己写个LinkedList没问题，但是想用java的实现，遇到困难了...
比如
HashMap map = new HashMap();
Integer key = new Integer(3);
map.put(key, 10);
LinkedList ll = new LinkedList();
ll.add(1);
ll.add(key); //同样的key object，加到linked list里面
ll.add(10);
// the list should be 1->3->10 now
int keyToLookUp = 3;
然后怎样可以在map里拿到原来的key object reference然后把ll里面对应的node删除
呢？就是HashMap里需要给key的value，找key的object reference。 LinkedList里需
要给node object reference，然后从list里删掉。我知道大概得用iterator，但是这
种情况怎么搞?

x*d2013-11-11 08:11

2 楼

indexOf(key) >>> remove()
Or
indexOf(new Integer(3)) >>> remove
Or
indexOf(3) >>> remove
I don't think I fully understand what a map is doing for you here, maybe I
dont understand your question at all. But just give you something to try.

x*d2013-11-11 08:11

3 楼

just search leetcode LRU, I guess I know what you talking about now.
LinkedList has remove(Object o), just remove it, dont even need to use
indexOf(Object o).

x*d2013-11-11 08:11

4 楼

LinkedList list = new LinkedList();
Integer inte = new Integer(3);
list.add(new Integer(3));
list.add(new Integer(3));
list.add(new Integer(5));
list.add(new Integer(3));
list.add(new Integer(5));

list.remove(inte);

// list.remove(new Integer(5));
list.removeLastOccurrence(new Integer(5));
System.out.println(list);

System.out.println(list.indexOf(3));
System.out.println(list.lastIndexOf(3));
System.out.println(list.indexOf(inte));
System.out.println(list.lastIndexOf(inte));

g*g2013-11-11 08:11

5 楼

Guava BiMap

...

【在 f**********3 的大作中提到】

: 在做leetcode LRU，自己写个LinkedList没问题，但是想用java的实现，遇到困难了...
: 比如
: HashMap map = new HashMap();
: Integer key = new Integer(3);
: map.put(key, 10);
: LinkedList ll = new LinkedList();
: ll.add(1);
: ll.add(key); //同样的key object，加到linked list里面
: ll.add(10);
: // the list should be 1->3->10 now

w*i2013-11-11 08:11

6 楼

我一开始也用了这样的方法，但是在Java里，LinkedList的remove方法最坏情况会遍历
整个链表，这样的话会超时的。我自己试过。
C++可以使用list的splice函数完成将某个指定的节点移到表头，Java我暂时没发现什
么现成的API可以在O(1)时间内解决。LinkedList里可以放自定义元素，增加prev和
next指针可以搞定。这样每次操作可以以指定节点为起点，而不是以表头节点为起点。
我代码贴在了：
http://blog.csdn.net/whuwangyi/article/details/15495845

f*32013-11-11 08:11

7 楼

大牛，这个面试题不好用这种特殊的library吧

【在 g*****g 的大作中提到】

: Guava BiMap
:
: ...

x*d2013-11-11 08:11

8 楼

过不了leetcode oj是肯定的。喂马非要注册呢，我还想玩玩，麻烦。

【在 f**********3 的大作中提到】

: 大牛，这个面试题不好用这种特殊的library吧

x*d2013-11-11 08:11

9 楼

remove(int index) is O(n)
Iterator.remove() is O(1)

【在 w*******i 的大作中提到】

: 我一开始也用了这样的方法，但是在Java里，LinkedList的remove方法最坏情况会遍历
: 整个链表，这样的话会超时的。我自己试过。
: C++可以使用list的splice函数完成将某个指定的节点移到表头，Java我暂时没发现什
: 么现成的API可以在O(1)时间内解决。LinkedList里可以放自定义元素，增加prev和
: next指针可以搞定。这样每次操作可以以指定节点为起点，而不是以表头节点为起点。
: 我代码贴在了：
: http://blog.csdn.net/whuwangyi/article/details/15495845

w*i2013-11-11 08:11

10 楼

你的意思是说，当把entry存到链表中后，与其对应的listIterator存到map里么？

【在 x****d 的大作中提到】

: remove(int index) is O(n)
: Iterator.remove() is O(1)

f*32013-11-11 08:11

11 楼

问题就是怎样才能让iterator O(1)到给定的key里呢？

【在 x****d 的大作中提到】

: remove(int index) is O(n)
: Iterator.remove() is O(1)

w*i2013-11-11 08:11

12 楼

我也有这样的问题，暂时理解是这样：例如你有一个LinkedList结构表示双向
链表，那么hash map里不要存，而是应该存>。这样要进行remove操作只需要将这个listIterator的prev和next连起来就可
以了。
当然，这个设想还有待验证，我有空去试试。

【在 f**********3 的大作中提到】

: 问题就是怎样才能让iterator O(1)到给定的key里呢？

f*32013-11-11 08:11

13 楼

觉得这java.util提供的LinkedList比我自己写得难用多了，竟然2天都没搞清楚怎么
delete一个node

ListIterator

【在 w*******i 的大作中提到】

:
: 我也有这样的问题，暂时理解是这样：例如你有一个LinkedList结构表示双向
: 链表，那么hash map里不要存，而是应该存: >。这样要进行remove操作只需要将这个listIterator的prev和next连起来就可
: 以了。
: 当然，这个设想还有待验证，我有空去试试。

x*d2013-11-11 08:11

14 楼

itorator.next()==key

【在 f**********3 的大作中提到】

: 问题就是怎样才能让iterator O(1)到给定的key里呢？

x*d2013-11-11 08:11

15 楼

I am not saying anything to your problem. Just pointing out that in general
itorator.remove() is O(1). I don't know if that helps your problem.
and btw itorator is not exactly the same as listitorator.

ListIterator

【在 w*******i 的大作中提到】

x*d2013-11-11 08:11

16 楼

and we were talking about something about java collections in the other
thread, and many people says
"java collections framework is not 高深", i agree.
but I strongly suggest java beginners to spend lot of time fooling around
with this topic. just my 2 cents.

f*82013-11-11 08:11

17 楼

所以有现在有些面试真让人头疼，实际工作中，当然用类库。我的TEAM里就有只会算法
的HELLO WOLRD程序员，觉得自己会了算法就什么都懂，设计个WEB APP连到DB，连
CONNECTIOn POOL都不用。实际中有必要自己去做个CACHE吗。

【在 f**********3 的大作中提到】

: 大牛，这个面试题不好用这种特殊的library吧

g*g2013-11-11 08:11

18 楼

你不能抄袭实现吗？

【在 f**********3 的大作中提到】

: 大牛，这个面试题不好用这种特殊的library吧

x*d2013-11-11 08:11

19 楼

do you know how much will power it needs to open any source code done by
others? LOL
most java programmer never see or compile source code shipped with java.
same for hibernate, spring. I am one of those lazy bones too, lol. Now java
is true open source, how many of you really read into the code of javap,
javac? I havent, i feel shame some times, but you know, shame is what keep
us going as human being, lol...

【在 g*****g 的大作中提到】

: 你不能抄袭实现吗？

g*g2013-11-11 08:11

20 楼

Guava is open source, and AbstractBiMap has 400 lines total, out of them
less than 50 lines essential to answer his question. I don't check javap or
javac implementation at all, but I do check the implementation of library
classes I am using from time to time, because the javadoc doesn't answer all
my questions.
If you have to write a data structure from scratch, I don't know better way
than copy and modify an existing one.

java

【在 x****d 的大作中提到】

: do you know how much will power it needs to open any source code done by
: others? LOL
: most java programmer never see or compile source code shipped with java.
: same for hibernate, spring. I am one of those lazy bones too, lol. Now java
: is true open source, how many of you really read into the code of javap,
: javac? I havent, i feel shame some times, but you know, shame is what keep
: us going as human being, lol...