How to obtain index of a given LinkedHashSet element without iteration?

Question

Is it even possible?

Say you have

private Set<String> names = new LinkedHashSet<String>();

and Strings are "Mike", "John", "Karen".

Is it possible to get "1" in return to "what's the index of "John" without iteration?

The following works fine .. with this question i wonder if there is a better way

for (String s : names) {
 ++i;
 if (s.equals(someRandomInputString)) {
 break;
 }
}

• Mat: Sets generally don't have an internal order, so the "index" of an element doesn't really make sense - it might make sense for set implementations, but not in the general case.
• James Raitsev: Is there a particular Set implementation that allows for this?
• Omnaest: @Mat LinkedHashSet is ordered, it does more than his Set contract requires it to do, so the question is quite reasonable
• toto2: Is there a reason you are stuck with a Set? If you need to work with indices, clearly you should use a List.
• kap: I find it quite weird that it is not possible. LinkedHashSet even explicitly states that the elements are stored in a linked list, why is there no method to get the index?

Answer 1

The Set interface doesn't have something like as an indexOf() method. You'd really need to iterate over it or to use the List interface instead which offers an indexOf() method.

If you would like to, converting Set to List is pretty trivial, it should be a matter of passing the Set through the constructor of the List implementation. E.g.

List<String> nameList = new ArrayList<String>(nameSet);
// ...

• BalusC: But.. If you're using Set from the beginning on for the purpose for which a List is unsuitable, then I'd rather just loop over it (and if necessary create some utility method for that). Why exactly are you using a Set while you'd like to know about the index? Just to have the items in an order? You might want to just use List from the beginning on and use Collections#sort() beforehand.
• mjs: Terrible answer. I have to create a new arraylist to do this? Imagine you do this all the time. There are no good answers to this question on SO, so I have to write my own.
• BalusC: @momo: Answers to terrible functional requirements are indeed usually terrible. Just use List instead of Set in first place.
• mjs: A list and set also yield different results. Maybe a user needs a to avoid duplicates in an efficient manner, why linked hashet is used, yet want to be able to present someone with list of available items, and have them select only one. I have posted my answer below. It uses an arraylist as a backup instead, allowing for o(1) get(index)

Answer 2

Here is an implementation that does insertions, removals, retainings, backed by an arraylist to achieve o(1) on get(index).

/**
 * @Author Mo. Joseph
 *
 * Allows you to call get with o(1) instead of o(n) to get an instance by index
 */
public static final class $IndexLinkedHashSet<E> extends LinkedHashSet<E> {
 private final ArrayList<E> list = new ArrayList<>();
 public $IndexLinkedHashSet(int initialCapacity, float loadFactor) {
 super(initialCapacity, loadFactor);
 }
 public $IndexLinkedHashSet() {
 super();
 }
 public $IndexLinkedHashSet(int initialCapacity) {
 super(initialCapacity);
 }
 public $IndexLinkedHashSet(Collection<? extends E> c) {
 super(c);
 }
 @Override
 public synchronized boolean add(E e) {
 if ( super.add(e) ) {
 return list.add(e);
 }
 return false;
 }
 @Override
 public synchronized boolean remove(Object o) {
 if ( super.remove(o) ) {
 return list.remove(o);
 }
 return false;
 }
 @Override
 public synchronized void clear() {
 super.clear();
 list.clear();
 }
 public synchronized E get(int index) {
 return list.get(index);
 }
 @Override
 public synchronized boolean removeAll(Collection<?> c) {
 if ( super.removeAll(c) ) {
 return list.removeAll(c);
 }
 return true;
 }
 @Override
 public synchronized boolean retainAll(Collection<?> c) {
 if ( super.retainAll(c) ) {
 return list.retainAll(c);
 }
 return false;
 }
 /**
 * Copied from super class
 */
 @Override
 public synchronized boolean addAll(Collection<? extends E> c) {
 boolean modified = false;
 for (E e : c)
 if (add(e))
 modified = true;
 return modified;
 }
}

To test it:

public static void main(String[] args) {
 $IndexLinkedHashSet<String> abc = new $IndexLinkedHashSet<String>();
 abc.add("8");
 abc.add("8");
 abc.add("8");
 abc.add("2");
 abc.add("3");
 abc.add("4");
 abc.add("1");
 abc.add("5");
 abc.add("8");
 System.out.println("Size: " + abc.size());
 int i = 0;
 while ( i < abc.size()) {
 System.out.println( abc.get(i) );
 i++;
 }
 abc.remove("8");
 abc.remove("5");
 System.out.println("Size: " + abc.size());
 i = 0;
 while ( i < abc.size()) {
 System.out.println( abc.get(i) );
 i++;
 }
 abc.clear();
 System.out.println("Size: " + abc.size());
 i = 0;
 while ( i < abc.size()) {
 System.out.println( abc.get(i) );
 i++;
 }
}

