Java Iterated HashTable vs ArrayList speed

Question

I am writing a simple 3D SW rendering engine. I have a default ArrayList<Object3D> containing the whole scene. Now, I want to be able to add, remove and select objects by name, like 3D editors do (because its MUCH more simple than mouse select, but still looking good in homework :) ).

So, the first thing I thought is to have Hashtable for name and index to scene ArrayList. But, then I thought I could just simply save the scene using Hashtable directly, and go through it to render using iterator.

So I want to ask, in a 3D engine, what is speed-preferable? Because I will for-loop the scene many times per second, compared to selecting object. Is ArrayList any faster than iterated Hashtable? Thanks.

Answer 1

First, I suggest you use a HashMap instead of a Hashtable, for the same reason that ArrayList is a better choice than a Vector: less overhead due to useless synchronization.

My guess is that iterating through an ArrayList will be faster than iterating through the Set returned by a Hashtable's (or HashMap's) entrySet() method. But the only way to know is to profile.

Obviously, changes to the display list (other than appending or chopping off the last element) are going to be faster for a HashMap than for an ArrayList.

EDIT So I followed my own advice and benchmarked. Here's the code I used:

import java.util.*;

public class IterTest {
    static class Thing {
        Thing(String name) { this.name = name; }
        String name;
    }

    static class ArrayIterTest implements Runnable {
        private final ArrayList<Thing> list;
        ArrayIterTest(ArrayList<Thing> list) {
            this.list = list;
        }
        public void run() {
            int i = 0;
            for (Thing thing : list) {
                ++i;
            }
        }
    }

    static class ArraySubscriptTest implements Runnable {
        private final ArrayList<Thing> list;
        ArraySubscriptTest(ArrayList<Thing> list) {
            this.list = list;
        }
        public void run() {
            int i = 0;
            int n = list.size();
            for (int j = 0; j < n; ++j) {
                Thing thing = list.get(j);
                ++i;
            }
        }
    }

    static class MapIterTest implements Runnable {
        private final Map<String, Thing> map;
        MapIterTest(Map<String, Thing> map) {
            this.map = map;
        }
        public void run() {
            int i = 0;
            Set<Map.Entry<String, Thing>> set = map.entrySet();
            for (Map.Entry<String, Thing> entry : set) {
                ++i;
            }
        }
    }

    public static void main(String[] args) {
        final int ITERS = 10000;
        final Thing[] things = new Thing[1000];
        for (int i = 0; i < things.length; ++i) {
            things[i] = new Thing("thing " + i);
        }
        final ArrayList<Thing> arrayList = new ArrayList<Thing>();
        Collections.addAll(arrayList, things);
        final HashMap<String, Thing> hashMap = new HashMap<String, Thing>();
        for (Thing thing : things) {
            hashMap.put(thing.name, thing);
        }
        final ArrayIterTest t1 = new ArrayIterTest(arrayList);
        final ArraySubscriptTest t2 = new ArraySubscriptTest(arrayList);
        final MapIterTest t3 = new MapIterTest(hashMap);
        System.out.println("t1 time: " + time(t1, ITERS));
        System.out.println("t2 time: " + time(t2, ITERS));
        System.out.println("t3 time: " + time(t3, ITERS));
    }

    private static long time(Runnable runnable, int iters) {
        System.gc();
        long start = System.nanoTime();
        while (iters-- > 0) {
            runnable.run();
        }
        return System.nanoTime() - start;
    }
}

And here are the results for a typical run:

t1 time: 41412897
t2 time: 30580187
t3 time: 146536728

Clearly using an ArrayList is a big win (by a factor of 3-4) over a HashMap, at least for my style of iterating through a HashMap. I suspect the reason the array iterator is slower than array subscripting is all the iterator objects that need to be created and then garbage-collected.

For reference, this was done with Java 1.6.0_26 (64-bit JVM) on an Intel 1.6GHz quad-core Windows machine with plenty of free memory.

Answer 2

I'm fairly sure that iterating through the ArrayList will be faster than iterating over the Hashtable. Not sure how significant the difference is, though -- maybe (thumb suck) 2x in the actual internal logic, but that's not much.

But note that, unless you need multithread synchronization, you should use a HashMap rather than a Hashtable. There's some performance to be gained there.