CODEWITHSUNDEEP
javacollectionsbig-o
Jimmy P
Jimmy P

Reputation: 1892

Java data structure with a set() method and O(1) Contains()

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?

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

Upvotes: 2

Views: 1462

Answers (2)

fabian
fabian

Reputation: 82491

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

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);

Upvotes: 1

Jeremy Gurr
Jeremy Gurr

Reputation: 1623

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

Upvotes: 1

Related Questions