My implementations of HashMap and ConcurrentHashMap。难点，MyConcurrentHashMap 的 get() 可以不用加锁，大大提高了性能

MyConcurrentHashMap.java

import java.util.concurrent.locks.ReentrantLock;

public class MyConcurrentHashMap<K,V> {
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 256;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private Segment<K,V>[] segments;

    /**
     * The number of key-value mappings contained in this map.
     */
    private volatile int size;

    private int capacity;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    private final float loadFactor;

    public MyConcurrentHashMap() {
        this.capacity = DEFAULT_INITIAL_CAPACITY;
        this.loadFactor = DEFAULT_LOAD_FACTOR;

        final int smallCapacity = this.capacity / DEFAULT_CONCURRENCY_LEVEL;
        this.segments = new Segment[DEFAULT_CONCURRENCY_LEVEL];
        for (int i = 0; i < DEFAULT_CONCURRENCY_LEVEL; ++i) {
            segments[i] = new Segment<>(smallCapacity, loadFactor);
        }
    }

    V put(K key, V value) throws InterruptedException {
        int segmentIndex = key.hashCode() % DEFAULT_CONCURRENCY_LEVEL;
        size++;
        return segments[segmentIndex].put(key, value);
    }

    V get(K key) throws InterruptedException {
        int segmentIndex = key.hashCode() % DEFAULT_CONCURRENCY_LEVEL;
        return segments[segmentIndex].get(key);
    }


    static class Segment<K,V> {
        private final MyHashMap<K,V> map;
        private final ReentrantLock lock;

        Segment(int initialCapacity, float loadFactor) {
            this.map = new MyHashMap<>(initialCapacity, loadFactor);
            this.lock = new ReentrantLock();
        }

        V put(K key, V value) throws InterruptedException {
            lock.lockInterruptibly();
            try {
                return map.put(key, value);
            } finally {
                lock.unlock();
            }
        }

        // 用 HashEntry 对象的不变性来降低读操作对加锁的需求
        // http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/index.html
        V get(K key) throws InterruptedException {
            if (map.size == 0)
                return null;

            if (key == null) throw new IllegalArgumentException();

            int index = key.hashCode() % map.table.length;

            for (MyHashMap.Node<K,V> cur = map.table[index]; cur != null; cur = cur.next) {
                if (cur.key.equals(key)) {
                    V v = cur.getValue();
                    if (v != null) {
                        return v;
                    } else {
                        return readValueUnderLock(map.table[index]);
                    }
                }
            }

            V value = map.get(key);
            if (value != null) return value;

            // recheck under lock
            lock.lockInterruptibly();
            try {
                return map.get(key);
            } finally {
                lock.unlock();
            }
        }

        private V readValueUnderLock(MyHashMap.Node<K, V> node) throws InterruptedException {
            this.lock.lockInterruptibly();
            try {
                return node.value;
            } finally {
                this.lock.unlock();
            }
        }
    }
}

MyHashMap.java

import java.util.Map;

public class MyHashMap<K, V> {
    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private Node<K,V>[] table;

    /**
     * The number of key-value mappings contained in this map.
     */
    private volatile int size;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    private final float loadFactor;

    public MyHashMap() {
        table = new Node[DEFAULT_INITIAL_CAPACITY];
        loadFactor = DEFAULT_LOAD_FACTOR;
    }
    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public MyHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        this.loadFactor = loadFactor;
        this.table = new Node[tableSizeFor(initialCapacity)];
    }

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (key == null) throw new IllegalArgumentException();
        if (value == null) throw new IllegalArgumentException();

        int index = key.hashCode() % table.length;

        V oldValue = null;
        if (table[index] == null) {
            table[index] = new Node(key, value, null);
        } else {
            Node cur = table[index];
            for (; cur.next != null; cur = cur.next) {
                if (cur.key == key) {
                    oldValue = (V) cur.value;
                    cur.value = value; // update
                    break;
                }
            }
            if (cur.next == null) {
                if (cur.key == key) {
                    oldValue = (V) cur.value;
                    cur.value = value; // update
                } else { // insert before the head
                    Node newNode = new Node(key, value, table[index]);
                    table[index] = newNode;
                }
            }
        }
        size++;
        // optional
        if (size >= loadFactor * table.length) {
            Node<K, V>[] tmp = new Node[table.length * 2];
            System.arraycopy(table, 0, tmp, 0, table.length);
            table = tmp;
            reHash();
        }
        return oldValue;
    }

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     */
    public V get(K key) {
        if (key == null) throw new IllegalArgumentException();

        int index = key.hashCode() % table.length;

        for (Node cur = table[index]; cur != null; cur = cur.next) {
            if (cur.key == key) {
                return (V) cur.value;
            }
        }
        return null;
    }

    public int size() {
        return size;
    }
    
    private void reHash() {
        for (int i = 0; i < table.length; ++i) {
            if (table[i] != null) {
                int newIndex = table[i].key.hashCode() % table.length;
                if (i != newIndex) {
                    table[newIndex] = table[i];
                    table[i] = null;
                }
            }
        }
    }

    static class Node<K,V> implements Map.Entry<K,V> {
        final K key;
        volatile V value;
        final Node<K,V> next;

        Node(K key, V value, Node<K,V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    }

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
}