java - HashMap同步

Question

我的任务是同步 HashMap 的方法 put(K key, V value)。但它应该比 synchronized(this) 或 synchronized(table) 工作得更快。我写了这段代码:

public V put(K key, V value) {
    if (key == null) 
        return putForNullKey(value);

    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            synchronized(e) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

问题是，当我通过使用相同键的不同线程调用此方法时，可能会出现 map.entrySet().size() > 1 的情况。所以我的同步是错误的，但我不明白为什么。我怎样才能正确地做到这一点？

Answer 1

The problem is that when I call this method by different Threads using the same key, there can be situation, that map.entrySet().size() > 1. So my synchronization is wrong, but I don't understand why.

我不是 100% 确定我理解错误情况，但我发现您尝试同步时存在许多问题，这些问题会导致竞争条件。

例如，如果两个线程试图同时将相同的键添加到HashMap，它们将循环遍历桶而找不到条目。然后他们都将尝试将条目添加到表中。这可能会导致两个条目具有相同的键甚至损坏表。

我还假设 addEntry(...) 可以更改桶数组，这可能会导致所有元素的重新散列。因此，一个线程可能会导致存储桶发生变化，而另一个线程正在处理一个过时的数组。这可能会导致条目丢失或表格再次损坏。

How can I do this properly?

这是一个非常重要的练习。您可以做的一件事是使用 ReadWriteLock 这样至少您可以进行查找而不阻止写入。但是如果你正在向 map 中写入一个新条目，由于上面提到的 bucket 数组的更改，你可能必须对其进行独占锁定。