C# HashTable internal structure

Question

Dear all

I want to know about C# HashTable internal structure,

  

According to article
 http://msdn.microsoft.com/en-us/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.

 

Answer 1

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; }

Harry

---

Please remember to mark the replies as answers if they help and unmark them if they provide no help.
Welcome to the All-In-One Code Framework! If you have any feedback, please tell us.

Answer 2

more info can be found here:

Hashtable Constructor ()

http://msdn.microsoft.com/en-us/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 All-In-One Code Framework! If you have any feedback, please tell us.

Answer 3

Thanks Harry,

 Could you please write code of add() method

---

Seek Knowledge From Cradle to Grave

Answer 4

Hi,

The code bellow is found using .Net Reflector:

public virtual void Add(object key, object value)
{
    this.Insert(key, value, true);
}

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] private void Insert(object key, object nvalue, bool add) { uint num; uint num2; if (key == null) { throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key")); } if (this.count >= this.loadsize) { this.expand(); } else if ((this.occupancy > this.loadsize) && (this.count > 100)) { this.rehash(); } uint num3 = this.InitHash(key, this.buckets.Length, out num, out num2); int num4 = 0; int index = -1; int num6 = (int) (num % this.buckets.Length); Label_0071: if (((index == -1) && (this.buckets[num6].key == this.buckets)) && (this.buckets[num6].hash_coll < 0)) { index = num6; } if ((this.buckets[num6].key == null) || ((this.buckets[num6].key == this.buckets) && ((this.buckets[num6].hash_coll & 0x80000000L) == 0L))) { if (index != -1) { num6 = index; } Thread.BeginCriticalRegion(); this.isWriterInProgress = true; this.buckets[num6].val = nvalue; this.buckets[num6].key = key; this.buckets[num6].hash_coll |= (int) num3; this.count++; this.UpdateVersion(); this.isWriterInProgress = false; Thread.EndCriticalRegion(); } else if (((this.buckets[num6].hash_coll & 0x7fffffff) == num3) && this.KeyEquals(this.buckets[num6].key, key)) { if (add) { throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", new object[] { this.buckets[num6].key, key })); } Thread.BeginCriticalRegion(); this.isWriterInProgress = true; this.buckets[num6].val = nvalue; this.UpdateVersion(); this.isWriterInProgress = false; Thread.EndCriticalRegion(); } else { if ((index == -1) && (this.buckets[num6].hash_coll >= 0)) { this.buckets[num6].hash_coll |= -2147483648; this.occupancy++; } num6 = (int) ((num6 + num2) % ((ulong) this.buckets.Length)); if (++num4 < this.buckets.Length) { goto Label_0071; } if (index == -1) { throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_HashInsertFailed")); } Thread.BeginCriticalRegion(); this.isWriterInProgress = true; this.buckets[index].val = nvalue; this.buckets[index].key = key; this.buckets[index].hash_coll |= (int) num3; this.count++; this.UpdateVersion(); this.isWriterInProgress = false; Thread.EndCriticalRegion(); } }

Harry

---

Please remember to mark the replies as answers if they help and unmark them if they provide no help.
Welcome to the All-In-One Code Framework! If you have any feedback, please tell us.

Answer 5

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