ArrayList .get faster than HashMap .get?

Question

I had thought that HashMaps were faster for random access of individual values than ArrayLists . . . that is, to say, that HashMap.get(key) should be faster than ArrayList.get(index) simply because the ArrayList has to traverse every element of the collection to reach its value, whereas the HashMap does not. You know, O(1) vs O(n) and all that.

edit: So my understanding of HashMaps was/is inadequate, hence my confusion. The results from this code are as expected. Thanks for the many explanations.

So I decided to test it, on a lark. Here is my 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;
        do
        {
            alistiterator.add(new SomeClass());
            j++;
        }
        while(j < 4000);
        for (short i = 0; i < 4000; i++)
        {
             hmap.put(i, new SomeClass());
        }
        boolean done = false;
        Scanner input = new Scanner(System.in);
        String blargh = null;
        do
        {
            System.out.println("\nEnter 1 to run iteration tests.");
            System.out.println("Enter w to run warmup (recommended)");
            System.out.println("Enter x to terminate program.");
            try
            {
                blargh = input.nextLine();
            }
            catch (NoSuchElementException e)
            {
                System.out.println("Uh, what? Try again./n");
                continue;
            }
            switch (blargh)
            {
                case "1":
                    long starttime = 0;
                    long total = 0;
                    for (short i = 0; i < 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;
                    for (short i = 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;
                    for (short i = 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;
                    for (short i = 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;
                    for (short i = 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"
                                   + " from ArrayList");
                    total = 0;
                    for (short i = 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"
                               + " from HashMap");
                    break;
                case "w":
                    for (int i = 0; i < 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 try again.");
                    break;
            }           
        }
        while (!done);
        input.close();
    }

    public static void iteratearraylist(ArrayList<SomeClass> alist)
    {
        ListIterator<SomeClass> tempiterator = alist.listIterator();
        do
        {
            tempiterator.next();
        }
        while (tempiterator.hasNext());
    }

    public static void iteratearraylistbyget(ArrayList<SomeClass> alist)
    {
        short i = 0;        
        do
        {
            alist.get(i);
            i++;
        }
        while (i < 4000);
    }

    public static void iteratehashmap(HashMap<Short, SomeClass> hmap)
    {
        Iterator<HashMap.Entry<Short, SomeClass>> hmapiterator = 
        map.entrySet().iterator();
        do
        {
            hmapiterator.next();
        }
        while (hmapiterator.hasNext());
    }   

    public static void iteratehashmapbykey(HashMap<Short, SomeClass> hmap)
    {
        short i = 0;
        do
        {
            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 a = 0;
    float b = 0;
    short c = 0;

    public SomeClass()
    {
        a = (int)(Math.random() * 100000) + 1;
        b = (float)(Math.random() * 100000) + 1.0f;
        c = (short)((Math.random() * 32000) + 1);
    }
}

Interestingly enough, the code seems to warm up in stages. The final stage that I've identified comes after around 120,000 iterations of all methods. Anyway, on my test machine (AMD x2-220, L3 + 1 extra core unlocked, 3.6 ghz, 2.1 ghz NB), the numbers that really jumped out at me were the last two reported. Namely, the time taken to .get() the last entry of the ArrayList (index == 3999) and the time taken to .get() the value associated with a Short key of 3999.

After 2-3 warmup cycles, testing shows that ArrayList.get() takes around 56 ns, while HashMap.get() takes around 68 ns. That is . . . not what I expected. Is my HashMap all eaten up with collisions? All the key entries are supposed to autobox to Shorts which are supposed to report their stored short value in response to .hashcode(), so all the hashcodes should be unique. I think?

Even without warmups, the ArrayList.get() is still faster. That is contrary to everything I've seen elsewhere, such as this question. Of course, I've also read that traversing an ArrayList with a ListIterator is faster than just using .get() in a loop, and obviously, that is also not the case . . .

Answer 1

Hashmaps aren't faster at retrieval of something at a known index. If you are storing things in a known order, the list will win.

But say instead of your example of inserting everything into the list 1-4000, you did it in a total random order. Now to retrieve the correct item from a list, you have to check each item one by one looking for the right item. But to retrieve it from the hashmap, all you need to know is the key you would have given it when you inserted it.

So really, you should be comparing Hashmap.get(i) to

for(Integer i : integerList)
   if(i==value)
       //found it!

Then you would see the real efficiency of the hashmap.

Answer 2

Big O for HashMap is O(1+α). Your α comes from hashcode collisions and a bucket must be traversed to check for equality.

Big O for pulling an item out of an ArrayList by index O(1)

When in doubt... draw it out...

Answer 3

Both ArrayList and HashMap are backed with arrays, HashMap has to compute a hash code of the key from which it derives the index to use for accessing the array while for accessing an and element in the ArrayList using get you provide the index. So its 3 operations vs 1 operation for the ArrayList.

But whether a List or a Map is backed with an array is implementation detail. So the answer may differ depending on which implementations you use.

Answer 4

the ArrayList has to traverse every element of the collection to reach its value

This is not true. ArrayList is backed by an array which allows for constant-time get operations.

HashMap's get, on the other hand, first must hash its argument, then it must traverse the bucket to which the hash code corresponds, testing each element in the bucket for equality with the given key. This will generally be slower than just indexing an array.

Answer 5

ArrayList.get(index) acctualy uses constant time, since ArrayList is backed by an array, so it just uses that index in the bacing array. ArrayList.contains(Object) is a long operation in O(n) in worst case.