Java并发编程（三）--并发数据结构

ConcurrentHashMap的设计实现

为什么还需要ConcurrentHashMap，不是有了Hashtable吗。如果所有的事情都用Synchronized去解决，那么这个世界会变得很糟糕。

ConcurrentHashMap最绝妙的地方是采用了锁分段技术，一种分而治之的策略，一个HashMap被分为了几个Segment，在每个Segment里面实行同步控制。

对ConcurrentHashMap的操作首先找到相应的Segment，然后在Segment里面进行操作

public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, false);
}
final Segment<K,V> segmentFor(int hash) {
        return segments[(hash >>> segmentShift) & segmentMask];
    }
这种所分段方法本身有利于多线程操作。
但是ConcurrentHashMap所做的还不止这些，源代码中对Segment中Entry的读取操作并未加锁！
V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry<K,V> e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }

 

 

首先找到对应的项，如果不为null就直接返回，否则调用readValueUnderLock方法。需要注意的就是那个readValueUnderLock(e)方法

/**
         * Reads value field of an entry under lock. Called if value
         * field ever appears to be null. This is possible only if a
         * compiler happens to reorder a HashEntry initialization with
         * its table assignment, which is legal under memory model
         * but is not known to ever occur.
         */
        V readValueUnderLock(HashEntry<K,V> e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }

 

源码注释的解释是编译器可能会对HashEntry进行重排序，这对JMM来说是允许的。我的理解还是此时会有其他线程会对value进行更新，所以需要加锁，等待其他线程更新之后获取value。

 

CopyOnWriteArrayList设计实现

所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。

 

BlockingQueue设计实现

天生的生产者消费者型的数据结构。

BlockingQueue的实现，两把锁takeLock和putLock，两个信号量（条件变量）notEmpty和notFull，基于PV原理实现。Await操作支持延迟，所以相应的put和take也支持延迟操作。

 

ConcurrentLinkedQueue的设计实现

一个基于非阻塞算法的链表队列。非阻塞算法比较难理解的一个地方是多个指针或者引用如何运用CAS操作。此处只涉及两个指针，一offer操作为例：

public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        Node<E> n = new Node<E>(e);
        retry:
        for (;;) {
            Node<E> t = tail;
            Node<E> p = t;
            for (int hops = 0; ; hops++) {
                Node<E> next = succ(p);
                if (next != null) {
                    if (hops > HOPS && t != tail)
                        continue retry;
                    p = next;
                } else if (p.casNext(null, n)) {
                    if (hops >= HOPS)
                        casTail(t, n); // Failure is OK.
                    return true;   
                } else {
                    p = succ(p);
                }
            }
        }
    }

 

对于多个指针的修改可能会使数据结构状态不一致，例如第一个引用的指向修改成功了，但是第二个修改失败的情形，这中间如果有其它线程对数据结构进行操作就有可能产生不可预知的问题。一般采用多线程协助操作的策略进行非阻塞处理，如果第一个线程有未完成的操作，后续线程能够判断出并可以帮助它继续完成。对于offer操作，如果其他线程在更新是发现尾节点一致，但是尾节点的后继节点不为空，那么表示上一线程操作未完成，则在此线程会继续在循环里设置尾节点为当前尾节点的后继。