143

If anybody is familiar with Objective-C there is a collection called NSOrderedSet that acts as Set and its items can be accessed as an Array's ones.

Is there anything like this in Java?

I've heard there is a collection called LinkedHashMap, but I haven't found anything like it for a set.

2
  • I am working on a similar problem in c++. with NSOrderedSet, can we access elements in the order we inserted into it?
    – Vinay
    Commented May 27, 2014 at 8:03
  • Do u know how to get above functionality in C++? i,e acting as SET and can be accessed as an Array's elements?
    – Vinay
    Commented May 27, 2014 at 9:22

11 Answers 11

170

Take a look at LinkedHashSet class for insertion-order, implementing SequencedSet & Set interfaces.

From Java doc:

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list 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. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.).

3
  • Thank you very much. It seams to be trivial looking at LinkedHashMap but I haven't found it somehow.
    – Uko
    Commented Jan 3, 2012 at 13:28
  • 3
    Class LinkedHashSet<E> Commented Jan 3, 2012 at 13:45
  • SequencedSet 🤔 *clicks javadoc* ... Since: 21 Commented Jul 19 at 19:46
41

Every Set has an iterator(). A normal HashSet's iterator is quite random, a TreeSet does it by sort order, a LinkedHashSet iterator iterates by insert order.

You can't replace an element in a LinkedHashSet, however. You can remove one and add another, but the new element will not be in the place of the original. In a LinkedHashMap, you can replace a value for an existing key, and then the values will still be in the original order.

Also, you can't insert at a certain position.

Maybe you'd better use an ArrayList with an explicit check to avoid inserting duplicates.

1
  • I want to be able to set/get element on specific position and to get them by order I've added them. It seams that LinkedHashSet should do that. Thanks for reply
    – Uko
    Commented Jan 3, 2012 at 13:24
16

Take a look at the Java standard API doc. Right next to LinkedHashMap, there is a LinkedHashSet. But note that the order in those is the insertion order, not the natural order of the elements. And you can only iterate in that order, not do random access (except by counting iteration steps).

There is also an interface SortedSet implemented by TreeSet and ConcurrentSkipListSet. Both allow iteration in the natural order of their elements or a Comparator, but not random access or insertion order.

For a data structure that has both efficient access by index and can efficiently implement the set criterium, you'd need a skip list, but there is no implementation with that functionality in the Java Standard API, though I am certain it's easy to find one on the internet.

4
  • I may be misunderstanding your comment but I was under the impression that since Java 1.6 there were several default collections based on skip lists (like, say, ConcurrentSkipListSet etc.). Commented Jan 3, 2012 at 12:55
  • @user988052: yes, but those don't implement random access by index (though my understanding of skip lists says that should be possible), which seems to be what Uko wants. Commented Jan 3, 2012 at 13:01
  • @MichaelBorgwardt Java 6 and later includes a pair of Skip List implementations: ConcurrentSkipListMap and ConcurrentSkipListSet. Both maintain a sort based on natural order or a Comparator. I do not understand if they provide the random access or order-of-entry you discuss. Commented Jul 6, 2015 at 20:03
  • @BasilBourque: good find, and thanks for the edits. OP wanted access by index, and now that I's looked at it and think about it, I think skip lists actually don't have that capability either... Commented Jul 7, 2015 at 8:01
6

TreeSet is ordered.

http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

3
  • This is the correct answer. Unlike LHSet, TreeSet does implement java.util.SortedSet.
    – deprecated
    Commented Apr 25, 2013 at 12:11
  • 51
    ordered and sorted is different things. TreeSet is sorted, not ordered
    – andrii
    Commented Jul 1, 2013 at 9:47
  • 5
    Exactly, ordered refers to insertion order (the way a List) works, while sorted refers to after-the-fact ordering of the elements based on some criteria. Commented Nov 9, 2015 at 16:47
5

Try using java.util.TreeSet that implements SortedSet.

To quote the doc:

"The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used"

Note that add, remove and contains has a time cost log(n).

If you want to access the content of the set as an Array, you can convert it doing:

YourType[] array = someSet.toArray(new YourType[yourSet.size()]); 

This array will be sorted with the same criteria as the TreeSet (natural or by a comparator), and in many cases this will have a advantage instead of doing a Arrays.sort()

1
  • 1
    I need ordering like in ArrayList e.i. if I put first element c and then element a, as I iterate over a collection I want to get them in the same order: c, a etc.
    – Uko
    Commented Jan 3, 2012 at 13:26
1

treeset is an ordered set, but you can't access via an items index, just iterate through or go to beginning/end.

1
  • With treeSet you'll incur in increased cost. LinkedHashSet has a lower cost.
    – Carlos
    Commented Jan 27, 2015 at 7:51
0

If we are talking about inexpensive implementation of the skip-list, I wonder in term of big O, what the cost of this operation is:

YourType[] array = someSet.toArray(new YourType[yourSet.size()]);

I mean it is always get stuck into a whole array creation, so it is O(n):

