473,325 Members | 2,785 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

Any benefit for fixed size hashtable?

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
Nov 2 '06 #1
8 3695
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.

"chrisben" <ch******@discussions.microsoft.comwrote in message
news:B6**********************************@microsof t.com...
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

Nov 2 '06 #2
Bob Powell [MVP] <bob@_spamkiller_.bobpowell.netwrote:
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.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
Nov 2 '06 #3

Bob Powell [MVP] wrote:
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).

Nov 2 '06 #4
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

"chrisben" wrote:
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
Nov 2 '06 #5
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

Nov 2 '06 #6

chrisben wrote:
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.

Nov 2 '06 #7
thanks

"chrisben" wrote:
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

"chrisben" wrote:
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
Nov 2 '06 #8
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.

chrisben wrote:
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

"chrisben" wrote:
>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
Jan 31 '07 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

179
by: SoloCDM | last post by:
How do I keep my entire web page at a fixed width? ********************************************************************* Signed, SoloCDM
11
by: Linny | last post by:
Hi, I need some help in declaring an array of pointers to array of a certain fixed size. I want the pointers to point to arrays of fixed size only (should not work for variable sized arrays of the...
0
by: DC | last post by:
Hi, I currently use a SortedList for something like this: public class DataRow : SortedList { public DataRow() : base(3) { Add("id", (int)-1);
3
by: Manish Jain | last post by:
Platform: C# (Windows Application)/XP/Framework 1.1 ----------------------------------------------------------- Hi I am doing some performance checks, I am using a hashtable that I suspect is...
5
by: Phil Jones | last post by:
Is there a way to determine the size (number of bytes) of an object? I figure this can be done by serializing the object to disk and measuring the file size - but I definately don't want to do...
0
by: Ken Varn | last post by:
I have a managed C++ assembly in which I need to interact with some 'C' APIs that take fixed size 'C' data blocks. I need to wrap these data blocks into a managed object. It seems like a lot of...
2
by: PAzevedo | last post by:
I have this Hashtable of Hashtables, and I'm accessing this object from multiple threads, now the Hashtable object is thread safe for reading, but not for writing, so I lock the object every time I...
2
by: neuneudr | last post by:
Hi everybody, I'm scratching my head with a CSS problem. I want to have the following (the two pics have these size for a good reason, the whole point of the page is basically to show these...
24
by: Rob Hoelz | last post by:
Hello everyone, I'm working on a hashtable-based dictionary implementation in C, and it uses void pointers for data storage, naturally. However, since one of the data types I will be using it...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.