Why ArrayList, not Hashtable

[Bruce]

Hi
I am having a problem understanding the exact advantages of using an
ArrayList over a Hashtable in any situation.
In most areas of an application I am working on, lookup needs to be
fast. If I use a hashtable
Addition - O(1) - same as ArrayList
Removal - O(1) - same as ArrayList
Lookup- O(1) - ArrayList is O(n)
Memory - Maybe slightly more than ArrayList since we have a hash to
store.

And even if I need lookup by index which is easy using ArrayList, I
could simply use a Hashtable with the array index as the key and value
as my object.

The only other thing I do not know about is serialization efficiency.

So, my question is, anywhere I need lookup, I can just blindly use a
hashtable? In which situation would it be better to use an ArrayList?

Thanks
Bruce

 

[Michael Nemtsev]

Hello Bruce,

B> So, my question is, anywhere I need lookup, I can just blindly use a
B> hashtable? In which situation would it be better to use an ArrayList?

Yep. the hashlist advantage over the arraylist in the way of getting value
by key

---
WBR, Michael Nemtsev [C# MVP].
My blog: http://spaces.live.com/laflour
Team blog: http://devkids.blogspot.com/

"The greatest danger for most of us is not that our aim is too high and we
miss it, but that it is too low and we reach it" (c) Michelangel

 

[Jon Skeet [C# MVP]]

I am having a problem understanding the exact advantages of using an
ArrayList over a Hashtable in any situation.

Use an ArrayList when you want to store a list. Use a Hashtable when
you want a map/dictionary.

In most areas of an application I am working on, lookup needs to be
fast. If I use a hashtable
Addition - O(1) - same as ArrayList
Removal - O(1) - same as ArrayList
Lookup- O(1) - ArrayList is O(n)
Memory - Maybe slightly more than ArrayList since we have a hash to
store.

And even if I need lookup by index which is easy using ArrayList, I
could simply use a Hashtable with the array index as the key and value
as my object.

Even though it's O(1) it's still going to be less efficient doing that
than using an index with a list.

Note also that with a list, you typically want to iterate in index
order - which you get for free with a list, but not a hashtable (which
is naturally unordered).

The only other thing I do not know about is serialization efficiency.

So, my question is, anywhere I need lookup, I can just blindly use a
hashtable? In which situation would it be better to use an ArrayList?

If you need to look a value up by a key, you should indeed use a
Hashtable (or Dictionary<T> on 2.0). When something is naturally a
list, you should use an ArrayList (or preferably List<T> if you're
using 2.0).

 

[Bruce]

Use an ArrayList when you want to store a list. Use a Hashtable when
you want a map/dictionary.



Even though it's O(1) it's still going to be less efficient doing that
than using an index with a list.

Note also that with a list, you typically want to iterate in index
order - which you get for free with a list, but not a hashtable (which
is naturally unordered).



If you need to look a value up by a key, you should indeed use a
Hashtable (or Dictionary<T> on 2.0). When something is naturally a
list, you should use an ArrayList (or preferably List<T> if you're
using 2.0).

Thanks for the replies!
One question: My data are all logically lists - say, a user's list of
phone numbers.
I am forced to insert the numbers as both keys and values in a
Hashtable only because I need quick lookup - that affects performance.
O(N) for every lookup is not good for me. I guess it is ok in this
situation to use it in this manner?

Thanks
Bruce

 

[Alun Harford]

Hi
I am having a problem understanding the exact advantages of using an
ArrayList over a Hashtable in any situation.
In most areas of an application I am working on, lookup needs to be
fast. If I use a hashtable
Addition - O(1) - same as ArrayList

Not true. The worst case is O(n). If you have a very bad hash, there
will be n hash collisions when you try to add your element to the
hashtable. (Hashtables in C# also grow automatically, and this may
involve copying all the data in the old hashtable. You get this problem
also with an arraylist, so that's O(n) too).

Removal - O(1) - same as ArrayList

The worst case is O(n). Again, if your hash is very bad.

Lookup- O(1) - ArrayList is O(n)

Again, it's O(n) in the worst case. (If your hash is very bad).

Memory - Maybe slightly more than ArrayList since we have a hash to
store.

The constant of proportionality, k, is likely to be *much* larger in the
case of the hashtable (that's the really big problem).

I think you should read up on O(...) notation, and how hashtables and
arraylists work. You'd probably find it more useful than the answers
you'll get by asking in newsgroups.

Alun Harford

 

[=?ISO-8859-1?Q?G=F6ran_Andersson?=]

Thanks for the replies!
One question: My data are all logically lists - say, a user's list of
phone numbers.

That is not a list, that's a collection. Phone numbers doesn't have any
natural order, they are just a bunch of unordered items.

I am forced to insert the numbers as both keys and values in a
Hashtable only because I need quick lookup - that affects performance.
O(N) for every lookup is not good for me. I guess it is ok in this
situation to use it in this manner?

In a sorted list you can use binary search, that would be even faster.
There is a bit of work done everytime you change the list to keep the
list sorted, of course, but if you have much more lookups than changes,
it should still be faster.