Hash table & threading

[Guest]

Hi,
I am working on a winform app. I need to use an object which can store
some information(key/value pairs) and also can be acessed by multiple
threads(read/write). From what I heard Hash table is best suited for it. My
question is
Why hash table. why can't we use an array.
I thought hash table uses more memory than array. Correct me if am wrong.

 

[Dan Bass]

It all depends how you want to access your data. The point of a hash table
is that it's indexed by a value derived from the key, where an Array holds
single values in an numerically indexed fashion.

If you want to call the value for key "xyz" for example, then hash tables
are far more efficient. The Array would have to go through each element to
check for the value each time you want to access a value. The larger your
data set is, the more efficient the hash table becomes.

The other thing with ArrayList for example, is that it stores a single value
that is indexed by "i" where "i" is the next available integer. To get a
name/value pair you'd first have to create a struct (or class I suppose)
which contains two strings, name and value. Then create these and store
these in your array.

The more you look at it, the more you realise your requirement pushes you in
one direction or another.

 

[Guest]

Hash Tables use more memory, but in almost every case a Hash Table will have
better performance than an array. The only case where it's best to simply use
an array is when the keys are all consecutive integers.
Hash Tables are roughly O(1) to access a value with its key, while arrays
are usually O(N) or similar depending on your algorithm for lookup.

If you want to compromise to save memory, one thing you can do is use a
tree-based map. That will have slower access time [usually O(log N)] but it
will use very low memory overhead.

Another way to lower memory usage is to set the load factor of your hash
table to a high value. Lower load factors mean faster lookup, but they also
mean more memory. In general, the memory a hash table uses is 1.5 /
load-factor * number-of-entries. Setting your load factor too high can cause
your hash table to perform like an array. Setting it too low can cause it to
resize too often. It is usually good to keep it around 0.7. Unfortunately the
Hashtable class provided in the .NET Platform doesn't have an easy way to
change load factor that I know of. I would just rely on the Hashtable
implementation to handle your data efficiently.

There is almost no case where the memory savings of an Array will make up
for the performance hit. It's almost certainly better to use a Hash Table.