locked
use of GetHashCode and Equal RRS feed

  • Question

  • Hi,

    I am trying to understand a piece of code which basically uses GetHashCode() and Equals(). I googled it but still can't find any good artical to understand. MsDN has something but cud'nt understand.

    The below metioned code has been used in my app class library. I have taken it out and put it in console app and used some constant value just to make it compilable.

    Can someone explain me the use of NameValuePair class from below code snippet. More specifically the use of GetHashCode and Equals (If posible if you can put line by line comment for each line for method GetHashCode and Equals stating why we have written it, wud be great).


    Code:


     class Program
        {
            private static readonly IDictionary<NameValuePair, string> myNameValueAssetMappings =
                new Dictionary<NameValuePair, string>();

            static void Main(string[] args)
            {
                // some code
               
                var pair = ConstructNameValuePair("someName", "SomeValue");
                if (pair != null)
                {
                    myNameValueAssetMappings[pair] = "20000"; // this value will be coming from somewhere else
                }

                Console.ReadKey();
            }

            private static NameValuePair ConstructNameValuePair(string name, string value)
            {
               // some code

                return new NameValuePair(name, value);
            }  

            #region NameValuePair

            private sealed class NameValuePair : Tuple<string, string>
            {
               
                internal NameValuePair(string name, string value) :
                    base(name, value)
                {
                    // left empty
                }

                /// <see cref="object.GetHashCode"/>
                public override int GetHashCode()
                {
                    return Item1.GetHashCode() + 5 * Item2.GetHashCode();
                }

                public override bool Equals(object obj)
                {
                    if (obj == this)
                    {
                        return true;
                    }
                    var otherPair = obj as NameValuePair;
                    if (otherPair == null)
                    {
                        return false;
                    }
                    return otherPair.Item1 == Item1 &&
                           otherPair.Item2 == Item2;
                }
            }

            #endregion
        }

    Thanks a lot for taking time to read this.

    your help will be highly appriciated.

    Best Regards.

    Sunday, November 25, 2012 6:52 AM

Answers

  • Ok, here goes:

    // Defines the notion of 'Equality' for objects of type 
    // NameValuePair (the type of the Key for objects stored
    // in the dictionary myNameValeAssetMappings
    public override bool Equals(object obj)   {
       // Returns true if the references obj and this are 
       // equal, ad thus point to the same object on the heap
       if (obj == this) {
          return true;
       }
    
       // Returns false if obj is null, as obviously it is
       // then != this (since we are inside a valid 'this')
       var otherPair = obj as NameValuePair;
       if (otherPair == null) {
          return false;
       }
    
       // Returns true if and only if Item1 and Item2 are 
       // the same value for both obj and this
       return otherPair.Item1 == Item1 &&
              otherPair.Item2 == Item2;
    }
     


    "Premature optimization is the root of all evil." - Knuth

    If I provoked thought, please click the green arrow

    If I provoked Aha! please click Propose as Answer

    • Marked as answer by Lisa Zhu Saturday, December 1, 2012 8:53 AM
    Sunday, November 25, 2012 12:05 PM
  • And for GetHashCode:

    // GetHashCode is used by an IDictionary to map keys to a
    // sparse array to reduce look-up time in exchange for
    // increased memory usage. A sparse array of lists of
    // objects of type TValue (conceptually if not exactly)
    // is allocated. GetHashCode is implemented by the KeyType
    // of the stored object to provide the mapping function
    // into the sparse array for use by the Dictionary.
    // A (very basic) default GetHashCode() is inherited from
    // the type object, which is leveraged here in an
    // uncomplicated fashion to obtain a GetHashCode for
    // NameValuePair
    
    /// <see cref="object.GetHashCode"/>
    public override int GetHashCode() {
       return Item1.GetHashCode() + 5 * Item2.GetHashCode();
    }
     
    


    "Premature optimization is the root of all evil." - Knuth

    If I provoked thought, please click the green arrow

    If I provoked Aha! please click Propose as Answer

    • Marked as answer by Lisa Zhu Saturday, December 1, 2012 8:53 AM
    Sunday, November 25, 2012 12:13 PM
  • To execute these two lines:

    1.  A call is made to GetHashCode to determine which particular slot in the sparse array holds the list of possible candidate items;
    2. The items in the selected list are scanned with Equals until a match to the NameValuePair is found; and
    3. The identified item is used in executing the code statement.

    Barring code optimizations by the compiler and jitter, I would expect a calls to both of GetHashCode and Equals to be made on each line you have specified.


    "Premature optimization is the root of all evil." - Knuth

    If I provoked thought, please click the green arrow

    If I provoked Aha! please click Propose as Answer

    • Marked as answer by Lisa Zhu Saturday, December 1, 2012 8:54 AM
    Sunday, November 25, 2012 8:30 PM
  •   

    // Returns false if obj is null, as obviously it is
      
    // then != this (since we are inside a valid 'this')
      
    var otherPair = obj as NameValuePair;
      
    if (otherPair == null) {
         
    return false;
      
    }
    The comment is not quite correct.  This code performs a downcast of obj from object to NameValuePair.  If the downcast is successful then otherPair will be a valid NameValuePair.  If the downcast is not successful then otherPair will be null, that is to say obj was not of a type that could be cast to NameValuePair.  If obj was not of a comparable type to NameValuePair then obj and 'this' cannot be equal and so false is returned.

    If obj is null then it is just a special case of obj not being of type NameValuePair.


    Paul Linton

    • Marked as answer by Lisa Zhu Saturday, December 1, 2012 8:53 AM
    Sunday, November 25, 2012 9:59 PM

