Map iteration is traversing the whole map entry table. If your initial capacity is 1,000,000 the iterator have to traverse all the 1,000,000 entries (2^20 actually) even if only a small subset of them contain values. So your
test with initial capacity of 1,000,000 and 1,000 keys is actually doing 10,000 iteration x 1,000,000 entries rather than 10,000 x 1,000.
[ July 31, 2008: Message edited by: Manuel Laflamme ]