Shulou(Shulou.com)05/31 Report--

This article mainly introduces "what is the use of the C# dictionary". In the daily operation, I believe that many people have doubts about the use of the C# dictionary. The editor consulted all kinds of materials and sorted out the simple and easy-to-use operation methods. I hope it will be helpful to answer the doubt about "what is the use of C# dictionary?" Next, please follow the editor to study!

A dictionary represents a complex data structure that allows elements to be accessed by a key. A dictionary is also known as a mapping or hash table.

The main feature of dictionaries is the ability to quickly find values based on keys. You are also free to add and remove elements, which is a bit like List, but with no performance overhead of moving subsequent elements in memory.

The following figure is a simplified representation in which the key converts bits to a hash. Use a hash to create a number that associates the index with the value. The index then contains a link to the value. An index item can be associated with multiple values, and the index can be stored as a tree structure.

The .NET Framework provides several dictionary classes. The main class is Dictionary.

1. Type of key

The type used as a key in the dictionary must override the GetHashCode () method of the Object class. Whenever the dictionary class needs to determine the location of the element, it calls the GetHashCode () method. The int returned by the GetHashCode () method has a dictionary for calculating the index of the element placed at the corresponding location. We will introduce this algorithm later, and now we only need to know that it involves primes, so the capacity of the dictionary is a prime.

The requirements that the implementation code of the GetHashCode () method must meet:

* the same object should always return the same value

* different objects can return the same value

* it should be executed faster and the cost of calculation is small.

* it cannot throw an exception

* it should use at least one instance field

* Hash code values should be evenly distributed over the range of numbers that int can store

* Hash code is preferably unchanged during the lifetime of the object

The performance of the dictionary depends on the implementation code of the GetHashCode () method.

The reason why hash code values should be evenly distributed over the range of numbers that int can store:

If the hash code values returned by the two keys get the same index, the dictionary class must find the nearest available free location to store the second data item, which requires a certain search to retrieve this item later. This obviously degrades performance, and conflicts are more likely to occur if many keys have the same index when sorting. According to Microsoft's algorithm, this risk is minimized when the calculated hash code values are evenly distributed between int.MinValue and int.MaxValue.

In addition to implementing the GetHashCode () method, the key type must also implement the IEquatable.Equals () method, or override the Object.Equals () method. 0 because different key objects may return the same hash code, the dictionary uses the Equals () method to compare keys. The dictionary checks whether the two keys An and B are equal and calls the A.Equals (B) method. This means that it is necessary to ensure that the following conditions are always true:

If A.Equals (B) returns true, A.GetHashCode () and B.GetHashCode () always return the same hash code.

It sounds strange, but it's important. If the above conditions are not true, the dictionary will still work, but it will appear that after an object is placed in the dictionary, it can no longer be retrieved or the wrong entry is returned.

Therefore, if an override version of the Equals () method is provided, but no rewrite version of the GetHashCode () method is provided, the C# compiler displays a warning.

For System.Object, this condition is true, because the Equals () method is just a comparison reference, and the GetHashCode () method actually returns a hash code based only on the object address. This means that if the hash table is based on a key and the key does not override these methods, the hash table works, but the key is considered equal only if the object is exactly the same. That is, when you put an object in a dictionary, you must associate it with a reference to the key. Nor can you instantiate another key object later with the same value. It is not convenient to use types in dictionaries without overriding the Equals () method and the GetHashCode () method.

System.String implements the IEquatable interface and overloads the GetHashCode () method. The Equals () method provides a comparison of values, and the GetHashCode () method returns a hash code based on the value of the string. Therefore, it is convenient to use strings with keys in dictionaries.

Numeric types such as Int32 also implement the IEquatable interface and overload the GetHashCode () method. However, the hash codes returned by these types can only be mapped to values. If the number you want to use as a key is not distributed within the range of possible integer values, using an integer as a key does not satisfy the rule of average distribution of key values, so you cannot get the best performance. Int32 is not suitable for use in dictionaries.

If the type of key you need to use does not implement the IEquatable interface and overloads the GetHashCode () method based on the key value stored in the dictionary, you can create a comparator that implements the IEqualityComparer interface. The IEqualityComparer interface defines the GetHashCode () method and the Equals () method, and takes the passed object as a parameter, which provides a different implementation than the object type.

two。 Demo dictionary

Create an employee ID (EmployeeId) structure to use as the key for the dictionary. The data stored in the dictionary is an object of type Employee.

The members of this structure are a prefix character and a number that represent the employee. Both variables are read-only and can only be initialized in the constructor. The keys in the dictionary should not be changed, which must be guaranteed.

Public struct EmployeeId: IEquatable {private readonly char prefix; private readonly int number; public EmployeeId (string id) {Contract.Requires (id! = null); prefix = (id.ToUpper ()) [0]; int numLength = id.Length-1 Try {number = int.Parse (id.Substring (1, numLength > 6? 6: numLength));} catch (FormatException) {throw new Exception ("Invalid EmployeeId format") }} public override string ToString () {return prefix.ToString () + string.Format ("{0jcm6ju 000000}", number) } / / because the integer range is not filled, the GetHashCode method moves the number 16 bits to the left, then XOR with the original number, and / / finally multiplies the result by the hexadecimal number 0x15051505. In this way, the hash code is evenly distributed over the integer value area. Public override int GetHashCode () {return (number ^ number r.Country); foreach (Racer r in lookupRacers ["Australia"]) {Console.WriteLine (r);}}

Output:

Alan Jones Jack Brabham4. Ordered dictionary

The SortedDictionary class is a binary search tree in which elements are sorted by key. The key type must implement the IComparable interface.

If the types of keys cannot be sorted, you can also create a comparator that implements the IComparer interface and uses the comparator as a parameter to the constructor of the ordered dictionary.

The difference between SortedDictionary and ordered list SortedList:

* the SortedList class uses less memory than SortedDictionary.

* insertion and deletion of SortedDictionary elements are relatively fast.

* when filling a collection with sorted data, ortedList is faster if there is no need to change the capacity.

At this point, the study of "what is the use of the C# dictionary" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.