带有set（）方法的Java数据结构和O（1）包含（）

Does an ordered data structure exist in Java that can replace an item at a specific index and also has a contains method with O(1) time complexity?

Java中是否存在可以替换特定索引处的项的有序数据结构,并且还具有O(1)时间复杂度的contains方法?

LinkedHashSet is almost what I am looking for, but you cannot set/replace items at an index using them.

LinkedHashSet几乎就是我要找的东西,但你不能使用它们在索引处设置/替换项目。

2 个解决方案

#1

You can use store the items in a ArrayList and use a HashMap<ItemType, Integer> to map from the element type to the number of elements in equivalence classes in the List allowing access to the elements using the list and allowing you to test, if an item is contained by using

您可以使用存储ArrayList中的项目并使用HashMap 从元素类型映射到List中等价类中的元素数量,允许使用列表访问元素并允许您测试,如果使用包含项目 ,integer>

Integer i = map.get(object);
boolean contained = ( i != null ) && ( i > 0 );

Updating the map for adding an element:

更新地图以添加元素:

map.merge(object, 1, Integer::sum);

removing an element:

删除元素:

map.computeIfPresent(object, (k, v) -> v > 1 ? v - 1 : null);

If an item is replaced in the list, you can handle as

如果在列表中替换了某个项目,则可以处理为

map.merge(newValue, 1, Integer::sum);
map.computeIfPresent(oldValue, (k, v) -> v > 1 ? v - 1 : null);

#2

Not in the standard Java classes. You can make a class fairly easily that composes a HashSet and an ArrayList.

不在标准的Java类中。你可以很容易地创建一个组成HashSet和ArrayList的类。

#1

Integer i = map.get(object);
boolean contained = ( i != null ) && ( i > 0 );