Intermittent Hashtable() error: Load factor too high

[Gary Davis]

Once a day or so, I receive an error on a fairly active website that
calls this StrMixed.cs method constructor. 99% of the time there is no
exception:

System.Web.Http UnhandledExcept ion: Exception of type
System.Web.Http UnhandledExcept ion was thrown. --->
System.InvalidO perationExcepti on: Hashtable insert failed. Load factor
too high.
at System.Collecti ons.Hashtable.I nsert(Object key, Object nvalue,
Boolean add)
at System.Collecti ons.Hashtable.s et_Item(Object key, Object value)
at AEC.StrMixed..c tor() in C:\Documents and
Settings\...\AE C\StrMixed.cs:l ine 97

A search on Google for "Load factor too high" and Hashtable did not
provide any insight.

The Hashtable created is fairly small and the trap occurs below:

public StrMixed()
{
Exceptions = new Hashtable();

Exceptions["3Do"] = "3DO";
Exceptions["A"] = "a";
Exceptions["Ac"] = "AC";
Exceptions["Ac-3"] = "AC-3";
Exceptions["Ac/Dc"] = "AC/DC";
Exceptions["Am/Fm"] = "AM/FM";
Exceptions["And"] = "and";
Exceptions["D.a.T"] = "D.A.T.";
Exceptions["De"] = "de";
Exceptions["Dr"] = "Dr";
Exceptions["Emi"] = "EMI";
Exceptions["En"] = "en";
Exceptions["For"] = "for";
Exceptions["Ft"] = "Ft";
Exceptions["Ii"] = "II";
Exceptions["Iii"] = "III";
Exceptions["Imax"] = "IMAX";
Exceptions["In"] = "in";
Exceptions["La"] = "la";
Exceptions["Los"] = "los";
Exceptions["Mac-Pc"] = "Mac-PC";
Exceptions["Macabre"] = "Macabre";
Exceptions["Macarena"] = "Macarena";
Exceptions["Macedonia"] = "Macedonia" ; <-- Traps here
Exceptions["Macedonian "] = "Macedonian ";
Exceptions["Mackie"] = "Mackie";
:
:


Since I know in advance the number of default entries added, should I
specify a load factor of some sort? This seems like a framework bug to
me.

Thanks

Gary Davis

[Fergus Cooney]

Re: Intermittent Hashtable() error: Load factor too high

Hi Gary,

I did a search on Google for "Load factor too high" as well and there
was just a single reference.

http://dotnet.di.unipi.it/Content/sscli/docs/doxygen/fx/bcl/hashtable_

8cs-source.html

This took me to the source code for an implementation of Hastable.

The top of the file started with: [some lines omitted]

00004 // Copyright (c) 2002 Microsoft Corporation. All rights
reserved.
00005 //
00006 // The use and distribution terms for this software are
contained in the file
00007 // named license.txt, which can be found in the root of this
distribution.
00008 // By using this software in any fashion, you are agreeing to
be bound by the
00009 // terms of this license.
00010 //
00017 ** Class: Hashtable
00021 ** Purpose: Hash table implementation
00023 ** Date: September 25, 1999
00024 **

Somewhere down inside is the function that you are calling when you
assign to the hashtable.

00711 // Inserts an entry into this hashtable. This method is
called from the Set
00712 // and Add methods. If the add parameter is true and the
given key already
00713 // exists in the hashtable, an exception is thrown.
00714 private void Insert (Object key, Object nvalue, bool
add) {
00715 if (key == null) {
00716 throw new ArgumentNullExc eption("key",
Environment.Get ResourceString( "ArgumentNull_K ey"));
00717 }

At at the end of the function it says: [Caps added]

00777
00778 // If you see this assert, make sure load
factor & count are reasonable.
00779 // Then verify that our double hash function (h2,
described at top of file)
00780 // meets the requirements described above. YOU
SHOULD NEVER SEE THIS ASSERT.
00781 BCLDebug.Assert (false, "hash table insert failed!
Load factor too high, or our double hashing function is incorrect.");
00782 throw new
InvalidOperatio nException(Envi ronment.GetReso urceString
("InvalidOperat ion_HashInsertF ailed"));
00783 }

Now, the error message isn't <exactly> like yours but it looks mighty
suspicious, doesn't it?

In which case the answer is, yes, set your loadfactor and initial
capacity. And who can dispute that it's a framework bug - they seem to
say so themselves!!

Note. There are no properties to determine the load factor or capacity
(number of buckets), but these are clearly visible if you stick your
Hashtable into a Watch - loadFactor, buckets.Length.

The documentation says 1.0 for initial load factor. I found that it
was 0.72 in .NET 1.0.3705

Regards,
Fergus

[Gary Davis]

Re: Intermittent Hashtable() error: Load factor too high

"Fergus Cooney" <wollus@tesco.n et> wrote in message news:<#Ra4tFAbD HA.2476@tk2msft ngp13.phx.gbl>. ..[color=blue]
> Hi Gary,
>
> I did a search on Google for "Load factor too high" as well and there
> was just a single reference.
>
> http://dotnet.di.unipi.it/Content/ss...bcl/hashtable_
> 8cs-source.html
>
> This took me to the source code for an implementation of Hastable.
>...
> Regards,
> Fergus[/color]

Yes, I did see that hit and was very interested in the source file and
other stuff on that site. It showed how complex the hashtable actually
is.

However, even though it indicated the error, I was not sure why it
traps on occasion and generally works fine, for the exact same
constructor. Also, I couldn't figure how what to set the load factor
to (1.1? 0.9?).

Gary

[Fergus Cooney]

Re: Intermittent Hashtable() error: Load factor too high

Hi Gary,

I think someone famous quoted:
Ours is not to reason why,
Ours to work around, or die.

Yes, it does look a meaty bit of code.

From looking at Insert(), it only tries increasing the Hashtable
if it's reached the limit (specified by the capacity (number of
buckets) and load factor) which is kept in the private variable
loadsize.

