Hashtable question.

[Guest]

Hi,

I'm working on a Client/Server application. Server application needs to
keep
track of all the clients.

I'm planning to use a Hashtable for this purpose. There would be thousands
of
clients connect to the server application. In this case, according to my
plan,
I need to store thousands of clients along with corresponding data
in the hashtable.

Do you think storing thousands of objects( [key,value] pairs ) in the
hashtable
could lead to any problems. If so, is there any other better way of
maintaing
thousands of [key,value] pairs. Kindly let me know.

Cheers,

Naveen.

 

[Tim Haughton]

I can't see a real problem. A HashTable is certainly the simplest way to do
what you propose. I guess it would help to ensure that what you put in has
good hash code support (GetHashCode).

Regards,

Tim Haughton

 

[Helge Jensen]

Do you think storing thousands of objects( [key,value] pairs ) in the
hashtable
could lead to any problems. If so, is there any other better way of
maintaing
thousands of [key,value] pairs. Kindly let me know.

If the most important operation is lookup you cannot beat hashing. but
declare it as IDictionary and instantiate it as Hashtable. That way you
don't pin yourself to using System.Collections.Hashtable for
implementation.

You should be able to have millions of entries in hashtables and still
have *very* efficient (O(1)) lookup and removal (provided you have
enough RAM .

In all situations of disconnected operation with server-storage, you
will need to consider what to do with "dead" items. Some cleanup will
need to be done to prevent the dictionary from filling up with old
connections that will never be used later. The most common technique is
"timeout", where each stored item will be expunged when a certain
timeout expires.

 

[Lars-Inge Tønnessen [VJ# MVP]]

You should be able to have millions of entries in hashtables and still
have *very* efficient (O(1)) lookup and removal (provided you have enough
RAM .

Hashtables performs better when they are about 75% full.


Regards,
Lars-Inge Tønnessen

 

[Michael S]

Hashtables performs better when they are about 75% full.

Please tell me why this is true. I would love to read your explanation... =)

I would say that hastables perform best when its fill-ratio is 1/4.

- Michael S

 

[Brian Gideon]

All,

Keeping in mind that you cannot make generalizations of this kind
regarding every hashtable we should all assume that we are specifically
talking about the System.Collections.Hashtable. The 75% figure cited
may have been based on the default load factor Microsoft chose for
their implementation which is 0.72. That means the Hashtable will
never be more than 72% full. If an item is inserted that would bring
the table over that threshold then an expansion occurs. That value was
chosen to optimally balance space and runtime efficiency based on
Microsoft's implementation. Since quadratic probing is used for the
basis of their implementation the size of the table is a prime number.

If by performance you mean the balance between space and runtime
efficiency then a fill ratio of no more than ~75% is optimal for the
..NET Hashtable. In general, though, lower fill ratios result in faster
runtimes, but more memory.

<http://msdn.microsoft.com/library/d...s/dv_vstechart/html/datastructures_guide2.asp>

Brian

 

[Michael S]

Thanks for the indepth explanation Brian.

Happy Coding
- Michael S

All,

Keeping in mind that you cannot make generalizations of this kind
regarding every hashtable we should all assume that we are specifically
talking about the System.Collections.Hashtable. The 75% figure cited
may have been based on the default load factor Microsoft chose for
their implementation which is 0.72. That means the Hashtable will
never be more than 72% full. If an item is inserted that would bring
the table over that threshold then an expansion occurs. That value was
chosen to optimally balance space and runtime efficiency based on
Microsoft's implementation. Since quadratic probing is used for the
basis of their implementation the size of the table is a prime number.

If by performance you mean the balance between space and runtime
efficiency then a fill ratio of no more than ~75% is optimal for the
..NET Hashtable. In general, though, lower fill ratios result in faster
runtimes, but more memory.

<http://msdn.microsoft.com/library/d...s/dv_vstechart/html/datastructures_guide2.asp>

Brian

 

[Helge Jensen]

A statement like "X is most efficient when Y" generally means that one
should strive to fullfill Y in order to improve efficiency. This is
definatly not true here, adding more elements to the hash-table without
re-hashing does *not* improve lookup or insert efficiency.

There really is a lot of freedom in the definition of even the
*statement* here. When is a hash-table most efficient? are we talking
worst-case or average lookup-time, insertions? memory consumption?
latency-time on rehashes? ...

Real hash-tables lookup and insert-performance doesn't depend on how
"full" they are. They use rehashing when "too many" key-collisions
occur, and can (given that the hash-function is, what's called
"universal" -- which is a specific way of saying it's good) be proven to
provide amortized O(1) insert, lookup and removal operations using O(N)
memory.

System.Collections.Hashtable is a pretty good implementation -- with an
acceptable tradeoff between space and performance, and basically you
should only think about "tuning" anything about it if you have run a
profiler and shown that the performance problem lies there.