Answered by:
C# HashTable internal structure

Dear all
I want to know about C# HashTable internal structure,According to article
http://msdn.microsoft.com/enus/library/ms379571(VS.80).aspx#datastructures20_2_topic5
I found that C# HashTable using rehasing, but rehashing also having disadvantages.Why the C# HashTable not based upon idea of perfect hashing?
in System.Collections.Hashtable ht = new System.Collections.Hashtable();
if I don't provide capacity to hashtable
then what would be default size of it ?.
how it grows, if its size become larger than default size ?
Thank you. Edited by Mr. Jehan Thursday, December 03, 2009 7:48 AM Went closer to solution
Question
Answers

Hi,
Could you please be more specific about the perfect hashing?
As far as I can see, every hashing method has it's shortcoming.
They choose rehasing because it provides better collision avoidance than either linear or quadratic probing.
A hashtable's capacity is used to calculate the optimal number of hashtable buckets based on the load factor. If you do not provide the initial capacity ,the default initial capacity is zero.
When the actual load factor reaches the load factor, the number of buckets is automatically increased to the smallest prime number that is larger than twice the current number of buckets.
Please note the actual load factor is 0.72 if you passin a number larger than 0.72.
That's because the class team found through empirical testing that values greater than 0.72 seriously degraded the performance.
If we pass using the overloading method that does not take parameters , it will call another overloading method and pass in 0 as capacity.
public Hashtable() : this(0, (float) 1f) { }
The hash table method found through Reflector:
public Hashtable(int capacity, float loadFactor) { if (capacity < 0) { throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); } if ((loadFactor < 0.1f)  (loadFactor > 1f)) { throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", new object[] { 0.1, 1.0 })); } this.loadFactor = 0.72f * loadFactor; double num = ((float) capacity) / this.loadFactor; if (num > 2147483647.0) { throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow")); } int num2 = (num > 11.0) ? HashHelpers.GetPrime((int) num) : 11; this.buckets = new bucket[num2]; this.loadsize = (int) (this.loadFactor * num2); this.isWriterInProgress = false; }
Please remember to mark the replies as answers if they help and unmark them if they provide no help.
Welcome to the AllInOne Code Framework! If you have any feedback, please tell us. Marked as answer by Harry Zhu Monday, December 14, 2009 7:11 AM

Hi,
The code bellow is found using .Net Reflector:
public virtual void Add(object key, object value)
{
this.Insert(key, value, true);
}
Please remember to mark the replies as answers if they help and unmark them if they provide no help.
Welcome to the AllInOne Code Framework! If you have any feedback, please tell us. Marked as answer by Mr. Jehan Friday, January 15, 2010 3:09 PM
All replies

Hi,
Could you please be more specific about the perfect hashing?
As far as I can see, every hashing method has it's shortcoming.
They choose rehasing because it provides better collision avoidance than either linear or quadratic probing.
A hashtable's capacity is used to calculate the optimal number of hashtable buckets based on the load factor. If you do not provide the initial capacity ,the default initial capacity is zero.
When the actual load factor reaches the load factor, the number of buckets is automatically increased to the smallest prime number that is larger than twice the current number of buckets.
Please note the actual load factor is 0.72 if you passin a number larger than 0.72.
That's because the class team found through empirical testing that values greater than 0.72 seriously degraded the performance.
If we pass using the overloading method that does not take parameters , it will call another overloading method and pass in 0 as capacity.
public Hashtable() : this(0, (float) 1f) { }
The hash table method found through Reflector:
public Hashtable(int capacity, float loadFactor) { if (capacity < 0) { throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); } if ((loadFactor < 0.1f)  (loadFactor > 1f)) { throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", new object[] { 0.1, 1.0 })); } this.loadFactor = 0.72f * loadFactor; double num = ((float) capacity) / this.loadFactor; if (num > 2147483647.0) { throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow")); } int num2 = (num > 11.0) ? HashHelpers.GetPrime((int) num) : 11; this.buckets = new bucket[num2]; this.loadsize = (int) (this.loadFactor * num2); this.isWriterInProgress = false; }
Please remember to mark the replies as answers if they help and unmark them if they provide no help.
Welcome to the AllInOne Code Framework! If you have any feedback, please tell us. Marked as answer by Harry Zhu Monday, December 14, 2009 7:11 AM

more info can be found here:
Hashtable Constructor ()http://msdn.microsoft.com/enus/library/aa318143(VS.71).aspx
Harry
Please remember to mark the replies as answers if they help and unmark them if they provide no help.
Welcome to the AllInOne Code Framework! If you have any feedback, please tell us. 

Hi,
The code bellow is found using .Net Reflector:
public virtual void Add(object key, object value)
{
this.Insert(key, value, true);
}
Please remember to mark the replies as answers if they help and unmark them if they provide no help.
Welcome to the AllInOne Code Framework! If you have any feedback, please tell us. Marked as answer by Mr. Jehan Friday, January 15, 2010 3:09 PM

Hi,
Just wanted a few clarifications from your end.
this.loadfactor=0.72*loadfactor
when i have already defined the loadfactor value in the constructor.
second, why do i need this statement in the constructor itself.
int num2 = (num > 11.0) ? HashHelpers.GetPrime((int) num) : 11;
Can you explain why there is a need to calculate the Prime in the constructor itself. When i am constructing a table for the first time, i don't need to resize forcefully, I will enlarge the bucket array only when the it is approaching 0.72.
I understand that this function will help me in increasing the size of the table, the bucket array.
healthy disregard for the impossible