What isthe Miracle and the Disaster of the Dictionary object in Microsoft Dot Net Programming Code?
Arraysdirect indexing is one of the fastest retrieval operations ofcost 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 wholearrayfrom start to end till you find the object/value you want which has acost of Big O(n)where n is thearraysize.
Using numbers to index a value/object in anarrayhas 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 =newList<int>();
employeeAgeList.add(33);
intkhaledAge = 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>();
Hashing algorithm which transforms objects to an index number in the array:
Dictionaryis usingarraysin the background. But with a mathematical function, it takes ahashing codeand retrievesarrayindex number. Each object hashash codemethod calledGetHashCode()which produces a32-Bit integervalue for each object. But thehashing algorithmdoes not guarantee the uniqueness of thehash code. Secondly, the mathematical transformationalgorithmfromhash value to arrayindex number does not guarantee the uniqueness of thearrayindex value which is called acollisionin the mathematical transformation function.
Dictionaryuses a method to handlecollisionsby using a list in each box in thearraywhere acollisionoccurs. In case ofcollision, a sequential search will be added to search inside the list that handles thecollisionbox to return the correct value fromcollisionlist.
Here,GetHash(key)is, by default, the result returned by key’s call toGetHashCode()(although when using theHashtable, you can specify a customGetHash()function).GetHash(key) >> 5computes thehashfor keyand then shifts the result 5 bits to the right – this has the effect of dividing thehashresult by32. The % operator performs modular arithmetic.hashsizeis the number of total slots in thehashtable. (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 thatH(key)will be a value between 0 andhashsize– 1. Sincehashsizeis the total number of slots in thehash table, the resultinghashwill always point to within the acceptable range of values.
Collision Resolution in the Dictionary Class ByMicrosoft MSDN:
TheDictionaryclass differs from theHashtableclass in more ways than one. In addition to being strongly-typed, theDictionaryalso employs a differentcollisionresolution strategy than theHashtableclass, 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. (Withrehashing, thehashis recomputed, and that new slot is tried.) With chaining, however, a secondary data structure is utilized to hold anycollisions. Specifically, each slot in theDictionaryhas anarrayof elements that map to that bucket. In the event of acollision, the colliding element is prepended to the bucket’s list.
To better understand how chaining works, it helps to visualize theDictionaryas ahashtablewhose buckets each contain a linked list of items thathashto that particular bucket. Figure illustrates how series of items thathashto the same bucket will form a chain on that bucket.
TheDictionaryin the above figure has eight buckets, drawn in yellow and running from the top down. A number of Employee objects have been added to theDictionary. When an Employee object is added to theDictionary, it is added to the bucket that its keyhashesto and, if there’s already an Employee instance there, it’s prepended to the list of Employees. That is, employees Al and Johnhashto the same bucket, as do Fred, Zak, and Amy, and Sam and Ted. Rather than reprobing in the event of acollision, as is done with theHashtableclass, theDictionarysimply chains anycollisionsonto the bucket’s list.
Disadvantages of Dictionary:
Rehashingis an expensive process.Rehashingis the increase of thehashtablesize to minimizecollisionsas much as possible). Solution:InitializeDictionary const intCAPACITY_SIZE =100; Dictionary<string,int> nameAgeList =newDictionary<string,int>( CAPACITY_SIZE);
Dictionaryeats memory (Dictionaryuses large memory size). As more the items added to thedictionary, it leads to double, triple or more thearraysize with respect to the number of items in thearrayto lower the possiblecollisionsresulted from thehashing algorithm. Solution:Do not useDictionaryfor a big number of items unless high speed is required and you have enough memory.
تم النشر منذ
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?
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.
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:
Solution: Initialize Dictionary
const int CAPACITY_SIZE = 100;
Dictionary<string, int> nameAgeList = new Dictionary<string, int>( CAPACITY_SIZE);
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
شارك هذا الرد
رابط المشاركة
شارك الرد من خلال المواقع ادناه