0

What java data structure is an ordered collection, provides the functionality constant time contains method of HashSet, and provides constant time lookup by index much like the get method of ArrayList? Does the Java API contain such a thing? I considered using TreeSet, but according to the Java Docs those operations are O(log n).

Improve this question
4
  • A LinekdHashSet perhaps? Commented Mar 21, 2016 at 20:28
  • Do you need constant-time insertion? If so, this isn't going to work, since a data structure like that would let you do a comparison sort in O(n) time. Commented Mar 21, 2016 at 20:28
  • 2
    When you say "ordered", do you mean sorted order, or do you mean some other order, like insertion order? Commented Mar 21, 2016 at 20:31
  • you won't find such collection in JDK. None of ordered or hash-based collections have access by index. You can write your own, but I doubt that O(1) random access for some sorted structure can be gained unless insertion is O(N) Commented Mar 21, 2016 at 20:42

2 Answers 2

Reset to default
1

The Java standard library does not offer such a class, but you could implement your own without too much trouble. It would be more or less the dual of LinkedHashSet: a List (maybe wrapping ArrayList) that maintains an internal HashSet for constant-time contains() processing.

The Collections API has classes intended to make it easy to implement collection classes; in this case I would look at implementing a concrete subclass of AbstractList.

Update: On the other hand, if your idea is that the instances automatically maintain their elements in order, and/or that they disallow duplicate elements, then what you're talking about is not a List at all. In that case you would want to consider implementing a concrete subclass of AbstractSet that adds indexed retrieval methods. You could still wrap a HashSet and an ArrayList, but you would need to expend some effort to keep the list ordered on element insertion.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Use LinkedHashSet. It is Hash table and linked list implementation of the Set interface, with predictable iteration order.

You will see up to O(n) complexity for insertion or checking the existence of an item in the hash set. However most times you don't see collisions and so in most cases it will be O(1).

Improve this answer

4 Comments

Does LinkedHashSet support indexing?
Set interface does not have any direct methods such as indexOf() or get(). You need to parse the whole collection in order to search for a element. indexOf() and get() internally do the same only.
The OP requests constant-time element retrieval by index. Although LinkedHashSet offers constant-time retrieval, it is only by key, not index.
@JohnBollinger thanks for setting us straight with our answers.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.