Data structure with O(1) performance for get(int index) and ability to avoid duplication

Set is an obvious choice, if I do not want to have duplication on my list of data.

However, Set doesn't have get(int index) method : Why doesn't java.util.Set have get(int index)?

Several suggestions to implement a pseudo get(int index) and none of them are efficient.

  1. toArray and access the new array by index.
  2. Get the iterator, and use a for loop to access the indexed element by count.

Is there any advanced data structure, which enables me to

  1. Avoid duplication.
  2. Have O(1) performance for get(int index).
Jon Skeet
people
quotationmark

The simplest approach is to have a composite collection which contains a HashSet and an ArrayList. Your add operation would try to add it to the set, and only add it to the list if that has actually added a new item. The get operation would just get from the list.

Do you ever need to remove values? If not, that makes life simpler - otherwise, removing an item would be an O(N) operation. Not necessarily a problem, but something to bear in mind.

people

See more on this question at Stackoverflow