Hashing, equality, and comparison

Although hash values must be equal for objects to be equal, the converse need not be true. Two objects hashing to the same value does not necessarily mean the objects are equal. For reasons of efficiency, object hash values of two objects are first compared to test for equality, before a more expensive comparison is made. If two objects do not hash to the same value, they cannot be equal, so the second, more expensive test can be avoided. Because most objects are not equal when compared, the quick hash comparison, based on the comparison of two longs, can be used to determine that two objects are not equal.

If hash values are not equal, elements are not equal

However, the comparator's Compare function is only called if the comparator's GetHash function has returned the same value for both objects. If Compare returns a value that indicates equality, the objects are considered equal. Thus if you subclass, TComparator, you must override both GetHash and Compare in a way that meets these two criteria. You must assure that objects which you consider equal will return identical hash values. Also, the hashing algorithm selected is important as an algorithm which provides good distribution of objects which should not be considered equal. Calls to a potentially costly implementation of Compare can be replaced by a simple comparison of the two long values returned by the hash function for each of the elements being compared.

Defining a comparator to reverse sort order

  class TReversedComparator : public TMOrderableCollectibleComparator<TStandardText> {
  public:
      virtual EComparisonResult   Compare(const TStandardText& leftObj,
                                          const TStandardText& rightObj) const;
      virtual HashResult          GetHash(const TStandardText& obj) const 
                                          { return obj.Hash(); }
  };

  EComparisonResult TReversedComparator::Compare(const TStandardText& leftObj,
                                                 const TStandardText& rightObj) const
  {
      qprintf("ENTER comparator\n");
      if (leftObj.IsLessThan(&rightObj))
          return kGreaterThan;
      if (leftObj.IsGreaterThan(&rightObj))
          return kLessThan;
      return kEqual;
  }

    TReversedComparator* comparator = new TReversedComparator;

Here's a complete program.

Sample program using reversed-order comparator

  // Copyright (c) 1994 Taligent, Inc. All Rights Reserved.
  
  #ifndef Taligent_STANDARDTEXT
  #include <StandardText.h>
  #endif
  
  #ifndef _H_STDIO
  #include <stdio.h>
  #endif
  
  void printCollection(TCollectionOf<TStandardText>* collection)
  {
      int i = 0;                          // tracks order of elements
      TIteratorOver<TStandardText>* iterator = collection->CreateIterator();
      for (TStandardText* text = iterator->First();
           text != NIL;
           text = iterator->Next(), i++) {
  
          ////////////////////////////////////////////////////
          // buffer must be large enough for
          // longest possible string + zero terminator
          ////////////////////////////////////////////////////
          static const int kBufferSize = 256;
          static char extractBuffer[kBufferSize];
  
          text->Extract(TTextRange::GetMaximumRange(),
                        extractBuffer,
                        kBufferSize - 1);
          printf("\n%3d> %s", i, extractBuffer);
      }
      printf("\n");
  
      delete iterator;
  }
  
  
  
  class TReversedComparator : public TMOrderableCollectibleComparator<TStandardText> {
  public:
      virtual EComparisonResult   Compare(const TStandardText& leftObj, const TStandardText& rightObj) const;
      virtual HashResult          GetHash(const TStandardText& obj) const { return obj.Hash(); }
  };
  
  
  EComparisonResult TReversedComparator::Compare(const TStandardText& leftObj,
                                                 const TStandardText& rightObj) const
  {
      if (leftObj.IsLessThan(&rightObj))
          return kGreaterThan;
      if (leftObj.IsGreaterThan(&rightObj))
          return kLessThan;
      return kEqual;
  }
  
  
  int main()
  {
      TReversedComparator* comparator = new TReversedComparator;
  
      TSortedSequenceOf<TStandardText>* collection =
          new TSortedSequenceOf<TStandardText>(comparator, NIL);
  
      collection->Add(new TStandardText("a"));
      collection->Add(new TStandardText("b"));
      collection->Add(new TStandardText("c"));
  
      collection->Add(new TStandardText("a"));
      collection->Add(new TStandardText("b"));
      collection->Add(new TStandardText("c"));
  
  
      printCollection(collection);
  
      delete collection;
      return 0;
  }

  1> c
  2> b
  3> b
  4> a
  5> a

In the following slightly contrived example, consider the comparator class that lets you monitor calls to the comparator's Compare member function.

Class for monitoring compare operations

  int main()
  {
      TIntComparator *comparator = new TIntComparator;
      TSetOf<TCollectibleLong>* collection =
          new TSetOf<TCollectibleLong>(comparator, NIL);
  
      collection->Add(new TCollectibleLong(0));
      collection->Add(new TCollectibleLong(1));
      collection->Add(new TCollectibleLong(2));
      collection->Add(new TCollectibleLong(1));
      collection->Add(new TCollectibleLong(1));
  
      printCollection(collection);
  
      delete collection;
      return 0;
  }

  ENTER comparator
  ENTER comparator
  
    0> 0
    1> 1
    2> 2

If the definition of the hash function were changed to always return a value of 0, you'd have the worst kind of hash function possible, as shown in the following definition for GetHash.

  class TIntComparator : public TMCollectibleComparator<TCollectibleLong> {
  public:
      ...
      virtual HashResult          GetHash(const TCollectibleLong& obj) const { return 0; }
  };

  ENTER comparator
  ENTER comparator
  ENTER comparator
  ENTER comparator
  ENTER comparator
  ENTER comparator
  ENTER comparator
  
    0> 0
    1> 2
    2> 1