Java并发编程：使用Map的列表

Question

我有一个Java类，被很多线程同时访问，我想确保它是线程安全的。这个类有一个私有字段，它是一个字符串到字符串列表的映射。我已经将该映射实现为ConcurrentHashMap，以确保获取和放置操作是线程安全的：

public class ListStore {

  private Map<String, List<String>> innerListStore;

  public ListStore() {
    innerListStore = new ConcurrentHashMap<String, List<String>>();
  }
  ...
}

考虑到对Map的gets和puts是线程安全的，我的关注点在于存储在Map中的列表。例如，考虑以下方法，该方法检查给定列表中是否存在给定条目（为简洁起见，我省略了错误检查）：

public boolean listEntryExists(String listName, String listEntry) {

  List<String> listToSearch = innerListStore.get(listName);

  for (String entryName : listToSearch) {
    if(entryName.equals(listEntry)) {
      return true;
    }
  }

  return false;
}

似乎我需要同步此方法的整个内容，因为如果另一个方法在此方法迭代期间更改innerListStore.get(listName)列表的内容，则会抛出ConcurrentModificationException异常。 如果是这样，请问我应该在innerListStore上同步还是在本地变量listToSearch上同步呢？

更新：感谢您的回复。听起来我可以在列表本身上同步。有关更多信息，请参见add()方法，该方法可以同时在另一个线程中运行listEntryExists()方法。

public void add(String listName, String entryName) {

  List<String> addTo = innerListStore.get(listName);
  if (addTo == null) {
    addTo = Collections.synchronizedList(new ArrayList<String>());
    List<String> added = innerListStore.putIfAbsent(listName, addTo);
    if (added != null) {
      addTo = added;
    }
  }

  addTo.add(entryName);
}

如果这是唯一修改存储在地图中的基础列表的方法，并且没有公共方法返回对地图或地图中条目的引用，那么我可以在列表本身上同步迭代吗？这个add()的实现是否足够？

- Cameron

---

你的 add() 实现有问题。你需要正确处理 putIfAbsent() 的结果（否则可能会添加到错误的列表中）。 - jtahlborn

@jtahlborn 您的意思是我需要在 putIfAbsent() 返回的 List 上调用 add() 吗？如果是这样，我不同意。putIfAbsent() 返回与该键之前相关联的任何内容，这将是错误的列表。对吗？ - Cameron

请重新阅读有关putIfAbsent()方法的文档（注意该方法的名称）。 - jtahlborn

我现在明白你的意思了，并且已经编辑了 add() 函数。那么这样处理是正确的吗？ - Cameron

Answer 1

您可以在listToSearch上同步（“synchronized(listToSearch) {...}”）。确保创建列表时没有竞态条件（使用innerListStore.putIfAbsent来创建它们）。

- Spike Gronim

Answer 2

你可以只在listToSearch上进行同步，没有理由在任何人仅使用一个条目时锁定整个映射。

但请记住，在修改列表的任何地方都需要同步！同步迭代器并不能自动阻止其他人执行add()或其他操作，如果你向他们传递了对未同步列表的引用。

最安全的方法是在Map中存储同步列表，然后在迭代时锁定它们，并在返回列表引用时记录用户必须在迭代时同步。当没有实际争用时，现代JVM中的同步非常便宜。当然，如果你从不让列表之一的引用逃逸出你的类，你可以使用更细致的方式来处理它。

或者，你可以使用像CopyOnWriteArrayList这样的线程安全列表，它使用快照迭代器。你需要什么样的时间点一致性是一个我们无法为你做出的设计决策。javadoc还包括有关性能特征的有用讨论。

- Affe

---

+1 提醒 listEntryExists 中的迭代器同步不会阻塞其他方法中的修改。 - CPerkins

抱歉Affe，那是我在反对同步的一般性战争中犯了错。今天重新阅读答案后，它是完全合理的，不应该被贬低。你说得对，无争用的同步是便宜的，但有争用的同步则不然。锁定解决方案的问题在于随着列表变得越来越大，关键部分也会变得越来越大，争用的可能性也会增加。然而，你通过建议使用写时复制结构来避免这个问题。很抱歉，但SE现在不让我取消投票。 - Jed Wesley-Smith

没关系，我只是想问一下，因为如果我说错了什么，我想学习一下 :) - Affe

Answer 3

似乎我需要同步此方法的整个内容，因为如果另一个方法在此方法迭代时更改了innerListStore.get(listName)列表的内容，则会抛出ConcurrentModificationException异常。

其他线程是否访问列表本身，还是只通过ListStore公开的操作访问？

其他线程调用的操作是否会导致Map中存储的List的内容发生更改？还是只会从Map中添加/删除条目？

只有当不同的线程可以导致对相同的List实例进行更改时，才需要同步访问存储在Map中的List。如果只允许线程向Map中添加/删除List实例（即更改Map的结构），则不需要同步。

- matt b

Answer 4

由于除了boolean listEntryExists(String listName, String listEntry)方法之外，您没有提供任何用于地图列表的客户端，我想知道为什么您要存储列表？这个结构似乎更自然是一个Map<String, Set<String>>，而listEntryExists应该使用contains方法（也可在List上使用，但O(n)到列表大小）：

public boolean listEntryExists(String name, String entry) {
  SetString> set = map.get(name);
  return (set == null) ? false : set.contains(entry;
}

现在，contains调用可以封装任何您想要的内部并发协议。

对于add，您可以使用同步包装器（简单但可能较慢），或者如果写入相对于读取不频繁，则利用ConcurrentMap.replace来实现自己的写时复制策略。例如，使用Guava ImmutableSet：

public boolean add(String name, String entry) {
  while(true) {
    SetString> set = map.get(name);
    if (set == null) {
      if (map.putIfAbsent(name, ImmutableSet.of(entry))
        return true
      continue;
    }
    if (set.contains(entry)
      return false; // no need to change, already exists
    Set<String> newSet = ImmutableSet.copyOf(Iterables.concat(set, ImmutableSet.of(entry))        
    if (map.replace(name, set, newSet)
      return true;
  }
}

现在这是一个完全线程安全的无锁结构，其中并发读写者不会相互阻塞（除了底层ConcurrentMap实现的无锁性）。这个实现在写入时具有O(n)的复杂度，而你原来的实现在读取时具有O(9n)的复杂度。如果你主要进行读取而不是写入，那么这可能是一个巨大的优势。

- Jed Wesley-Smith

Answer 5

如果Map已经是线程安全的，那么我认为同步listToSearch应该可以工作。虽然我不是100%确定，但我认为它应该可以工作。

synchronized(listToSearch)
{

}

- RMT

Answer 6

如果存储在映射中的列表属于不会抛出CME（例如CopyOnWriteArrayList）的类型，则可以随意迭代。

但是，如果不小心，这可能会引入一些竞争。

- ratchet freak

Answer 7

你可以使用Guava中的另一个抽象。

请注意，这将在整个映射上进行同步，因此对你可能没有那么有用。

- whiskeysierra

Answer 8

可以用更少的代码完成。 这是一个例子，它是并发压力测试Jcstress的一部分 在此输入链接描述

void add(String key, String val) {
     List<String> list = map.computeIfAbsent(key,
                    k -> Collections.synchronizedList(new ArrayList<>()));
     list.add(val);
}

- wromma