CODEWITHSUNDEEP
javadata-structures
Utku Zihnioglu
Utku Zihnioglu

Reputation: 4873

Random beginning index iterator for HashSet

I use HashSet for add(); remove(); clear(); iterator(); methods. So far everything worked like a charm. However, now I need to fulfill a different requirement.

I'd like to be able to start iterating from a certain index. For example, I'd like the following two programs to have same output.

Program 1

Iterator it=map.iterator();
for(int i=0;i<100;i++)
{
    it.next();
}
while (it.hasNext())
{
  doSomethingWith(it.next());
}

Program 2

Iterator it=map.iterator(100);
while (it.hasNext())
{
  doSomethingWith(it.next());
}

The reason I don't want to use the Program 1 is that it creates unnecessary overhead. From my research, I couldn't not find a practical way of creating an iterator with beginning index.

So, my question is, what would be a good way to achieve my goal while minimizing the overhead?

Thank you.

Upvotes: 3

Views: 2545

Answers (5)

Peter Lawrey
Peter Lawrey

Reputation: 533500

Following @toader's suggestion.

for(Integer i : new ArrayList<Integer>(set).subList(100, set.size())) {
   // from the 100'th value.
}

Note: the nth value has no meaning with a HashSet. Perhaps you need a SortedSet in which case the 100th would be 100th largest value.

Upvotes: 0

Jason Orendorff
Jason Orendorff

Reputation: 45086

Since a HashSet's iterator produces items in no particular order, it doesn't really make any difference whether you drop 100 items from the beginning or from the end.

Dropping items from the end would be faster.

Iterator it = map.iterator();
int n = map.size() - 100;
for (int i = 0; i < n; i++)
    doSomethingWith(it.next());

Upvotes: 2

Mihai Toader
Mihai Toader

Reputation: 12243

There is a reason why add(), remove(), are fast in a HashSet. You are trading the ability to treat the elements in the set as a random access list for speed and memory costs.

I'm afraid you can't really do that unless you convert your Set into a List first. This is simple to do but it usually involved a complete processing of all the elements in a Set. If you want the ability to start the iterator from a certain place more than once form the same state it might make sense. If not then you will probably be better with your current approach.

And now for the code (assuming that Set<Integer> set = new HashSet<Integer>(); is your declared data structure:

List<Integer> list = new ArrayList<Integer>(set);
list.subList(100, list.size()).iterator(); // this will get your iterator.

Upvotes: 5

卢声远 Shengyuan Lu
卢声远 Shengyuan Lu

Reputation: 32004

HashSet does not have order. So you could put the set into a List which could use index.

Example:

HashSet set = new HashSet();
//......
ArrayList list = new ArrayList(set);

Upvotes: 2

Costi Ciudatu
Costi Ciudatu

Reputation: 38195

You can make use of a NavigableMap. If you can rely on keys (and start from a certain key), that's out of the box.

Map<K,V> submap = navigableMap.tailMap(fromKey);

Then you'll use the resulting submap to simply get the iterator() and do your stuff. Otherwise, if you must start at some index, you may need make use of a temporary list.

K fromKey = new ArrayList<K>( navigableMap.keySet() ).get(index);

and then get the submap as above.

Upvotes: 1

Related Questions