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

Is it even possibl开发者_StackOverflow中文版e?

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;
    }
}

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);
// ...

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.

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.

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.

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

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

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)

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);