java.util.Arrays#copyOf
1
  • 1
    That depends on the performance characteristics of the iterator and the size() method of the underlying set. Iteration is usually O(n), size is usually O(1) except for ConcurrentSkipListSet where it's O(n). Commented Oct 23, 2012 at 13:42
0

You might also get some utility out of a Bidirectional Map like the BiMap from Google Guava

With a BiMap, you can pretty efficiently map an Integer (for random index access) to any other object type. BiMaps are one-to-one, so any given integer has, at most, one element associated with it, and any element has one associated integer. It's cleverly underpinned by two HashTable instances, so it uses almost double the memory, but it's a lot more efficient than a custom List as far as processing because contains() (which gets called when an item is added to check if it already exists) is a constant-time and parallel-friendly operation like HashSet's, while List's implementation is a LOT slower.

0

I had a similar problem. I didn't quite need an ordered set but more a list with a fast indexOf/contains. As I didn't find anything out there I implemented one myself. Here's the code, it implements both Set and List, though not all bulk list operations are as fast as the ArrayList versions.

disclaimer: not tested

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;
import java.util.Collection;
import java.util.Comparator;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import static java.util.Objects.requireNonNull;

/**
 * An ArrayList that keeps an index of its content so that contains()/indexOf() are fast. Duplicate entries are
 * ignored as most other java Set's do.
 */
public class IndexedArraySet<E> extends ArrayList<E> implements Set<E> {

    public IndexedArraySet() { super(); }

    public IndexedArraySet(Iterable<E> c) {
        super();
        addAll(c);
    }

    private HashMap<E, Integer> indexMap = new HashMap<>();

    private void reindex() {
        indexMap.clear();
        int idx = 0;
        for (E item: this) {
            addToIndex(item, idx++);
        }
    }

    private E addToIndex(E e, int idx) {
        indexMap.putIfAbsent(requireNonNull(e), idx);
        return e;
    }

    @Override
    public boolean add(E e) {
        if(indexMap.putIfAbsent(requireNonNull(e), size()) != null) return false;
        super.add(e);
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return addAll((Iterable<? extends E>) c);
    }
    public boolean addAll(Iterable<? extends E> c) {
        boolean rv = false;
        for (E item: c) {
            rv |= add(item);
        }
        return rv;
    }

    @Override
    public boolean contains(Object e) {
        return indexMap.containsKey(e);
    }

    @Override

    public int indexOf(Object e) {
        if (e == null) return -1;
        Integer i = indexMap.get(e);
        return (i == null) ? -1 : i;
    }

    @Override
    public int lastIndexOf(Object e) {
        return indexOf(e);
    }

    @Override @SuppressWarnings("unchecked")
    public Object clone() {
        IndexedArraySet clone = (IndexedArraySet) super.clone();
        clone.indexMap = (HashMap) indexMap.clone();
        return clone;
    }

    @Override
    public void add(int idx, E e) {
        if(indexMap.putIfAbsent(requireNonNull(e), -1) != null) return;
        super.add(idx, e);
        reindex();
    }

    @Override
    public boolean remove(Object e) {
        boolean rv;
        try { rv = super.remove(e); }
        finally { reindex(); }
        return rv;
    }

    @Override
    public void clear() {
        super.clear();
        indexMap.clear();
    }

    @Override
    public boolean addAll(int idx, Collection<? extends E> c) {
        boolean rv;
        try {
            for(E item : c) {
                // check uniqueness
                addToIndex(item, -1);
            }
            rv = super.addAll(idx, c);
        } finally {
            reindex();
        }
        return rv;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        boolean rv;
        try { rv = super.removeAll(c); }
        finally { reindex(); }
        return rv;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean rv;
        try { rv = super.retainAll(c); }
        finally { reindex(); }
        return rv;
    }

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        boolean rv;
        try { rv = super.removeIf(filter); }
        finally { reindex(); }
        return rv;
    }

    @Override
    public void replaceAll(final UnaryOperator<E> operator) {
        indexMap.clear();
        try {
            int duplicates = 0;
            for (int i = 0; i < size(); i++) {
                E newval = requireNonNull(operator.apply(this.get(i)));
                if(indexMap.putIfAbsent(newval, i-duplicates) == null) {
                    super.set(i-duplicates, newval);
                } else {
                    duplicates++;
                }
            }
            removeRange(size()-duplicates, size());
        } catch (Exception ex) {
            // If there's an exception the indexMap will be inconsistent
            reindex();
            throw ex;
        }

    }

    @Override
    public void sort(Comparator<? super E> c) {
        try { super.sort(c); }
        finally { reindex(); }
    }
}
0

IndexedTreeSet from the indexed-tree-map project provides this functionality (ordered/sorted set with list-like access by index).

0

My own MapTreeAVL (whose implementations are under the mtAvl package next to that interface) provides both a method to obtain a SortedSet and a way to have index-based access (some so-called Optimizations such as MinMaxIndexIteration might be preferred in that case).

(Note: since my repo is open you can directly download the desired file, but I advise you to check if [and will be] some other classes in the same superpackage dataStructure are required/used/imported)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.