java - ArrayList .get faster than HashMap .get? -

java - ArrayList .get faster than HashMap .get? -

i had thought hashmaps faster random access of individual values arraylists . . . is, say, hashmap.get(key) should faster arraylist.get(index) because arraylist has traverse every element of collection reach value, whereas hashmap not. know, o(1) vs o(n) , that.

edit: understanding of hashmaps was/is inadequate, hence confusion. results code expected. many explanations.

so decided test it, on lark. here code:

import java.util.hashmap; import java.util.iterator; import java.util.listiterator; import java.util.nosuchelementexception; import java.util.scanner; public class testing { public static void main(string[] args) { arraylist<someclass> alist = new arraylist<>(); hashmap<short, someclass> hmap = new hashmap<>(4000, (float).75); listiterator<someclass> alistiterator = alist.listiterator(); short j = 0; { alistiterator.add(new someclass()); j++; } while(j < 4000); (short = 0; < 4000; i++) { hmap.put(i, new someclass()); } boolean done = false; scanner input = new scanner(system.in); string blargh = null; { system.out.println("\nenter 1 run iteration tests."); system.out.println("enter w run warmup (recommended)"); system.out.println("enter x terminate program."); seek { blargh = input.nextline(); } grab (nosuchelementexception e) { system.out.println("uh, what? seek again./n"); continue; } switch (blargh) { case "1": long starttime = 0; long total = 0; (short = 0; < 1000; i++) { starttime = system.nanotime(); iteratearraylist(alist); total += system.nanotime() - starttime; } total = (long)(total * .001); system.out.println(total + " ns: iterating sequentially" + " through arraylist"); total = 0; (short = 0; i< 1000; i++) { starttime = system.nanotime(); iteratearraylistbyget(alist); total += system.nanotime() - starttime; } total = (long)(total * .001); system.out.println(total + " ns: iterating sequentially" + " through arraylist via .get()"); total = 0; (short = 0; i< 1000; i++) { starttime = system.nanotime(); iteratehashmap(hmap); total += system.nanotime() - starttime; } total = (long)(total * .001); system.out.println(total + " ns: iterating sequentially" + " through hashmap via .next()"); total = 0; (short = 0; i< 1000; i++) { starttime = system.nanotime(); iteratehashmapbykey(hmap); total += system.nanotime() - starttime; } total = (long)(total * .001); system.out.println(total + " ns: iterating sequentially" + " through hashmap via .get()"); total = 0; (short = 0; i< 1000; i++) { starttime = system.nanotime(); getvaluebyindex(alist); total += system.nanotime() - starttime; } total = (long)(total * .001); system.out.println(total + " ns: getting end value" + " arraylist"); total = 0; (short = 0; i< 1000; i++) { starttime = system.nanotime(); getvaluebykey(hmap); total += system.nanotime() - starttime; } total = (long)(total * .001); system.out.println(total + " ns: getting end value" + " hashmap"); break; case "w": (int = 0; < 60000; i++) { iteratearraylist(alist); iteratearraylistbyget(alist); iteratehashmap(hmap); iteratehashmapbykey(hmap); getvaluebyindex(alist); getvaluebykey(hmap); } break; case "x": done = true; break; default: system.out.println("invalid entry. please seek again."); break; } } while (!done); input.close(); } public static void iteratearraylist(arraylist<someclass> alist) { listiterator<someclass> tempiterator = alist.listiterator(); { tempiterator.next(); } while (tempiterator.hasnext()); } public static void iteratearraylistbyget(arraylist<someclass> alist) { short = 0; { alist.get(i); i++; } while (i < 4000); } public static void iteratehashmap(hashmap<short, someclass> hmap) { iterator<hashmap.entry<short, someclass>> hmapiterator = map.entryset().iterator(); { hmapiterator.next(); } while (hmapiterator.hasnext()); } public static void iteratehashmapbykey(hashmap<short, someclass> hmap) { short = 0; { hmap.get(i); i++; } while (i < 4000); } public static void getvaluebykey(hashmap<short, someclass> hmap) { hmap.get(3999); } public static void getvaluebyindex(arraylist<someclass> alist) { alist.get(3999); } }

and

public class someclass { int = 0; float b = 0; short c = 0; public someclass() { = (int)(math.random() * 100000) + 1; b = (float)(math.random() * 100000) + 1.0f; c = (short)((math.random() * 32000) + 1); } }

interestingly enough, code seems warm in stages. final stage i've identified comes after around 120,000 iterations of methods. anyway, on test machine (amd x2-220, l3 + 1 core unlocked, 3.6 ghz, 2.1 ghz nb), numbers jumped out @ me lastly 2 reported. namely, time taken .get() lastly entry of arraylist (index == 3999) , time taken .get() value associated short key of 3999.

after 2-3 warmup cycles, testing shows arraylist.get() takes around 56 ns, while hashmap.get() takes around 68 ns. . . . not expected. hashmap eaten collisions? key entries supposed autobox shorts supposed study stored short value in response .hashcode(), hashcodes should unique. think?

even without warmups, arraylist.get() still faster. contrary i've seen elsewhere, such this question. of course, i've read traversing arraylist listiterator faster using .get() in loop, , obviously, not case . . .

hashmaps aren't faster @ retrieval of @ known index. if storing things in known order, list win.

but instead of illustration of inserting list 1-4000, did in total random order. retrieve right item list, have check each item 1 1 looking right item. retrieve hashmap, need know key have given when inserted it.

so really, should comparing hashmap.get(i) to

for(integer : integerlist) if(i==value) //found it!

then see real efficiency of hashmap.

java performance arraylist hashmap