Any benefit for fixed size hashtable?

[Guest]

Hi,

If I am not sure how many items will be in my Hashtable/ArrayList
dynamically (multiple threads can add/remove/check the item), however, I can
estimate the total number will not exceed 60000. How much can I gain in term
of performance if I decalre the hash as

Hashtable h = new Hashtable(60000);

instead of

Hashtable h = new Hashtable()

Thanks

Chris

 

[Bob Powell [MVP]]

AFAIK Hashtables of large sizes are less useful than those of smaller
dimension because the tradeoff in accessing the keys diminishes with size.
To ensure a better access time a BTree might be the best choice. There are
several btree implementations available as source.

I've used BTrees before for things like type-ahead string searching in
dictionaries of 65000 phrases. The response times were phenomenally fast.

--
Bob Powell [MVP]
Visual C#, System.Drawing

Ramuseco Limited .NET consulting
http://www.ramuseco.com

Find great Windows Forms articles in Windows Forms Tips and Tricks
http://www.bobpowell.net/tipstricks.htm

Answer those GDI+ questions with the GDI+ FAQ
http://www.bobpowell.net/faqmain.htm

All new articles provide code in C# and VB.NET.
Subscribe to the RSS feeds provided and never miss a new article.

 

[Jon Skeet [C# MVP]]

AFAIK Hashtables of large sizes are less useful than those of smaller
dimension because the tradeoff in accessing the keys diminishes with size.
To ensure a better access time a BTree might be the best choice. There are
several btree implementations available as source.

I've used BTrees before for things like type-ahead string searching in
dictionaries of 65000 phrases. The response times were phenomenally fast.

Do you have any source for that? MSDN documents key retrieval in a
hashtable as an O(1) operation. Of course, if you've got a terrible
hash function, life will be pretty terrible, but I've used large
hashtables before with no problems.

 

[Bruce Wood]

AFAIK Hashtables of large sizes are less useful than those of smaller
dimension because the tradeoff in accessing the keys diminishes with size.

Sorry, Bob... I don't mean to be thick, but I read that statement five
times and have no idea what it means. What "tradeoff in accessing the
keys"? Tradeoff between what and what?

In general the opposite is true. Assuming a good hash function, larger
hash tables diminish the probability of chaining, which increases
access and storage speeds. Because hash tables are statistical
beasties, even having a table larger than the expected number of items
is of benefit (although as the hash table size to item count ratio
increases, you get diminishing returns, but performance still
increases, just not as dramatically).

 

[Guest]

sorry. I think my subject is misleading. My question is more general

for a collection class, like Queue, ArrayList or Hashtable, we can declare
them either as
new Queue(1000) or
new Queue()

My understanding is that fix size declaration may provide better memoery
allocation internally, but I am not sure whehter I will really gain anything
in performance. Since whenever I declare fix size, I always start a timed
bomb in the future which may explode if my data items go beyond that size and
I forget to handle it.

I see some leftover codes with hash,queue all declared as fixed size, which
I am thinking to change it since I assume that may bring me more trouble than
benefit.

Any thoughts?

Thanks

Chris

 

[Marc Gravell]

In general this isn't a problem, as this is just the initial capacity,
not the limit. There are exceptions (array being the most obvious).

If you expect rougly 60000, then allowing somewhere near that number
may save it having to expand a few times (which involves re-writing the
internal structure) - but since most containers use a doubling strategy
this doesn't hurt as much as you'd think. The hashtable IIRC uses a
"double then find next prime", so it would probably get to 60k in
significantly less than the 16 shuffles that it would take for straight
doubling (from 1; I can't recall the actual default capacity).

Note the other answer re spare capacity. Not my speciality, but useful
input... I must re-cap my theory ;-p

Marc

 

[Bruce Wood]

sorry. I think my subject is misleading. My question is more general

for a collection class, like Queue, ArrayList or Hashtable, we can declare
them either as
new Queue(1000) or
new Queue()

My understanding is that fix size declaration may provide better memoery
allocation internally, but I am not sure whehter I will really gain anything
in performance. Since whenever I declare fix size, I always start a timed
bomb in the future which may explode if my data items go beyond that size and
I forget to handle it.

I see some leftover codes with hash,queue all declared as fixed size, which
I am thinking to change it since I assume that may bring me more trouble than
benefit.

Don't confuse "initial size" with "fixed size".

None of the data structures you mentioned are "fixed size" in .NET. All
expand to accommodate new items if necessary.

The difference between specifying an initial size and not is that you
can save yourself the cost of reallocation and copying. (The only
exception is Hashtable, which works differently, but still has no
maximum... in the case of Hashtable you're really talking about storage
/ retrieval efficiency, not reallocation.)

For example, if you say

ArrayList x = new ArrayList();

and then add 1000 elements to it, your array list will start off with
some default capacity (say, 10) and then when the 11th element is added
the capacity will be increased. The standard algorithm is to double the
size on each reallocation, but I'm not sure what .NET does internally.

If you already know that you are going to have 1000 entries in the
array list, you can declare it

ArrayList x = new ArrayList(1100);

or something and save yourself the reallocation. (I used 1100 because
if you "know" there's going to be 1000 and there are in fact 1001 then
it would cost you a reallocation and copy to fit that last element in.
If you're just guessing you might as well use an even number like
1000.)

So, no matter what, you're never going to "hit the limit" on these data
structures. All you're doing is saving the maching a bit of extra work
reallocating and copying the data if you know that you're going to need
lots of items.

 

[Guest]

thanks

sorry. I think my subject is misleading. My question is more general

for a collection class, like Queue, ArrayList or Hashtable, we can declare
them either as
new Queue(1000) or
new Queue()

My understanding is that fix size declaration may provide better memoery
allocation internally, but I am not sure whehter I will really gain anything
in performance. Since whenever I declare fix size, I always start a timed
bomb in the future which may explode if my data items go beyond that size and
I forget to handle it.

I see some leftover codes with hash,queue all declared as fixed size, which
I am thinking to change it since I assume that may bring me more trouble than
benefit.

Any thoughts?

Thanks

Chris

 

[Bob Powell [MVP]]

In such a case the benefit comes only if you can predict the size of
your table or list and prevent the system from resizing / reallocating
the collection.

The consideration should be for performance cost, unless you're dealing
with huge structures memory cost is negligable, and if you can predict
your needs in a performance constrained system that's good.

I suggest testing with best / worse case scenarios to provide a good
average.

--
Bob Powell [MVP]
Visual C#, System.Drawing

Ramuseco Limited .NET consulting
http://www.ramuseco.com

Find great Windows Forms articles in Windows Forms Tips and Tricks
http://www.bobpowell.net/tipstricks.htm

Answer those GDI+ questions with the GDI+ FAQ
http://www.bobpowell.net/faqmain.htm

All new articles provide code in C# and VB.NET.
Subscribe to the RSS feeds provided and never miss a new article.