java - 在恒定时间内删除 HashMap 内的 List 元素

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<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 ³)在最坏的情况下。

我是否可以在恒定时间内修改内部列表而不会出现异常，或者我是否需要重新考虑实现的整个结构？

如果是这样，我希望得到一些关于如何做到这一点的建议。

Answer 1

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