java - 移除元素列表在恒定时间内在 HashMap 内部

Question

设法解决我的问题。我没有从列表中删除，而是创建了包含列表的类，这些类还包含一个索引，我每次都会递增而不是删除第一个元素。

我正在尝试实现稳定的婚姻算法。

我有一个men = HashMap<String, List<String>循环的地方men.keySet()

当满足某个条件时，我得到一个键，我应该使用该键删除列表的第一个元素：

int someCondition = listIWantToModify;
List<String> temp = men.get(listIWantToModify);
temp.remove(0);
men.replace(listIWantToModify, temp)

我想从 HashMap 中的一个列表中删除第一个元素。发生的事情是我得到java.util.ConcurrentModificationException的，我猜是因为我在同一个循环中从 List 中删除和获取项目。当我调用以下代码时：

List<String> replaceWithP = men.get(currentPartner);
replaceWithP.remove(0);
men.replace(currentPartner, replaceWithP);

我尝试执行以下操作：

List<String> replaceWithP = new ArrayList<>(men.get(currentPartner));
replaceWithP.remove(0);
men.replace(currentPartner, replaceWithP);

但是算法在最坏的情况下应该是 O(n ² )，我被告知当我创建新的 ArrayList 时它是 O(n) ，因此在最坏的情况下使我的算法为 O(n ³ )。

无论如何我可以在恒定时间内修改列表而不会出现异常，还是我需要重新考虑我的实现的整个结构？

如果是这样，我会喜欢一些关于如何做到这一点的建议。

标签： javaarraylisthashmapconcurrentmodification

Answer 1

在第一个示例中，您根本不需要 men.replace 行。您正在直接修改地图中的列表。无需再次放入相同的列表。