How to iterate a collection fast and memory-efficient?

[Alan Krueger]

From Algorithms and Data Structures 101. There's a reason I wrote
"supposed to be" rather than "is" -- this is the bound for a hash
with a proper hash function. IRL YMMV of course.

A HashMap is a Map, not the other way around.

 

[steve]

Hi.

I took a look at the Sun's tutorial on collections, but it does not say much
about complexity of various operations, and... javadoc says even less :-/.

Please help:

I am using a Vector of elements, but it turned out that Vector is not
suitable anymore and I need SortedMap instead. One of the operations that I
am going to do very frequently is to iterate objects stored in the map in
the key's increasing order.

The only class implementing SortedMap is TreeMap, and in order to iterate, I
believe I have to use TreeMap.values(). Here come 2 questions:

1.
Will I get what I want? They say "collection's iterator will return the
values in the order
that their corresponding keys appear in the tree" in javadoc.

2.
Will this be as cheap in terms of memory and complexity, as in the case of
Vector?
-----------------------------
// v is Vector()
SomeType sth;
int tmpSize = v.size();
for ( int i = 0; i < tmpSize; i++ ) {
sth = (SomeType)v.get(i);
...
}

Iterator it = SupGrps.iterator();

for (int i = 0; it.hasNext(); i++) {
Object element = it.next();
}


or

Iterator it = SupGrps.iterator();
while ( it.hasNext())
{
Object element = it.next();
}

-----------------------------
Or maybe it will use more memory and time? The problem is that I am going to
iterate frequently, so I do not want the heap to grow fast before garbage
collector does its job.

I simply do not know what TreeMap.values() does actually...

It seems that a new object is created (this means some memory and time)...
luckily, the elements seem not to be copied ("The collection is backed by
this TreeMap instance, so changes to this map are reflected in the
collection, and vice-versa"). I could preserve the reference between
iterations and so save time and space if I iterate frequently. But if no
object is really created, and the method just returns a reference to the
member, then this is useless effort.

Well, then I have to get Collection.iterator()... this time I cannot
preserve its value between iterations because it is forward-only. Will this
call create a new object on each iteration or maybe it will return a
reference to some existing object?

Finally, if the collection and map base on the same elements, then I have no
idea of how fast Iterator.next() is going to be :-/.


Well maby something else than TreeMap?

My requirements:
a. fast access to elements by key,
b. keys are integers, but not a contiguous range [0..n];
they might start above zero and many keys might be missing
in the range,
c. frequent iterating of the elements must be fast and memory efficient,
d. iteration must return elements in order of keys or in order
they were added to the structure,
e. variable number of elements (but adding and removal needs
not to be extremely fast)

Thanks for any help in advance.

DW.