Which outputs:

Size: 6
8
2
3
4
1
5
Size: 4
2
3
4
1
Size: 0

Ofcourse remove, removeAll, retainAll now has the same or worse performance as ArrayList. But I do not use them and so I am ok with that.

Enjoy!

EDIT:

Here is another implementation, which does not extend LinkedHashSet because that's redundant. Instead it uses a HashSet and an ArrayList.

/**
 * @Author Mo. Joseph
 *
 * Allows you to call get with o(1) instead of o(n) to get an instance by index
 */
public static final class $IndexLinkedHashSet<E> implements Set<E> {
 private final ArrayList<E> list = new ArrayList<>( );
 private final HashSet<E> set = new HashSet<> ( );
 public synchronized boolean add(E e) {
 if ( set.add(e) ) {
 return list.add(e);
 }
 return false;
 }
 public synchronized boolean remove(Object o) {
 if ( set.remove(o) ) {
 return list.remove(o);
 }
 return false;
 }
 @Override
 public boolean containsAll(Collection<?> c) {
 return set.containsAll(c);
 }
 public synchronized void clear() {
 set.clear();
 list.clear();
 }
 public synchronized E get(int index) {
 return list.get(index);
 }
 public synchronized boolean removeAll(Collection<?> c) {
 if ( set.removeAll(c) ) {
 return list.removeAll(c);
 }
 return true;
 }
 public synchronized boolean retainAll(Collection<?> c) {
 if ( set.retainAll(c) ) {
 return list.retainAll(c);
 }
 return false;
 }
 public synchronized boolean addAll(Collection<? extends E> c) {
 boolean modified = false;
 for (E e : c)
 if (add(e))
 modified = true;
 return modified;
 }
 @Override
 public synchronized int size() {
 return set.size();
 }
 @Override
 public synchronized boolean isEmpty() {
 return set.isEmpty();
 }
 @Override
 public synchronized boolean contains(Object o) {
 return set.contains(o);
 }
 @Override
 public synchronized Iterator<E> iterator() {
 return list.iterator();
 }
 @Override
 public synchronized Object[] toArray() {
 return list.toArray();
 }
 @Override
 public synchronized <T> T[] toArray(T[] a) {
 return list.toArray(a);
 }
}

Now you have two implementations, I would prefer the second one.

• Matej Snoha: Just noting that calling remove() on the Iterator will break things in both implementations. If you do not wish to implement the removal, just return Collections.unmodifiableList(list).iterator(); which throws UnsupportedOperationException on Iterator remove() and is fast (doesn't copy list data).
• mjs: @MatejSnoha Perhaps, maybe one needs to provide a custom iterator as well. Maybe that can come up someday, but don't have the need right now.
• Arturo Torres Sánchez: Maybe I'm confused, but I don't see an indexOf method in your implementations, which is what the question is asking.

Answer 3

I don't believe so, but you could create a LinkedHashSetWithIndex wrapper class that would do the iteration for you, or keep a separate table with the indexes of each entry, if the performance decrease is acceptable for your use case.

• James Raitsev: Nice and elegant suggestion. Thank you

Answer 4

It is generally not possible for a Set to return the index because it's not necessarily well defined for the particular Set implementation. For example it says in the HashSet documentation

It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.

So you shouldn't say the type is Set when what you actually expect is a Set implementing som order.

• ReyCharles: Wow people are fast at responding! This is my second post ever on stackoverflow so excuse me if I did something wrong :) I see Mat posted basically the same a few minutes before me.
• ReyCharles: @Aaron V.: A LinkedHashSet does keep an ordering "This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order)."

Answer 5

Although not as efficient for the machine, this achieves it in one line:

int index = new ArrayList<String>(names).indexOf("John");

• mjs: No good, new arraylist just to do this. It's cheaper to iterate the set.
• Bohemian: @mmm this is cheaper for the programmer and the eyes - being just one short line.

Answer 6

I modified the mjs's solution to accommodate indexOf()

Implementation 1:

/**
 * @Author Mo. Joseph
 *
 * Allows you to call get with o(1) instead of o(n) to get an instance by index
 */
