Take the 2-minute tour ×

I am using HashSets in an implementation to have fast adding, removing and element testing (amortized constant time). However, I'd also like a method to obtain an arbitraty element from that set. The only way I am aware of is

Object arbitraryElement = set.iterator.next();

My question is - how fast (asymptotically speaking) is this? Does this work in (not amortized) constant time in the size of the set, or does the iterator().next() method do some operations that are slower? I ask because I seem to lose a log-factor in my implementation as experiments show, and this is one of the few lines affected.

Thank you very much!

share|improve this question
Can you explain more what you mean by "lose a log-factor"? I don't understand. –  oconnor0 Mar 16 '12 at 0:24
To clarify: I agree that the iterator needs amortized constant time to call next(), however this does not help me. If - just as an example - the iterator creates a deep copy of the hash table or the indizes upon creation, then I already lose O(n) time in the first step, i.e. I need O(n) time to pull an arbitrary element. –  HdM Mar 16 '12 at 0:52
@oconnor0 This was just motivation and does not really have a bearing on my question. Sorry for the confusion. –  HdM Mar 16 '12 at 0:53
add comment

6 Answers

up vote 2 down vote accepted

HashSet.iterator().next() linearly scans the table to find the next contained item.

For the default load factor of .75, you would have three full slots for every empty one.

There is, of course, no guarantee what the distribution of the objects in the backing array will be & the set will never actually be that full so scans will take longer.

I think you'd get amortized constant time.

Edit: The iterator does not create a deep copy of anything in the set. It only references the array in the HashSet. Your example creates a few objects, but nothing more & no big copies.

share|improve this answer
add comment

I wouldn't expect this to be a logarithmic factor, on average, but it might be slow in some rare cases. If you care about this, use LinkedHashSet, which will guarantee constant time.

share|improve this answer
add comment

I would maintain an ArrayList of your keys, and when you need a random object, just generate an index, grab the key, and pull it out of the set. O(1) baby...

share|improve this answer
Sounds promising, but does that work using the HashSet from the Java API? EDIT: Actually, I do get problems when I remove elements from my HashSet, as I need to remove the keys from the ArrayList as well; but this means I have to traverse the whole list to find it. –  HdM Mar 16 '12 at 0:13
no you don't. you pick a random number which is the index into the array. you don't have to traverse the array (unless the implementation resizes it, but you don't do that). –  hvgotcodes Mar 16 '12 at 13:35
add comment

Getting the first element out of a HashSet using the iterator is pretty fast: I think it's amortised O(1) in most cases. This assumes the HashSet is reasonably well-populated for it's given capacity - if the capacity is very large compared to the number of elements then it will be more like O(capacity/n) which is the average number of buckets the iterator needs to scan before finding a value.

Even scanning an entire HashSet with an iterator is only O(n+capacity) which is effectively O(n) if your capacity is appropriately scaled. So it's still not particularly expensive (unless your HashSet is very large)

If you want better than that , you'll need a different data structure.

If you really need the fast access of arbitrary elements by index then I'd personally just put the objects in an ArrayList which will give you very fast O(1) access by index. You can then generate the index as a random number if you want to select an arbitrary element with equal probability.

Alternatively, if you want to get an arbitrary element but don't care about indexed access then a LinkedHashSet may be a good alternative.

share|improve this answer
add comment

This is from the JDK 7 JavaDoc for HashSet:

Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

I looked at the JDK 7 implementation of HashSet and LinkedHashSet. For the former, the next operation is a linked-list traversal within a has bucket, and between buckets an array traversal, where the size of the array is given by capacity(). The latter is strictly a linked list traversal.

share|improve this answer
add comment

If you need an arbitrary element in the probabilistic sense, you could use the following approach.

class MySet<A> {
     ArrayList<A> contents = new ArrayList();
     HashMap<A,Integer> indices = new HashMap<A,Integer>();
     Random R = new Random();

     //selects random element in constant O(1) time
     A randomKey() {
         return contents.get(R.nextInt(contents.size()));

     //adds new element in constant O(1) time
     void add(A a) {

     //removes element in constant O(1) time
     void remove(A a) {
         int index = indices.get(a);

     //all other operations (contains(), ...) are those from indices.keySet()
share|improve this answer
add comment

Your Answer


