HashMap和ArrayList在迭代/循环时添加元素

Question

我有一个游戏，每X秒钟它会将内存中的更改值写回到我的数据库。这些值在编辑它们所包含的数据时存储在容器中（HashMap和ArrayList）。

为了简单起见，让我们假设我只有一个容器要写入数据库：

public static HashMap<String, String> dbEntitiesDeletesBacklog = new HashMap<String, String>();

我的数据库写入循环：

Timer dbUpdateJob = new Timer();
dbUpdateJob.schedule(new TimerTask() {
    public void run() {
        long startTime = System.nanoTime();
        boolean updateEntitiesTableSuccess = UpdateEntitiesTable();
        if (!updateEntitiesTableSuccess){
            try {
                conn.rollback();
            } catch (SQLException e) {
                e.printStackTrace();
                logger.fatal(e.getMessage());
                System.exit(1);
            }
        } else { //everything saved to DB - commit time
            try {
                conn.commit();
            } catch (SQLException e) {
                e.printStackTrace();
                logger.fatal(e.getMessage());
                System.exit(1);
            }
        }
        logger.debug("Time to save to DB: " + (System.nanoTime() - startTime) / 1000000 + " milliseconds");
    }
}, 0, 10000); //TODO:: figure out the perfect saving delay

我的更新方法：