Did you try my suggestion of seeing how the Hastable grows by
using Add Watch?
The code I used is:
Dim oHashtable As New Hashtable
For I = 1 to 50
oHashtable(i) = 1000 + i
Next

You'll see that loadsize is small (7 for me). When the 8th item is
to be added, Insert() finds loadsize exceeded and proceeds to expand
the hashtable. In the docs it says that "the number of buckets is
automatically increased to the smallest prime number that is larger
than twice the current number of buckets.".

The initial (for me) number of buckets is 11 and the loadfactor is
..72 which gives a limit (loadsize = buckets.Length * loadfactor) of 7
(7.92 rounded down).

So, double the number of buckets (22) and go to the next prime
giving a new number of buckets, 27. The loadfactor stays the same, so
the new capacity (loadsize) is 27 * .72 = 24. The 25th insert will
cause further expansion. And so on.

So, your job is to find an initial size for the Hashtable which
will not cause Insert to expand the table. If it doesn't expand, it
won't reach the Exception.

I don't know how many items you have. But whatever it is, you need
to calculate for a loadsize which greater than your number of items.

Let's say you have 51 items. The loadfactor is .72 so the number
of buckets will be at least 51 / 0.72 which gives 70.833 which this
time is riunded <up> to 71. The number of buckets must be a prime
number (for an effective hashing algorithm). 71 <is> a prime number so
that's no problem.

Let's say you have 52 items. The loadfactor is .72 so the number
of buckets will be at least 52 / 0.72 which gives 72.222 which this
time is rounded up to 73. The number of buckets must be a prime number
and the next prime is 89. So the table will have 89 entries.

Have you followed so far? Because now I'm going to say forget all
that, lol, that's just background.

For plain Hashtables, the constructors are (), which you've been
using, (iCapacity) and (iCapacity, fLoadFactor).

You can use either of the other two because all the calculations
above are done by the Hashtable. It will ensure that whatever
loadfactor is used (default or supplied) it will have a sufficiently
large table to handle the given number of items.

The loadfactor is effectively the slider between max memory
efficiency (loadfactor = 1) and max access efficiency (loadfactor
smallish).

Small hashtables (loadfactor high) will have lots of what are
called 'collisions' when the initial index of two or more items is the
same and steps must be taken to get round this. With large hashtables
(loadfactor low), an item's initial index is always available to just
that item. But for this to happen there will be a large number of
buckets that will never be used. With medium Hastables there will be
some or occasional collisions, depending on how 'medium' it is.

Still with me ? Because now I'm going to say forget all that
<again>, lol.

I wouldn't worry about the loadfactor (should have said that in my
last post) - just use the capacity.

Hope this gives you more than you need. :-).

Regards,
Fergus

[Fergus Cooney]

Re: Intermittent Hashtable() error: Load factor too high

Hi Gary,

It's strange that you can't see loadsize, etc. I've got my
Hashtable added to a Watch window. When I click on the [+] it shows me
everything.

Regards,
Fergus