Java data structures: IndexedSet or HashList

Question

Is there a Java data structure that satisfies the following requirements?

Indexed access. (i.e., i should be able to retrieve objects with get(i))
Constant time get() & contains() methods
Should enforce ordering (enforced by Comparator)
Should be mutable

I could not find any in Oracle's JDK or Guava that gives the above listed features out of the box

List provides indexed access & some kind of ordering but not constant-time contains(). SortedSet and SortedMap provide constant-time contains() and sorting but not indexed access!!

Am I missing something or is there any data structure out there that could be manipulated to provide the features listed above?

My current solution:

A combination of HashMap & ArrayList => I use ArrayList to store the sorted keys which provides indexed access and use HashMap for constant-time contains() method. I just wanna make sure that I am not trying to re-invent something that has already been done

Why I need this:

Let's call this data structure SortedDataStore I am developing an Android app & most of the UI in that is a list of items and these items are pulled off the local db. (the local db gets its data from a remote server). The UI is populated using RecyclerView and I need constant-time indexed access to get the object from my SortedDataStore and populate the views. Since the order of items is decided based on their attributes, there is a need for sorting. Also the data gets updated a lot (items get modified, deleted and new items get added). When the new data comes in, I check against my SortedDataStore if it should be deleted, or added or modified (and moved to another index) for which I need constant-time contains() & mutability.

Any reason an [ArrayList](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html) does not work? — Appak, Mar 24 '15 at 17:59
You don't place any time requirements on insertion. What about wrapping an `ArrayList`, then calling `Collections.sort` after every insertion? — Andy Turner, Mar 24 '15 at 18:01
Use a combination of hashmap and List, though it is memory inefficient but will solve the purpose. use index as key map to get constant access time. — Satty, Mar 24 '15 at 18:02
@appak, @GriffeyDog - I forgot to put in conditions about `contains()`. Please have a look at the edited question — x-treme, Mar 24 '15 at 18:07
@Satty - That is exactly what I am using right now. I just wanted to make sure that I am not reinventing the wheel — x-treme, Mar 24 '15 at 18:08
This feels like premature optimization to me, especially since on a bellow answer you commented saying you will only have a few hundred to a few thousand elements. A sorted ArrayList and Collections.binarySearch() will work very well. If you are having performance problems in the view I would guess it is from something else. — Appak, Mar 24 '15 at 19:07
@Appak - Indeed it is a case of premature optimization it seems!! I will move to ArrayList — x-treme, Mar 24 '15 at 20:35

Louis Wasserman · Accepted Answer · 2015-03-24T20:37:51.783

4

Based on what you've described as your expected data size, ArrayList seems like it would actually be just fine in practice -- your data isn't big enough for the linear-time factor to matter that much.
Otherwise, what you're doing is the right solution; there's no provided mutable data structure that does all that at once.
If you can avoid mutation, Guava's ImmutableSet satisfies the rest of your demands. You can use ImmutableSet.asList().get(index) to get out elements by index in O(1) time, and otherwise it supports O(1) contains and insertion order.

edited Mar 24 '15 at 20:37

answered Mar 24 '15 at 18:16

Louis Wasserman

191,574
25
345
413

What kind of mutation? There's certainly no way to have `remove` be O(1) and support all your other constraints. – Louis Wasserman Mar 24 '15 at 18:21
addition and removal processes need not be O(1). It is just the retrieval and contains operations that have got to be O(1). – x-treme Mar 24 '15 at 18:26
Then what you're doing now is probably the right approach; there isn't any built-in way otherwise. – Louis Wasserman Mar 24 '15 at 18:28
(Though can you go into more detail about what exactly you need this structure? Are you sure you can't e.g. just populate it once and then leave it?) – Louis Wasserman Mar 24 '15 at 18:33
I have added the reasons for why i need such a data structure. Please have a look at the edit – x-treme Mar 24 '15 at 18:42
How big do you expect this data structure to get? How many elements? – Louis Wasserman Mar 24 '15 at 18:43
It ranges any where from a few hundred to few thousand elements – x-treme Mar 24 '15 at 18:44
3

I'd actually suspect you don't need constant time and that an `ArrayList` would suffice, but otherwise you've already got the right solution. – Louis Wasserman Mar 24 '15 at 18:45
(For a data structure that small, linear time isn't actually that big a price to pay.) – Louis Wasserman Mar 24 '15 at 19:17
Can you please edit your answer to reflect the comments? I would be happy to mark you answer as accepted – x-treme Mar 24 '15 at 20:31

score 2 · Answer 2 · answered Mar 24 '15 at 18:03

2

An ArrayList satisfies the three requirements:

Indexed access, using get(int i)
Constant time access, using get(int i)
Order by insertion, using add(Object o)

answered Mar 24 '15 at 18:03

Anderson Vieira

8,919
2
37
48

I forgot to put in conditions about `contains()`. Please have a look at the edited question – x-treme Mar 24 '15 at 18:07

score 2 · Answer 3 · answered Apr 30 '19 at 18:14

Java's LinkedHashMap satisfies your requirements if you use an index as your key.

Indexed access: use get(i)
Constant time get() & contains() methods: use get(i) and containsKey()
Should enforce ordering (enforced by Comparator): see note
Should be mutable: yes

Note

If you want a custom comparator, extend the Comparable interface and @Override the compareTo() method on the class of the child object.

comparator for LinkedHashMap

Java data structures: IndexedSet or HashList

3 Answers3