How to get nth element of a Set

Question

More specifically: how to get the nth element of a LinkedHashSet (which has a predictable iteration order)? I want to retrieve the nth element inserted into this Set (which wasn't already present).

Is it better to use a List:

List<T> list = new ArrayList<T>(mySet);
T value = list.get(x); // x < mySet.size()

or the toArray(T [] a) method:

T [] array = mySet.toArray(new T[mySet.size()]);
T value = array[y]; // y < mySet.size()

Other than the (likely slight) performance differences, anything to watch out for? Any clear winner?

Edit 1

NB: It doesn't matter why I want the last-inserted element, all that matters is that I want it. LinkedHashSet was specifically chosen because it "defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set."

Edit 2

This question seems to have devolved into a discussion of whether any Set implementation can ever preserve original insertion order. So I put up some simple test code at http://pastebin.com/KZJ3ETx9 to show that yes, LinkedHashSet does indeed preserve insertion order (the same as its iteration order) as its Javadoc claims.

Edit 3

Modified the description of the problem so that everybody isn't too focused on retrieving the last element of the Set (I originally thought that the title of the question would be enough of a hint — obviously I was wrong).

Solution 1

So I decided to go with a slight variation of the answer by @Juvanis.

To get at the nth element in a LinkedHashSet:

Iterator<T> itr = mySet.iterator();
int nth = y;
T value = null;

for(int i = 0; itr.hasNext(); i++) {
    value = itr.next();
    if (i == nth) {
        break;
    }
}

Version 2 of the code:

public class SetUtil {

    @Nullable
    public static <T> T nthElement(Set<T> set, int n) {
        if (null != set && n >= 0 && n < set.size()) {
            int count = 0;
            for (T element : set) {
                if (n == count)
                    return element;
                count++;
            }
        }
        return null;
    }
}

NB: with some slight modifications the method above can be used for all Iterables<T>.

This avoids the overhead of ensuring that a Set and a List stay in sync, and also avoids having to create a new List every time (which will be more time-consuming than any amount of algorithmic complexity).

Obviously I am using a Set to ensure uniqueness and I'd rather avoid a lengthy explanation as to why I need indexed access.

Solution 2

This method is based on the updated requirement to return the nth element, rather than just the last element. If the source is e.g. a Set with identifier mySet, the last element can be selected by nthElement(mySet, mySet.size()-1).

If n is small compared to the size of the Set, this method may be faster than e.g. converting to an ArrayList.

  /**
   * Return an element selected by position in iteration order.
   * @param data The source from which an element is to be selected
   * @param n The index of the required element. If it is not in the 
   * range of elements of the iterable, the method returns null.
   * @return The selected element.
   */
  public static final <T> T nthElement(Iterable<T> data, int n){
    int index = 0;
    for(T element : data){
      if(index == n){
        return element;
      }
      index++;
    }
    return null;
  }

Solution 3

I'd use the iterator of the LinkedHashSet if you want to retrieve the last element:

Iterator<T> it = linkedHashSet.iterator();
T value = null;

while (it.hasNext()) {
    value = it.next();
}

After the loop execution value will be referring to the last element.

Solution 4

You can go with below solution, here i have added object of ModelClass in HashSet.

ModelClass m1 = null;
int nth=scanner.nextInt();
for(int index=0;index<hashset1.size();index++){
    m1 = (ModelClass) itr.next();
    if(nth == index) {
        System.out.println(m1);
        break;
    }
}

View more solutions

Comments

[Nir Alfasi]

You're not answering the question! he didn't ask "how to do it" he asked which way is more efficient

[Juvanis]

@alfasin by answering with my own solution, i'm implicitly claiming this way is more efficient.

[markvgti]

From the javadoc for LinkedHashSet: "defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set." There's a reason I am specifically using a LinkedHashSet.

[bsd]

Where did the T come from ? And naming conventions ? Where is the compareTo, equals, hashCode methods ? Is extending a Set a right thing to do ?

[Nir Alfasi]

It's more efficient than what ? it's actually not more efficient than either of the options he provided both are O(n), and so is your solution.

[awksp]

This technically won't even compile because Set is an interface. The idea is right though.

[awksp]

And considering this is a Set, you only "insert" x once. If you try to add a duplicate element it will fail to add, period. That is the definition of a Set. Doesn't matter what "the user's point of view" is. Attempting to put something into a regular HashSet multiple times will only end up inserting it once too. There's a reason there's a return value on the add() method.

[Henry]

@alfasin it has the same asymptotic behaviour but it has a smaller constant factor than the other solutions, so clearly it is more efficient.

[Nir Alfasi]

on the contrary, the constant factor of this solution is O(n) as well while in the other solutions it's O(1)...

[markvgti]

@HelpVampire666 This idea doesn't work if I want the 5th element or the 11th. The two methods I asked about work in all cases. I am simply asking which one is better (and why).

[Erwin Bolwidt]

Both alternatives that the OP provides also iterate over all the elements of the set. The ArrayList constructor internally invokes toArray() and both toArray() and toArray(Object[]) (implemented in AbstractCollection and not overridden) internally iterate over all the elements of the set. So this answer describes a way to do the same without the overhead of creating temporary arrays and ArrayList objects. So it's a least as fast (if HotSpot can eliminate the temporaries) or faster than both of the OP's suggestions.

[Nir Alfasi]

@ErwinBolwidt as I wrote on my second comment - all the solutions provided on this page are O(n). If you claim that one of them is faster you should prove your claim by benchmarking the three...

[Erwin Bolwidt]

No you don't. Please read my comment. Since the two methods suggested by the OP do exactly what @Juvanis does, plus more (allocate object and array) then you can prove that Juvanis solution does less work, which is a good definition of "more efficient".Btw you brought in the big-O notation, the OP never mentioned it.