关于implement thread safe queue and hash map的问题
-
有同学在之前的onsite面试的时候遇到了implement thread safe queue and hash map。请问implement thread safe queue and hash map有什么要注意的???还有有没有什么推荐的教程关于implement thread safe queue and hash map???
-
我也有这个疑问,java.util.concurrent package 里面有blocking queue和hashmap,面试的时候可以直接拿来用吗?还是要自己加锁呢?谢谢~
-
自己先尝试写一个read和write都是thread safe的代码,然后再优化?
- 如何提高read的效率?
- 如何提高write的效率?
- 如何实现分布式?(这个有点像设计数据库的题目了)
ConcurrentHashMap
里面用到比较高级的锁分段技术,在面试现场不大可能要求写出来,但是至少知道原理。如果知道点Joshua Bloch的故事就更好玩了,因为Java的concurrency库很大部分是他重写的。@Hefang_Li 如果面试题目就是要写thread-safe的queue和hash map,我觉得应该不能用现成的库。向面试官提一下
java.util.concurrent
倒是必须的。Disclaimer: 我是吃瓜路人,一切以老师/助教解答为准。
-
我也很想知道!!!google也搜不到想要的答案。。。不知道是不是只要在冲突的步骤加上lock就可以了。。。。
-
@yrfzh 也不至于google不到…
https://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html
-
自己改写了个,用到了Java里的
ReentrantLock
和Condition
。改进空间:
- 加入Generic Type
- 内部容器改用
java.util.Collections
里的类 (不知道考官允不允许)。也可以改用linked list。 - 如果Queue满了,
put()
应该是blocking还是non-blocking?如果是non-blocking,那么“满”这个信息是通过return value返回还是通过exception来返回?
public class ArrBlockingQueue { final private Lock _lock = new ReentrantLock(); final private Condition _notFull = _lock.newCondition(); final private Condition _notEmpty = _lock.newCondition(); final private Object[] _items; private int _putptr, _takeptr, _count; public ArrBlockingQueue(final int size) { // Assuming size is valid here _items = new Object[size]; } public void put(final Object x) throws InterruptedException { _lock.lock(); try { while (_count == _items.length) _notFull.await(); _items[_putptr] = x; if (++_putptr == _items.length) _putptr = 0; ++_count; _notEmpty.signal(); } finally { _lock.unlock(); } } public Object take() throws InterruptedException { _lock.lock(); try { while (_count == 0) _notEmpty.await(); Object x = _items[_takeptr]; if (++_takeptr == _items.length) _takeptr = 0; --_count; _notFull.signal(); return x; } finally { _lock.unlock(); } } }
-
@Wenzhe 你的code写的真棒。有个小疑问,老师上课说推荐用signalAll(),这里会比signal()好吗?
-
@Hefang_Li 这个题目里我没看出区别,我感觉如果不确定的话就用
signalAll()
吧。Updates
细想了一下,signalAll()
会是一个更好的选择。如果有多个threads在等待.await()
,signalAll()
会唤醒所有的threads,然后拥有最高priority的thread将优先执行,这样threads之间的优先级得到保留。而signal()
之会随机选择一个thread,并不考虑优先级。除非特别原因(比如性能上的考虑),我觉得选
signalAll()
会比较好。参考文章
wait(), notify() and notifyAll() in Java - A tutorial
notify vs. notifyALL
虽然文章谈的是notifyAll()
,但大部分论据应该也适用于signalAll()
。Disclaimer 我没上课,以老师说的为准。