英文:
Remove elements List<String> inside of a HashMap in constant time
问题
成功解决了我的问题。我不是从列表中移除元素，而是创建了包含列表的类，这些类还包含一个索引，我每次递增该索引，而不是移除第一个元素。
我正在尝试实现稳定婚姻算法。
我有一个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^2)，有人告诉我，当我创建新的ArrayList时，它是O(n)，从而使得我的算法在最坏的情况下变为O(n^3)。
有没有办法在常数时间内修改列表，而不会出现异常？还是我需要重新思考整个实现结构？
如果需要重新思考，我希望能得到一些建议。
英文:
Manged to solve my problem. Instead of removing from the List I created classes containing the lists, the classes also contained an index which I incremented each time instead of removing the first element.
I'm trying to implement the Stable marriage algorithm.
I have a men = HashMap<String, List<String> where I loop over men.keySet()
When a certain condition is met I get a key, and I'm supposed to remove the first element of the list with that key:
int someCondition = listIWantToModify;
List<String> temp = men.get(listIWantToModify);
temp.remove(0);
men.replace(listIWantToModify, temp)
I want to remove the first element from the one of the lists inside the HashMap. What happens is that I get java.util.ConcurrentModificationException which I guess comes from the fact that I both remove and get items from the List<String> in the same loop. When I call the following code:
List<String> replaceWithP = men.get(currentPartner);
replaceWithP.remove(0);
men.replace(currentPartner, replaceWithP);
I tried to do the following:
List<String> replaceWithP = new ArrayList<>(men.get(currentPartner));
replaceWithP.remove(0);
men.replace(currentPartner, replaceWithP);
But the algorithm is supposed to be O(n<sup>2</sup>) in the worst case and I was told that when I create the new ArrayList it is O(n) thus making my algorithm O(n<sup>3</sup>) in the worst case.
Is there anyway I can modify the list inside in constant time without getting the exception or do I need to rethink the whole structure of my implementation?
If so I'd love some suggestions on how to do that.
答案1
得分: 0
你在第一个示例中根本不需要 men.replace 这一行。你直接修改的是映射中的列表。不需要再次放入相同的列表。
英文:
You don't need the men.replace line at all in the first example. You're directly modifying the list that's in the map. No need to put the same list in again.
答案2
得分: 0
第一个项目无法在常数时间内从ArrayList中移除。最后一个可以。该操作会在常数时间内从地图中移除一个条目：
List<String> temp = men.get(currentPartner);
temp.remove(temp.size() - 1);
如果您需要删除第一个项目，您应该使用不同的数据结构，例如ArrayDeque。
英文:
The first item of an ArrayList cannot be removed in constant time. The last one can be. This operation removes an entry from the map in constant time:
List<String> temp = men.get(currentPartner);
temp.remove(temp.size()-1);
If you need to remove the first item, you should use a different data structure, such as ArrayDeque.
专注分享java语言的经验与见解，让所有开发者获益！
评论