ConcurrentHashMap实现

Question

我已经编写了我自己的MyConcurrentHashMap的简化版本。我尝试使用Lock[]数组进行Lock条带化，以便如果需要的话，对MyConcurrentHashMap的所有put()操作都是通过锁进行的。此外，我还在内部创建了自己的MyHashMap，作为MyConcurrentHashMap的支持数据结构。我创建它是我自己的，因为我想将value字段限定为易失性读取操作，而不需要显式锁定。这确保了get()操作是一个非同步调用，在内存级别隐式锁定，通过易失性读取，而不是通过任何时候获取锁，从而使其更轻。查看并提供您的投入和改进(如果有的话)：

import java.util.LinkedList;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class MyConcurrentHashmap {

    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    private static final int INITIAL_CAPACITY = 16;

    private float LOAD_FACTOR = 0.75f;

    private int capacity = INITIAL_CAPACITY;

    private int size;

    private Lock[] locks;

    private MyHashMap myHashMap = new MyHashMap();

    private class MyHashMap {
        private LinkedList[] lists = new LinkedList[INITIAL_CAPACITY];

        private class MapEntry {
            final Object key;
            volatile Object value;

            MapEntry(Object key, Object value) {
                this.key = key;
                this.value = value;
            }
        }

        void put(Object key, Object value) {
            if (key == null)
                throw new IllegalArgumentException("Key Cannot be Null");
            int hash = key.hashCode();
            hash %= lists.length;
            if (size >= LOAD_FACTOR * lists.length) {
                capacity = lists.length * 2;
                LinkedList[] tempLists = new LinkedList[capacity];
                System.arraycopy(lists, 0, tempLists, 0, lists.length);
                lists = tempLists;
                reHash();
            }
            if (lists[hash] == null) {
                lists[hash] = new LinkedList<>();
                size++;
            }
            int i = 0;
            for (; i < lists[hash].size(); i++) {
                MapEntry mapEntry = (MapEntry) (lists[hash].get(i));
                if (mapEntry != null && mapEntry.key.equals(key)) {
                    mapEntry.value = value;
                    break;
                }
            }
            if (i == lists[hash].size()) {
                lists[hash].addLast(new MapEntry(key, value));
            }
        }

        Object get(Object key) {
            int hash = key.hashCode();
            hash %= lists.length;
            Object value = null;
            if (lists[hash] != null) {
                for (int i = 0; i < lists[hash].size(); i++) {
                    MapEntry mapEntry = (MapEntry) (lists[hash].get(i));
                    if (mapEntry != null && mapEntry.key.equals(key)) {
                        value = mapEntry.value;
                        break;
                    }
                }
            }
            return value;
        }

        private void reHash() {
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null) {
                    int hash = ((MapEntry) lists[i].getFirst()).key.hashCode();
                    hash %= lists.length;
                    if (i != hash) {
                        lists[hash] = lists[i];
                        lists[i] = null;
                    }
                }
            }

        }

        int size() {
            return size;
        }

        int capacity() {
            return capacity;
        }
    }

    public MyConcurrentHashmap(int concurrencyLevel) {
        locks = new Lock[concurrencyLevel];
        for (int i = 0; i < concurrencyLevel; i++) {
            locks[i] = new ReentrantLock();
        }
    }

    public MyConcurrentHashmap() {
        this(DEFAULT_CONCURRENCY_LEVEL);
    }

    public void put(Object key, Object value) {
        int hash = key.hashCode();
        hash %= myHashMap.capacity();
        locks[hash].lock();
        myHashMap.put(key, value);
        locks[hash].unlock();
    }

    public Object get(Object key) {
        return myHashMap.get(key);
    }

    public static void main(String[] args) {
        MyConcurrentHashmap myCCHashMap = new MyConcurrentHashmap();
        myCCHashMap.put(1, "Thomas");
        myCCHashMap.put(9, "Mathew");
        myCCHashMap.put(17, "Tissa");
        myCCHashMap.put(9, "Mathew Thomas");
        System.out.println(myCCHashMap.get(1));
        System.out.println(myCCHashMap.get(9));
        System.out.println(myCCHashMap.get(17));
    }

}

Answer 1

这是一项相当复杂的任务，我敢打赌一定会有问题的。

使用volatile Object value，您可以确保value的可见性，但是Object key在它之前就会被读取，而不是final。所以有很好的机会，它会破裂的。

    if (capacity == LOAD_FACTOR * lists.length) {

用浮点乘法，这可能永远不会发生.使用您的LOAD_FACTOR = 0.75f，它可以精确地表示为0.75，但是使用0.4，它将失败。测试应该是<=或>=，不知道哪个是正确的。

可能没有，因为您正在测试capacity，它永远不会改变。应该是size >= LOAD_FACTOR * lists.length。

get的正确性取决于LinkedList的内部工作。

    for (; i < lists[hash].size(); i++) {
        if (((MapEntry) (lists[hash].get(i))) != null
                && ((MapEntry) (lists[hash].get(i))).key.equals(key)) {
            ((MapEntry) (lists[hash].get(i))).value = value;
            break;
        }

由于LinkedList的get效率很低，所以效率加倍。实际上是三倍，因为你两次使用它。您应该迭代列表。

你把nulls列入名单了吗？如果不是，那你就不需要测试它们了。

为lists[hash]和i-th元素使用局部变量。

当你可以在break上保存自己的测试时，不要使用return

    if (i == lists[hash].size()) {
        lists[hash].addLast(new MapEntry(key, value));
    }

    hash %= lists.length;

由于您的list.length总是由两个人组成，所以您可以以更快的速度攻击：

    hash &= lists.length - 1;

  public Object get(Object key) {
    Integer hash = key.hashCode();
    hash %= myHashMap.capacity();
    return myHashMap.get(key);
  }

为什么是Integer？当你不使用hash时，为什么要使用它呢？