关于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就可以了。。。。





  • 自己改写了个,用到了Java里的ReentrantLockCondition

    改进空间:

    • 加入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 我没上课,以老师说的为准。


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待