إكسير مايكروسوفت دوت نت كود رقم 0005

[Phoenix Programmer 0]

What is the Miracle and the Disaster of the Dictionary object in Microsoft Dot Net Programming Code?

          Arrays direct indexing is one of the fastest retrieval operations of cost Big O(1). This is very useful in case you know the location of the item in the array. But in case you do not know the location, then you have to search the whole array from start to end till you find the object/value you want which has a cost of Big O(n) where n is the array size.

          Using numbers to index a value/object in an array has its complexity where retrieving value by name is much easier than by number.

C# String Indexing vs Number Indexing Example:

// Array with number indexing

List<int> employeeAgeList = new List<int>();

employeeAgeList.add(33);

int khaledAge = employeeAgeList[0]; // Age: 33

// Array with Text indexing using Hashing algorithms to transform

// Text to array index number in the background

Dictionary<string, int> employeeAgeDictionary = new Dictionary<string, int>();

employeeAgeDictionary.add(“Khaled”, 33);

int khaledAge = employeeAgeDictionary [“Khaled”]; // Age: 33

Hashing algorithm which transforms objects to an index number in the array:

          Dictionary is using arrays in the background. But with a mathematical function, it takes a hashing code and retrieves array index number. Each object has hash code method called GetHashCode() which produces a 32-Bit integer value for each object. But the hashing algorithm does not guarantee the uniqueness of the hash code. Secondly, the mathematical transformationalgorithm from hash value to array index number does not guarantee the uniqueness of the array index value which is called a collision in the mathematical transformation function.

          Dictionary uses a method to handle collisions by using a list in each box in the array where a collision occurs. In case of collision, a sequential search will be added to search inside the list that handles the collision box to return the correct value from collision list.

C# Dictionary Explained By Example:

string keyName1 = “Khaled”;

int khaledAge = 5;

Dictionary<string, int> namesAgeList = new Dictionary<string, int>();

namesAgeList.add(keyName1, khaledAge);

What Happens in the above code?

• Dictionary Strategy is doubling the size of the array to lower possible collisions (possible keys result in the same array index number).
• Mathematical Algorithm to output the array index number:
  hashsize: Array Size
  keyName1: “Khaled”
  Array Index number: H(keyName1)
  H(keyName1) = [GetHash(keyName1) + 1 + (((GetHash(keyName1) >> 5) + 1) % (hashsize – 1))] % hashsize

Algorithm Explained By Microsoft MSDN:

     Here, GetHash(key) is, by default, the result returned by key’s call toGetHashCode() (although when using the Hashtable, you can specify a custom GetHash() function). GetHash(key) >> 5 computes the hash for keyand then shifts the result 5 bits to the right – this has the effect of dividing the hash result by 32. The % operator performs modular arithmetic. hashsizeis the number of total slots in the hash table. (Recall that x % y returns the remainder of x / y, and that this result is always between 0 and y – 1.) Due to these mod operations, the end result is that H(key) will be a value between 0 and hashsize – 1. Since hashsize is the total number of slots in the hash table, the resulting hash will always point to within the acceptable range of values.

Collision Resolution in the Dictionary Class By Microsoft MSDN:

     The Dictionary class differs from the Hashtable class in more ways than one. In addition to being strongly-typed, the Dictionary also employs a different collision resolution strategy than the Hashtable class, using a technique referred to as chaining. Recall that with probing, in the event of acollision, another slot in the list of buckets is tried. (With rehashing, thehash is recomputed, and that new slot is tried.) With chaining, however, a secondary data structure is utilized to hold any collisions. Specifically, each slot in the Dictionary has an array of elements that map to that bucket. In the event of a collision, the colliding element is prepended to the bucket’s list.

     To better understand how chaining works, it helps to visualize theDictionary as a hashtable whose buckets each contain a linked list of items that hash to that particular bucket. Figure illustrates how series of items thathash to the same bucket will form a chain on that bucket.

     The Dictionary in the above figure has eight buckets, drawn in yellow and running from the top down. A number of Employee objects have been added to the Dictionary. When an Employee object is added to the Dictionary, it is added to the bucket that its key hashes to and, if there’s already an Employee instance there, it’s prepended to the list of Employees. That is, employees Al and John hash to the same bucket, as do Fred, Zak, and Amy, and Sam and Ted. Rather than reprobing in the event of a collision, as is done with theHashtable class, the Dictionary simply chains any collisions onto the bucket’s list.

Disadvantages of Dictionary:

• Rehashing is an expensive process. Rehashing is the increase of thehashtable size to minimize collisions as much as possible).
  Solution: Initialize Dictionary 
  const int CAPACITY_SIZE = 100;
  Dictionary<string, int> nameAgeList = new Dictionary<string, int>( CAPACITY_SIZE);
• Dictionary eats memory (Dictionary uses large memory size). As more the items added to the dictionary, it leads to double, triple or more the arraysize with respect to the number of items in the array to lower the possiblecollisions resulted from the hashing algorithm.
  Solution: Do not use Dictionary for a big number of items unless high speed is required and you have enough memory.

 

Dot Net Code Elixir Number 0005: 
https://goo.gl/ouZCJo

Draft 0005 Dot Net Code Elixir E-Book: 
https://goo.gl/HrygWP