关于implement thread safe queue and hash map的问题

yrfzh

有同学在之前的onsite面试的时候遇到了implement thread safe queue and hash map。请问implement thread safe queue and hash map有什么要注意的？？？还有有没有什么推荐的教程关于implement thread safe queue and hash map？？？

Hefang_Li

我也有这个疑问，java.util.concurrent package 里面有blocking queue和hashmap，面试的时候可以直接拿来用吗？还是要自己加锁呢？谢谢~

Wenzhe

自己先尝试写一个read和write都是thread safe的代码，然后再优化？

如何提高read的效率？
如何提高write的效率？
如何实现分布式？（这个有点像设计数据库的题目了）

ConcurrentHashMap里面用到比较高级的锁分段技术，在面试现场不大可能要求写出来，但是至少知道原理。如果知道点Joshua Bloch的故事就更好玩了，因为Java的concurrency库很大部分是他重写的。

@Hefang_Li 如果面试题目就是要写thread-safe的queue和hash map，我觉得应该不能用现成的库。向面试官提一下java.util.concurrent倒是必须的。

Disclaimer: 我是吃瓜路人，一切以老师/助教解答为准。

yrfzh

我也很想知道！！！google也搜不到想要的答案。。。不知道是不是只要在冲突的步骤加上lock就可以了。。。。

ywsun

@yrfzh 也不至于google不到…
https://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html

Wenzhe

自己改写了个，用到了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();
      }
    }
}

Hefang_Li

@Wenzhe 你的code写的真棒。有个小疑问，老师上课说推荐用signalAll()，这里会比signal()好吗？

Wenzhe

@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 我没上课，以老师说的为准。