New JavaRanch Journal article: Supercharging your HashMaps

[Ulf Dittmer]

The latest issue of the JavaRanch Journal contains an article by David O'Meara on Supercharging your HashMaps. Go read it while it's fresh, and discuss it in this thread.

[David O'Meara]

Not particularly ground breaking I admit, but if anyone has any comments on the "Unusual Iteration Times" mentioned in the after thoughts, I haven't had a chance to dig deeper and would appreciate opinions.

[Manuel Laflamme]

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 ]

[Campbell Ritchie]

. . . and welcome to JavaRanch, Manuel Laflamme

[David O'Meara]

Welcome also

Understood, but if you look at Table 5, we expect the iteration time to increase when increasing the initial capacity, what I wasn't expecting was the iteration time to decrease for a given capacity when the Map contains more items

ie

Key Size        Initial Capacity          Iterations        Time
    1000               1,000,000     10,000 (x 1000)      50,000
   10000               1,000,000     1000 (x 10,000)       5,800
  100000               1,000,000     100 (x 100,000)       2,400

In the above, the actual capacity should be the same in each case (2^20) but the iteration time decreases with the increasing size of data held in the HashMap, or so it would appear.