使用你熟悉的语言实现一个哈希表 HashMap，只需要支持 put 和 get 两个基本操作。

小助手答案很牛啊

本期答案：

这道题没有一个统一的答案。哈希表常见的实现可以按照解决冲突的方式分为 Chaining 和 Open-addressing 两种。Chaining 实现将 Hash 到同一个桶的元素使用链表串联起来（也可以是其他更高效的方式），相应的，查找的时候需要查看桶中的所有元素。Open-addressing 译为开地址法，插入时一旦发现对应的桶已经被占用，则会根据某种特定方式继续寻找另一个桶，直到找到一个空的桶为止，相应地查找时也要做相同的操作。 下面给出一个 Chaining 的实现：

public class
 MyHashTableImpl<K, V> {

    private final Node<K, V>[] buckets;

    public MyHashTableImpl(int expectedSize) {
        this.buckets = new Node[expectedSize * 4];
    }

    public void put(K key, V value) {
        int h = key.hashCode() % buckets.length;
        Node<K, V> node = new Node<>(key, value);
        node.next = buckets[h];
        buckets[h] = node;
    }

    public V get(K key) {
        int h = key.hashCode() % buckets.length;
        Node<K, V> node = buckets[h];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    private static class Node<K, V> {
        final K key;
        final V value;
        Node<K, V> next = null;

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

并发情况下，如果直接使用上述代码， buckets 上会产生数据竞争，可能导致数据结构损害。为了防止这一点，我们可以通过分段加锁来保护（类似于 JDK7 的 ConcurrentHashMap 实现）。但是，对于上面的代码来说，由于少了 rehash 的负担，我们还可以利用 CAS 实现乐观锁。这也是 JDK8+ 的 ConcurrentHashMap 使用的方案。

public class MyLockFreeHashTableImpl<K, V> {

    private final AtomicReferenceArray<Node<K, V>> buckets;

    public MyLockFreeHashTableImpl(int expectedSize) {
        this.buckets = new AtomicReferenceArray<>(expectedSize * 4);
    }

    public void put(K key, V value) {
        int h = key.hashCode() % buckets.length();
        while (true) {
            Node<K, V> node = new Node<>(key, value);
            node.next = buckets.get(h);
            if (buckets.compareAndSet(h, node.next, node)) { // 如果失败，则重试
                return;
            }
        }
    }

    public V get(K key) {
        int h = key.hashCode() % buckets.length();
        Node<K, V> node = buckets.get(h);
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }
    
    static class Node<K, V> {  /* 略 */ }
}

上面的代码都是对于 Chaining 来说的，Open-addressing 也可以用类似的方式实现乐观锁，有兴趣的读者可以自己试试 ：） 最后一个问题，如果考虑 rehash，并发的实现就复杂了许多。我们依然有很多选项。最简单的一种实现，参考 JDK7 的分段加锁方案，我们可以为各个 Segment 独立加锁，这样即时某个 Segment 发生了 rehash 操作，也不会影响其他 Segment 的并发访问。多数情况下，这种实现已经能较好的满足要求。 JDK8 的 ConcurrentHashMap 实现更复杂，当需要 rehash 时，线程会逐个将 bin (bucket) 的数据复制到新的位置。此时若有其他线程并发写入时，它们也会参与到复制中来，共同协作完成哈希表的扩容。其中，每个 bin 的复制过程都通过加锁保证互斥。 而对于 Open-addressing 的哈希表，还有一些更为精妙的解决方案，有兴趣的读者可自行阅读相关论文，这里不再讨论。