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

Question

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.

For assignments i've also had to work with contains and such, but they were too high a cost. So i worked around the problem by simply creating a small interface, that had 2 methods. "Set if in solution", "Am i in the solution". in the class itself i've had to use a local variable for those. Not the most elegant, but hey it works. Also, contains on a sorted list could be gotten down to complexity log(n) because you can do binary search on it. Or even lower if you consider you can use a 2-3 tree. Sorted, low cost of checking an element, but no index replacements :/ — MrKickkiller, Dec 13 '16 at 23:41
you want to be able to use generic sort algorithms on it or do you strictly require the `List` interface? If not, then why not simply use a wrapper for bidirectional `HashMap` + `HashMap — , Dec 13 '16 at 23:52
I mean that you can create a wrapper for bidi int<->object hash-based mapping that implements `List` as its interface, transparently acting as a `List` by itself. That should do the trick here perfectly. You basically want all the pros that only a hash table can give you - by using a bidi map, you get an O(1) iteration and quasi-ordering stored as mapped indexes. Note that with a proper `List` implementation, you essentially get your `sort()` for free since you already have `get()`, `set()` etc. — , Dec 14 '16 at 00:35

score 1 · Answer 1 · edited Dec 13 '16 at 23:40

1

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

edited Dec 13 '16 at 23:40

answered Dec 13 '16 at 23:36

Jeremy Gurr

1,613
8
11

2

At twice the memory cost. – shmosel Dec 13 '16 at 23:37
1

True. But it's no worse than a LinkedHashSet in that regard. – Jeremy Gurr Dec 13 '16 at 23:38
1

@shmosel NOT at twice the memory cost. The extra cost will amortize over the size of the elements. If they're Integers then yes it will be relatively expensive. If they're 1000 bytes each the additional cost will be negligible. – Jim Garrison Dec 13 '16 at 23:40
2

@JimGarrison Of course. I'm referring to the collection size, not its contents. – shmosel Dec 13 '16 at 23:41

fabian · Accepted Answer · 2016-12-13T23:55:55.133

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

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

2 Answers2