data structures

Today I had a little fun with java data structures and timing of adds vs lookups for Hashtable, ArrayList and LinkedList.

I intialized each structure with 10^6 random strings of length 6. 

Inserts:

Hashtable: 2061 ms
ArrayList: 706 ms
LinkedList: 867 ms

Lookups:


Hashtable: 0 ms!
ArrayList: 21 ms
LinkedList:  29 ms

These data basically make sense: hashtables take a while to load, but are super fast looking up because you're not looking through anything to get the element you want, as the hash tells you exactly where it is.  The other two take less time to load and more time to look up.  The weird bit here is that ArrayLists are supposed to insert faster than LinkLists (OK) and look up slower, but this last didn't hold true.  ArrayLists were just faster all around.  I think this has to do with where I was inserting in the list... beginning, middle, or end makes a difference here.

If I get time, I suppose that I should set this up to run a bunch of tests on inserting to different parts of the structures, and then get an average performace over many runs.  The machine is the standard box in our lab: Phenom II X4 945 quad processor with 4 GM RAM running Debian lenny.