Sans Pareil Technologies, Inc.

Key To Your Business

Lab 4 - Hashing


In this lab exercise we will use a Book class that we will store in a std::unordered_set to illustrate principles of writing hash functions as well as consider some of the issues to keep in mind when working with hash table type structures.
Book.h 
The header file that defines the book class along with standard hashing functor and a custom hashing functor.
#pragma once
#include <string>

namespace csc280
{
  class Book
  {
  public:
    const std::string& getTitle() const noexcept { return title; }
    Book& setTitle( const std::string& value )
    {
      title = value;
      return *this;
    }

    const std::string& getSubtitle() const noexcept { return subtitle; }
    Book& setSubtitle( const std::string& value )
    {
      subtitle = value;
      return *this;
    }

    const std::string& getAuthor() const noexcept { return author; }
    Book& setAuthor( const std::string& value )
    {
      author = value;
      return *this;
    }

    float getPrice() const noexcept { return price; }
    Book& setPrice( float value )
    {
      price = value;
      return *this;
    }

  private:
    std::string title;
    std::string subtitle;
    std::string author;
    float price = 0.0;
  };

  inline bool operator==( const Book& lhs, const Book& rhs )
  {
    return lhs.getAuthor() == rhs.getAuthor() &&
      lhs.getPrice() == rhs.getPrice() &&
      lhs.getTitle() == rhs.getTitle() &&
      lhs.getSubtitle() == rhs.getSubtitle();
  }
}

namespace std
{
  template<>
  struct hash<csc280::Book>
  {
    size_t operator()( const csc280::Book& book ) const
    {
      using std::hash;
      return hash<string>()( book.getTitle() ) ^
        ( hash<string>()( book.getSubtitle() ) << 1 ) ^
        ( hash<string>()( book.getAuthor() )  << 1 ) >> 1 ^
        ( hash<float>()( book.getPrice() ) << 1 );
    }
  };
}

namespace csc280
{
  struct BookPointerHash
  {
    std::size_t operator()( const Book* book ) const
    {
      using std::hash;
      return book ? hash<Book>()( *book ) : 0;
    }
  };

  struct BookPointerEquals
  {
    bool operator()( const Book* lhs, const Book* rhs ) const
    {
      if ( lhs && rhs ) return *lhs == *rhs;
      if ( !lhs && !rhs ) return true;
      return false;
    }
  };
}
test.cpp 
The test suite for the hashing function. Also illustrates facts to keep in mind when dealing with hashes.
#include "catch.hpp"
#include "../main/Book.h"
#include <unordered_set>

SCENARIO( "Hashing same book in stages" )
{
  GIVEN( "An unordered_set of book instances" )
  {
    using Set = std::unordered_set<csc280::Book>;
    Set set;

    THEN( "Changing book properties makes book invisible" )
    {
      csc280::Book book;
      set.insert( book );
      REQUIRE( 1 == set.size() );

      book.setTitle( "Something" );
      REQUIRE( set.find( book ) == set.cend() );

      set.clear();
      set.insert( book );
      book.setTitle( "Something" );
      REQUIRE_FALSE( set.find( book ) == set.cend() );

      set.clear();
      set.insert( book );
      book.setSubtitle( "Else" );
      REQUIRE( set.find( book ) == set.cend() );
    }

    AND_THEN( "Adding same book with different information creates copies" )
    {
      csc280::Book book;
      book.setTitle( "Something" );
      set.insert( book );
      REQUIRE( 1 == set.size() );
      REQUIRE_FALSE( set.find( book ) == set.cend() );

      set.insert( book );
      REQUIRE( 1 == set.size() );

      book.setSubtitle( "Else" );
      set.insert( book );
      REQUIRE( 2 == set.size() );
    }
  }

  GIVEN( "An unordered_set of book pointers" )
  {
    using Set = std::unordered_set<csc280::Book*>;
    Set set;

    THEN( "Changing book properties does not affect visibility" )
    {
      csc280::Book book;
      set.insert( &book );
      REQUIRE( 1 == set.size() );

      book.setTitle( "Something" );
      REQUIRE_FALSE( set.find( &book ) == set.cend() );
    }

    AND_THEN( "Copy of book is not visisble" )
    {
      csc280::Book book;
      book.setTitle( "Something" );
      set.insert( &book );
      REQUIRE( 1 == set.size() );

      csc280::Book other = book;
      REQUIRE( set.find( &other ) == set.cend() );
    }
  }

  GIVEN( "An unordered_set of book pointers with custom hash function" )
  {
    using Set = std::unordered_set<csc280::Book*, csc280::BookPointerHash, csc280::BookPointerEquals>;
    Set set;

    THEN( "Changing book properties affects visibility" )
    {
      csc280::Book book;
      set.insert( &book );
      REQUIRE( 1 == set.size() );

      book.setTitle( "Something" );
      REQUIRE( set.find( &book ) == set.cend() );
    }

    AND_THEN( "Copy of book is visisble" )
    {
      csc280::Book book;
      book.setTitle( "Something" );
      set.insert( &book );
      REQUIRE( 1 == set.size() );

      csc280::Book other = book;
      REQUIRE_FALSE( set.find( &other ) == set.cend() );
    }
  }
}