private boolean UpdateEntitiesTable() {
    Iterator<Entry<String, String>> it = dbEntitiesDeletesBacklog.entrySet().iterator();
    while (it.hasNext()) {
        Entry<String, String> pairs = it.next();
        String tmpEntityId = pairs.getKey();

        int deletedSuccess = UPDATE("DELETE" + 
                " FROM " + DB_NAME + ".entities" + 
                " WHERE entity_id=(?)", new String[]{tmpEntityId});
        if (deletedSuccess != 1) {
            logger.error("Entity " + tmpEntityId + " was unable to be deleted.");
            return false;
        }
        it.remove();
        dbEntitiesDeletesBacklog.remove(tmpEntityId);
    }

“在‘保存到数据库’时，我需要为dbEntitiesDeletesBacklog HashMap和其他未在此节选中的容器创建某种锁定机制吗？我认为我需要这样做，因为它创建了迭代器，然后循环。如果在创建迭代器之后，在循环遍历条目之前添加了一些内容，会怎样呢？对于我的其他容器，我使用相同的方式，请问是否也需要这样做？抱歉，这更多是一个流程问题而不是代码帮助问题（因为我包含了如此多的示例代码），但我想确保易于理解我正在尝试做什么并且询问什么。”

public static ArrayList<String> dbCharacterDeletesBacklog =  new ArrayList<String>();

private boolean DeleteCharactersFromDB() {
    for (String deleteWho : dbCharacterDeletesBacklog){
        int deleteSuccess = MyDBSyncher.UPDATE("DELETE FROM " + DB_NAME + ".characters" +
                " WHERE name=(?)", 
                new String[]{deleteWho});

        if (deleteSuccess != 1) {
            logger.error("Character(deleteSuccess): " + deleteSuccess);
            return false;
        }
    }
    dbCharacterDeletesBacklog.clear();
    return true;
}

非常感谢您一如既往的帮助。我们非常感激！

- KisnardOnline

---

听起来你所需要做的就是同步访问你的HashMap和ArrayList的方法。 - Joel

你有多个线程吗？ - Tarik

是的，我本来想说阻塞对我来说是不可接受的。游戏需要运行流畅，数据库更新是次要的。我认为最好的方法是锁定(dbCharacterDeletesBacklog)并复制(dbCharacterDeletesBacklog)到目标(dbCharacterDeletesBacklog_copy)，然后清除(dbCharacterDeletesBacklog)。 - KisnardOnline

@JayAvon：对于集合的简单同步肯定可以起作用，如果您预计应用程序中运行的所有线程对集合的争用很少，那么这可能是一个好的可行解决方案。如果您认为可能存在高争用期，则很可能发现使用ConcurrentHashMap会更具性能。唯一的方法是在实际条件下运行您的应用程序...并对其进行分析。 - scottb

Answer 1

至少，在并发访问地图时，您需要一个同步的地图（通过Collections.synchronizedMap），否则您可能会遇到非确定性行为。

除此之外，如您所建议的，您还需要在迭代期间锁定地图。从Collections.synchronizedMap（）的javadoc中建议：

当迭代其任何集合视图时，用户必须手动同步返回的地图：

Map m = Collections.synchronizedMap(new HashMap());
      ...
Set s = m.keySet();  // Needn't be in synchronized block
      ...
synchronized(m) {  // Synchronizing on m, not s!
    Iterator i = s.iterator(); // Must be in synchronized block
    while (i.hasNext())
        foo(i.next());
}

不遵循此建议可能导致非确定性行为。

或者，使用ConcurrentHashMap代替常规的HashMap，在迭代期间避免需要同步。对于游戏而言，这可能是更好的选择，因为您可以避免长时间锁定集合。

甚至更好的方法是考虑通过轮换新集合来避免在数据库写入时锁定集合。每次更新数据库时，都会获取集合并将其替换为新的空集合，所有新的更新都会被写入其中，从而避免锁定集合。在这种情况下，集合将由某个容器管理，以使该抓取和替换是线程安全的。<<<注意：在这种情况下，您不能向修改代码公开基础集合，因为您需要严格保持其引用私有，以使交换有效（并且不会引入任何竞争条件）。

- Trevor Freeman

---

@JayAvon 最近我在思考这个问题，我认为你应该采用清除解决方案或使用ConcurrentHashmap并在迭代时删除条目。正确的旋转解决方案实际上需要复制“SynchronizedMap”并添加自己的方法来替换和返回底层映射。当考虑返回的迭代器时，它是非平凡的。任何使用映射的其他替换解决方案都可能存在微妙的竞争条件，因为您需要在与交换方法使用的相同互斥体上同步对底层映射的任何访问。 - Trevor Freeman

如果我使用ConcurrentHashmap，那么我只需要将其保持不变，它就会根据需要从迭代器中添加/删除任何内容？这是否意味着它会在数据库保存期间添加到迭代器中，还是排队等待下一次保存？ - KisnardOnline

@JayAvon 是的，您可以从迭代器中删除。在数据库保存期间，可能会对迭代器进行并发修改，也可能不会，这是不确定的（因此它们可能会排队等待下一次或添加到当前迭代中）。但是，只要在向数据库写入条目后在迭代器上调用remove，您就不会丢失任何条目（因此，无论并发项是添加到当前迭代还是排队等待下一次都没有关系）。 - Trevor Freeman

太好了。非常感谢你... 感激不尽。想帮我编写游戏吗？:D - KisnardOnline

@JayAvon 感谢您的提议，但很遗憾我没有时间（有孩子会这样做！）。 - Trevor Freeman

Answer 2

以下是我将要使用的示例。我在这里发布希望能帮助其他遇到类似问题的人。

public class MyDBSyncher {

    public static boolean running = false;
    public static HashMap<String, String> dbEntitiesInsertsBacklog_A = new HashMap<String, String>();
    public static HashMap<String, String> dbEntitiesInsertsBacklog_B = new HashMap<String, String>();

    public MyDBSyncher(){
        Timer dbUpdateJob = new Timer();
        dbUpdateJob.schedule(new TimerTask() {
            public void run() {
                running = true;
                boolean updateEntitiesTableSuccess = UpdateEntitiesTable();
                running = false;
            }
        }, 0, 10000); //TODO:: figure out the perfect saving delay
    }

    public HashMap getInsertableEntitiesHashMap(){
        if (running){
            return dbEntitiesInsertsBacklog_B;
        } else {
            return dbEntitiesInsertsBacklog_A;
        }
    }

    private boolean UpdateEntitiesTable() {
        Iterator<Entry<String, String>> it2 = getInsertableEntitiesHashMap().entrySet().iterator();
        while (it2.hasNext()) {
            Entry<String, String> pairs = it2.next();
            String tmpEntityId = pairs.getKey();

            //some DB updates here

            it2.remove();
            getInsertableEntitiesHashMap().remove(tmpEntityId);
        }
        return true;
    }
}

- KisnardOnline

---

如果它能正常工作，那就很好。问题在于由竞态条件或其他（非确定性）并发问题引起的错误可能很难引发，并且可能只会在以后出现，特别是如果您的应用程序转换为具有更多资源争用的更高并发负载。有一件事情确实让我困扰，那就是running变量。在这个解决方案中，Java内存模型根本不保证对该变量的更新将对其他线程可见，除非进行同步访问。如果您的需求很简单，volatile声明也可能足够。 - scottb

如果我理解代码正确的话，那么我认为它可能存在一些问题。主要是当这个类正在迭代时，并发访问将向您的 _A 映射中添加项目，而该映射永远不会被迭代。其次，正如 scottb 所说，您需要确保至少同步运行变量（volatile 应该足够）。 - Trevor Freeman

是的，你说得对。我一开始也想过迭代并在B完成向数据库写入后将A复制到B，但这样又要再次锁定...真是太烦人了，我会继续思考的。这个游戏是一个我已经开发了两年多的MMORPG。这是我最大的担忧，当用户同时在线时，我可能会遇到很多并发问题。 - KisnardOnline

@JayAvon：如果你想编写一个你预计会成为（或希望成长为）高度并发系统的系统，那么你确实需要阅读Brian Goetz和其他Java开发名人所著的《Java并发编程实践》。Joshua Bloch是其中的一位贡献者，书中的一些章节让人感到非常熟悉。这本书是Java并发编程的许多最佳实践的不可或缺的概括（双关语）。阅读它的投资将会带来巨大的回报。 - scottb