hash-generator-test.cpp

Go to the documentation of this file.

/*
  HashGenerator(Test)  -  hash value generation details

  Copyright (C)         Lumiera.org
    2011,               Hermann Vosseler <Ichthyostega@web.de>

  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 2 of
  the License, or (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

* *****************************************************/

#include "lib/test/run.hpp"
#include "lib/util.hpp"

#include <boost/functional/hash.hpp>
#include <boost/lexical_cast.hpp>
#include <iostream>
#include <string>
#include <map>

using boost::lexical_cast;
using util::contains;
using std::string;
using std::cout;
using std::endl;


namespace lib {
namespace test{
  
  
  
  
  
  /***********************************************************************/
  class HashGenerator_test : public Test
    {
      
      virtual void
      run (Arg)
        {
          demonstrate_boost_hash_weakness();
          verify_Knuth_workaround();
        }
      
      
      typedef boost::hash<string> BoostStringHasher;
      typedef std::map<size_t, string> StringsTable;
      
      
      void
      demonstrate_boost_hash_weakness ()
        {
          BoostStringHasher hashFunction;
          StringsTable hashValues;
          string prefix = "Entry.";
          uint collisions(0);
          for (uint i=0; i<100000; ++i)
            {
              string candidate = prefix + lexical_cast<string> (i);
              size_t hashVal = hashFunction(candidate);
              
              if (contains (hashValues, hashVal))
                {
                  ++collisions;
                  string other = hashValues[hashVal];
                  cout << "Duplicate at "<< i    << endl;
                  cout << "existing--->" << other  << endl;
                  cout << "new-------->" << candidate << endl;
                  
                  size_t exHash = hashFunction(other);
                  size_t newHash = hashFunction(candidate);
                  cout << "hash-ex---->" << exHash << endl;
                  cout << "hash_new--->" << newHash << endl;
                }
              hashValues[hashVal] = candidate;
            }
          if  (0 < collisions)
            cout << "boost::hash for strings produced "<<collisions<<" collisions. This is a known problem."<<endl;
          else
            cout << "SURPRISE. No collisions with the boost::hash function." <<endl;
        }
      
      
      
      void
      verify_Knuth_workaround()
        {
          StringsTable hashValues;
          string prefix = "Entry.";
          const size_t seed = rand();
          
          const size_t KNUTH_MAGIC = 2654435761;
          
          uint collisions(0);
          for (uint i=0; i<20000; ++i)
            {
              string candidate = prefix + lexical_cast<string> (i);
              size_t l = candidate.length();
              size_t hashVal = seed;
              
              boost::hash_combine(hashVal, KNUTH_MAGIC * candidate[l-1]);
              boost::hash_combine(hashVal, KNUTH_MAGIC * candidate[l-2]);
              boost::hash_combine(hashVal, KNUTH_MAGIC * candidate[l-3]);
              boost::hash_combine(hashVal, KNUTH_MAGIC * candidate[l-4]);
              boost::hash_combine(hashVal, candidate);
              
              if (contains (hashValues, hashVal))
                {
                  ++collisions;
                  string other = hashValues[hashVal];
                  cout << "Hash collision between " << i << " and " << other <<endl;
                }
              hashValues[hashVal] = candidate;
            }
          CHECK (!collisions, "the Knuth trick failed to spread our hash values evenly enough, what a shame...");
        }
      
    };
  
  
  LAUNCHER (HashGenerator_test, "unit common");
  
  
}} // namespace lib::test