public static final class $IndexLinkedHashSet<E> extends LinkedHashSet<E> {
 private final ArrayList<E> list = new ArrayList<>();
 public $IndexLinkedHashSet(int initialCapacity, float loadFactor) {
 super(initialCapacity, loadFactor);
 }
 public $IndexLinkedHashSet() {
 super();
 }
 public $IndexLinkedHashSet(int initialCapacity) {
 super(initialCapacity);
 }
 public $IndexLinkedHashSet(Collection<? extends E> c) {
 super(c);
 }
 @Override
 public synchronized boolean add(E e) {
 if ( super.add(e) ) {
 return list.add(e);
 }
 return false;
 }
 @Override
 public synchronized boolean remove(Object o) {
 if ( super.remove(o) ) {
 return list.remove(o);
 }
 return false;
 }
 @Override
 public synchronized void clear() {
 super.clear();
 list.clear();
 }
 public synchronized E get(int index) {
 return list.get(index);
 }
 
 
 // Added this function
 public synchronized int indexOf(E element) {
 return list.indexOf(element);
 }
 //
 @Override
 public synchronized boolean removeAll(Collection<?> c) {
 if ( super.removeAll(c) ) {
 return list.removeAll(c);
 }
 return true;
 }
 @Override
 public synchronized boolean retainAll(Collection<?> c) {
 if ( super.retainAll(c) ) {
 return list.retainAll(c);
 }
 return false;
 }
 /**
 * Copied from super class
 */
 @Override
 public synchronized boolean addAll(Collection<? extends E> c) {
 boolean modified = false;
 for (E e : c)
 if (add(e))
 modified = true;
 return modified;
 }
}

Implementation 2:

public static final class $IndexLinkedHashSet<E> implements Set<E> {
 private final ArrayList<E> list = new ArrayList<>( );
 private final HashSet<E> set = new HashSet<> ( );
 public synchronized boolean add(E e) {
 if ( set.add(e) ) {
 return list.add(e);
 }
 return false;
 }
 public synchronized boolean remove(Object o) {
 if ( set.remove(o) ) {
 return list.remove(o);
 }
 return false;
 }
 @Override
 public boolean containsAll(Collection<?> c) {
 return set.containsAll(c);
 }
 public synchronized void clear() {
 set.clear();
 list.clear();
 }
 public synchronized E get(int index) {
 return list.get(index);
 }
 
 
 // Added this function
 public synchronized int indexOf(E element) {
 return list.indexOf(element);
 }
 //
 
 public synchronized boolean removeAll(Collection<?> c) {
 if ( set.removeAll(c) ) {
 return list.removeAll(c);
 }
 return true;
 }
 public synchronized boolean retainAll(Collection<?> c) {
 if ( set.retainAll(c) ) {
 return list.retainAll(c);
 }
 return false;
 }
 public synchronized boolean addAll(Collection<? extends E> c) {
 boolean modified = false;
 for (E e : c)
 if (add(e))
 modified = true;
 return modified;
 }
 @Override
 public synchronized int size() {
 return set.size();
 }
 @Override
 public synchronized boolean isEmpty() {
 return set.isEmpty();
 }
 @Override
 public synchronized boolean contains(Object o) {
 return set.contains(o);
 }
 @Override
 public synchronized Iterator<E> iterator() {
 return list.iterator();
 }
 @Override
 public synchronized Object[] toArray() {
 return list.toArray();
 }
 @Override
 public synchronized <T> T[] toArray(T[] a) {
 return list.toArray(a);
 }
}

Example:

 public static void main (String[]args)
 {
 $IndexLinkedHashSet<String> names = new $IndexLinkedHashSet<String>();
 names.add("Mike");
 names.add("John");
 names.add("Karen");
 
 System.out.println("what's the index of John? "+names.indexOf("John")); // 1
 System.out.println("Who comes after John? "+names.get(names.indexOf("John")+1)); // Karen
 }

Answer 7

A better way there is not, only a single lined one (which makes use of the iterator, too but implicitly):

new ArrayList(names).get(0)

• mjs: No good, new arraylist just to do this. It's cheaper to iterate the set.

Answer 8

You can convert your Set to List then you can do any indexing operations.

Example: need to crop Set list to 5 items.

 Set<String> listAsLinkedHashSet = new LinkedHashSet<>();
 listAsLinkedHashSet.add("1");
 listAsLinkedHashSet.add("2");
 listAsLinkedHashSet.add("3");
 listAsLinkedHashSet.add("4");
 listAsLinkedHashSet.add("1");
 listAsLinkedHashSet.add("2");
 listAsLinkedHashSet.add("5");
 listAsLinkedHashSet.add("7");
 listAsLinkedHashSet.add("9");
 listAsLinkedHashSet.add("8");
 listAsLinkedHashSet.add("1");
 listAsLinkedHashSet.add("10");
 listAsLinkedHashSet.add("11");
 List<String> listAsArrayList = new ArrayList<>(listAsLinkedHashSet);
 //crop list to 5 elements
 if (listAsArrayList.size() > 5) {
 for (int i = 5; i < listAsArrayList.size(); i++) {
 listAsArrayList.remove(i);
 i--;
 }
 }
 listAsLinkedHashSet.clear();
 listAsLinkedHashSet.addAll(listAsArrayList);

• krishna T: @dyno-chris I am sure the person asking question knows how to create ArrayList from set and question was specifically find index without iteration. You are iterating ArrayList instead of set. Second problem is if the set is large then you will be wasting lots of memory.
• krishna T: The questioner was clear. "The following works fine .. with this question i wonder if there is a better way"