All replies

  • Ok, here goes:

    // Defines the notion of 'Equality' for objects of type 
    // NameValuePair (the type of the Key for objects stored
    // in the dictionary myNameValeAssetMappings
    public override bool Equals(object obj)   {
       // Returns true if the references obj and this are 
       // equal, ad thus point to the same object on the heap
       if (obj == this) {
          return true;
       }
    
       // Returns false if obj is null, as obviously it is
       // then != this (since we are inside a valid 'this')
       var otherPair = obj as NameValuePair;
       if (otherPair == null) {
          return false;
       }
    
       // Returns true if and only if Item1 and Item2 are 
       // the same value for both obj and this
       return otherPair.Item1 == Item1 &&
              otherPair.Item2 == Item2;
    }
     


    "Premature optimization is the root of all evil." - Knuth

    If I provoked thought, please click the green arrow

    If I provoked Aha! please click Propose as Answer

    • Marked as answer by Lisa Zhu Saturday, December 1, 2012 8:53 AM
    Sunday, November 25, 2012 12:05 PM
  • And for GetHashCode:

    // GetHashCode is used by an IDictionary to map keys to a
    // sparse array to reduce look-up time in exchange for
    // increased memory usage. A sparse array of lists of
    // objects of type TValue (conceptually if not exactly)
    // is allocated. GetHashCode is implemented by the KeyType
    // of the stored object to provide the mapping function
    // into the sparse array for use by the Dictionary.
    // A (very basic) default GetHashCode() is inherited from
    // the type object, which is leveraged here in an
    // uncomplicated fashion to obtain a GetHashCode for
    // NameValuePair
    
    /// <see cref="object.GetHashCode"/>
    public override int GetHashCode() {
       return Item1.GetHashCode() + 5 * Item2.GetHashCode();
    }
     
    


    "Premature optimization is the root of all evil." - Knuth

    If I provoked thought, please click the green arrow

    If I provoked Aha! please click Propose as Answer

    • Marked as answer by Lisa Zhu Saturday, December 1, 2012 8:53 AM
    Sunday, November 25, 2012 12:13 PM
  • Thanks a lot for the reply.

    I have few more questions or some more doubt :-(

    When I debug the code (the code snippet), I found that GetHashCode() gets called when we try to
    assign myNameValueAssetMappings dictionary.

    myNameValueAssetMappings[pair] = "20000";

    And Equals() mthod gets called when we try to extract value from myNameValueAssetMappings

    var pairs = myNameValueAssetMappings[pair];


    Now my question is what exactly happens when we use this two statement.

    myNameValueAssetMappings[pair] = "20000"; and
    var pairs = myNameValueAssetMappings[pair];


    Again, a lots of thanks for taking time to write to this question.

    Best Regards.

    Sunday, November 25, 2012 3:34 PM
  • To execute these two lines:

    1.  A call is made to GetHashCode to determine which particular slot in the sparse array holds the list of possible candidate items;
    2. The items in the selected list are scanned with Equals until a match to the NameValuePair is found; and
    3. The identified item is used in executing the code statement.

    Barring code optimizations by the compiler and jitter, I would expect a calls to both of GetHashCode and Equals to be made on each line you have specified.


    "Premature optimization is the root of all evil." - Knuth

    If I provoked thought, please click the green arrow

    If I provoked Aha! please click Propose as Answer

    • Marked as answer by Lisa Zhu Saturday, December 1, 2012 8:54 AM
    Sunday, November 25, 2012 8:30 PM
  •   

    // Returns false if obj is null, as obviously it is
      
    // then != this (since we are inside a valid 'this')
      
    var otherPair = obj as NameValuePair;
      
    if (otherPair == null) {
         
    return false;
      
    }
    The comment is not quite correct.  This code performs a downcast of obj from object to NameValuePair.  If the downcast is successful then otherPair will be a valid NameValuePair.  If the downcast is not successful then otherPair will be null, that is to say obj was not of a type that could be cast to NameValuePair.  If obj was not of a comparable type to NameValuePair then obj and 'this' cannot be equal and so false is returned.

    If obj is null then it is just a special case of obj not being of type NameValuePair.


    Paul Linton

    • Marked as answer by Lisa Zhu Saturday, December 1, 2012 8:53 AM
    Sunday, November 25, 2012 9:59 PM
  • Paul:

    I understood that. Which explanation do you think the OP understood?

    Here is a good review of hashing:

    http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx


    "Premature optimization is the root of all evil." - Knuth

    If I provoked thought, please click the green arrow

    If I provoked Aha! please click Propose as Answer

    Sunday, November 25, 2012 10:02 PM
  • To expand slightly on my commentary above for Equals, by comparing it to the reference-equality operator ==:

    1. The operator (==) compares whether the same object is being referred to; and
    2. The method(Equals) compares whether the objects have the same contents.

    The first is strictly stronger than the second, asit is possible for two objects to have the same contents without actually being the same object by occupying thesame storage space.


    "Premature optimization is the root of all evil." - Knuth

    If I provoked thought, please click the green arrow

    If I provoked Aha! please click Propose as Answer

    Sunday, November 25, 2012 10:11 PM
  • Hi,

    Thanks for all the replies.
    I have again questions on this :-(

    Please see the below code.

     public interface IBook
        {
            string BookName { get; }
            string BookPrice { get; }
        }

        public class Book : IBook
        {
            public Book(string bookName, string bookPrice)
            {
                BookName = bookName;
                BookPrice = bookPrice;
            }

            public string BookName
            {
                get;
                private set;
            }

            public string BookPrice
            {
                get;
                private set;
            }

            public override int GetHashCode()
            {
                return BookName.GetHashCode() * 13 + 5 * BookPrice.GetHashCode();
            }

     
            public override bool Equals(object obj)
            {
                if (obj == this)
                {
                    return true;
                }
                var other = obj as Book;
                if (other != null)
                {
                    return other.BookName == BookName && other.BookPrice == BookPrice;
                }
                return false;
            }

            /// <summary>
            /// String representation
            /// </summary>
            /// <returns></returns>
            public override string ToString()
            {
                return new StringBuilder().Append("BookName = ")
                    .Append(BookName)
                    .Append(" BookPrice = ")
                    .Append(BookPrice)
                    .ToString();
            }
        }

    Now, we can have book class without having GetHashCode(), Equals() and ToString() method.
    And it works fine as well.

    Then why we need those to put.??

    may be a very basic question.

    Thanks again.

    Saturday, December 15, 2012 5:19 AM
  • It 'works fine' without them because it actually has them if you don't override them.

    All types derived from System.Object get both methods since they are defined in System.Object. That means all types have both GetHashCode and Equals. They just might not do what you expect.

    Try not overriding them and have, for example, two books with the same name and different prices. See what you get for the hash codes.

    A good discussion of them can be found in "CLR via C#" by Jeffrey Richter.


    Regards David R
    ---------------------------------------------------------------
    The great thing about Object Oriented code is that it can make small, simple problems look like large, complex ones.
    Object-oriented programming offers a sustainable way to write spaghetti code. - Paul Graham.
    Every program eventually becomes rococo, and then rubble. - Alan Perlis
    The only valid measurement of code quality: WTFs/minute.

    Saturday, December 15, 2012 10:28 AM
  • There are a few variations on 'works'.  If something compiles then it 'works'.  If something compiles and also runs without producing an error then it 'works' in a different sense.  If something compiles and also runs without producing an error and then also produces the correct answer then it 'works' in yet another sense.

    You example is of the second type, it compiles and runs without generating an error.  But does it produce the correct answer?  That depends on what you mean by the 'correct' answer.

    By way of example, expand your Book class by adding a property called Edition.  Do not change the code for Equals or GetHashCode.  Now, if you have two instances of Book say, bookOnShelf and bookRequired.  The question is 'Should bookOnShelf.Equals(bookRequired) be true'.  Assume further that bookOnShelf and bookRequired both have the same BookName and BookPrice but different values for Edition.  Your override for Equals will return true becuase it only compares Name and Price.  If you are a bookshop you may track which Edition your books are (bookOnShelf.Edition == 3, for example) but customers just make general enquiries (bookRequired.Edition == 0).  The result of true for bookOnShelf.Equals(bookRequired) is probably what you want ("Yes sir, I have a copy of that book on the shelf").  If you remove the code that overrides Equals then you will get the result of false if you call bookOnShelf.Equals(bookRequired) because the default implementation takes into account all properties - which is not what you want in this case.  The correct thing to do is imlement Equals as you have done (you should probably override == and != as well for convenience)

    On the other hand, you may run an antiquarian and fine editions bookshop.   Now your customers may well ask for a particular Edition of a book.  Using bookOnShelf.Edition == 2 and bookRequired.Edition == 1 the result that you want from .Equals is false, the reverse of the first scenario.  In this case you could either add Edition to your code for Equals or remove the override altogether.


    Paul Linton

    Saturday, December 15, 2012 10:13 PM
  • Hi,

    Thanks for the reply.

    I tried without overriding GetHashCode and Equals. But result are always correct.

    Can you send me a code snippet where the code is implemented whitout GetHashCode and Equals and
    the result are not correct?


    Regards

    Monday, December 17, 2012 5:09 AM
  • If you get the result that you want then you are OK.  If you read my post it gives an example of when you might want a different result.

    My previous post gives examples of when the answer might not be correct.  The code is to delete the override of Equals, I don't really know how to send nothing.


    Paul Linton

    Monday, December 17, 2012 5:13 AM