Hashing function and bloom filter

profileBebo23
GeneralHashFunctions_-_CPP.zip
Home>Computer Science homework help>Hashing function and bloom filter

GeneralHashFunctions_-_CPP/GeneralHashFunctions.cpp

GeneralHashFunctions_-_CPP/GeneralHashFunctions.cpp

/*
 **************************************************************************
 *                                                                        *
 *          General Purpose Hash Function Algorithms Library              *
 *                                                                        *
 * Author: Arash Partow - 2002                                            *
 * URL: http://www.partow.net                                             *
 * URL: http://www.partow.net/programming/hashfunctions/index.html        *
 *                                                                        *
 * Copyright notice:                                                      *
 * Free use of the General Purpose Hash Function Algorithms Library is    *
 * permitted under the guidelines and in accordance with the MIT License. *
 * http://www.opensource.org/licenses/MIT                                 *
 *                                                                        *
 **************************************************************************
*/


#include   "GeneralHashFunctions.h"


unsigned   int   RSHash ( const  std :: string &  str )
{
    unsigned   int  b     =   378551 ;
    unsigned   int  a     =   63689 ;
    unsigned   int  hash  =   0 ;

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  =  hash  *  a  +  str [ i ];
      a     =  a  *  b ;
    }

    return  hash ;
}
/* End Of RS Hash Function */


unsigned   int   JSHash ( const  std :: string &  str )
{
    unsigned   int  hash  =   1315423911 ;

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  ^=   (( hash  <<   5 )   +  str [ i ]   +   ( hash  >>   2 ));
    }

    return  hash ;
}
/* End Of JS Hash Function */


unsigned   int   PJWHash ( const  std :: string &  str )
{
    unsigned   int   BitsInUnsignedInt   =   ( unsigned   int )( sizeof ( unsigned   int )   *   8 );
    unsigned   int   ThreeQuarters       =   ( unsigned   int )(( BitsInUnsignedInt    *   3 )   /   4 );
    unsigned   int   OneEighth           =   ( unsigned   int )( BitsInUnsignedInt   /   8 );
    unsigned   int   HighBits            =   ( unsigned   int )( 0xFFFFFFFF )   <<   ( BitsInUnsignedInt   -   OneEighth );
    unsigned   int  hash               =   0 ;
    unsigned   int  test               =   0 ;

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  =   ( hash  <<   OneEighth )   +  str [ i ];

       if (( test  =  hash  &   HighBits )    !=   0 )
       {
         hash  =   ((  hash  ^   ( test  >>   ThreeQuarters ))   &   ( ~ HighBits ));
       }
    }

    return  hash ;
}
/* End Of  P. J. Weinberger Hash Function */


unsigned   int   ELFHash ( const  std :: string &  str )
{
    unsigned   int  hash  =   0 ;
    unsigned   int  x     =   0 ;

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  =   ( hash  <<   4 )   +  str [ i ];
       if (( x  =  hash  &   0xF0000000L )   !=   0 )
       {
         hash  ^=   ( x  >>   24 );
       }
      hash  &=   ~ x ;
    }

    return  hash ;
}
/* End Of ELF Hash Function */


unsigned   int   BKDRHash ( const  std :: string &  str )
{
    unsigned   int  seed  =   131 ;   // 31 131 1313 13131 131313 etc..
    unsigned   int  hash  =   0 ;

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  =   ( hash  *  seed )   +  str [ i ];
    }

    return  hash ;
}
/* End Of BKDR Hash Function */


unsigned   int   SDBMHash ( const  std :: string &  str )
{
    unsigned   int  hash  =   0 ;

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  =  str [ i ]   +   ( hash  <<   6 )   +   ( hash  <<   16 )   -  hash ;
    }

    return  hash ;
}
/* End Of SDBM Hash Function */


unsigned   int   DJBHash ( const  std :: string &  str )
{
    unsigned   int  hash  =   5381 ;

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  =   (( hash  <<   5 )   +  hash )   +  str [ i ];
    }

    return  hash ;
}
/* End Of DJB Hash Function */


unsigned   int   DEKHash ( const  std :: string &  str )
{
    unsigned   int  hash  =   static_cast < unsigned   int > ( str . length ());

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  =   (( hash  <<   5 )   ^   ( hash  >>   27 ))   ^  str [ i ];
    }

    return  hash ;
}
/* End Of DEK Hash Function */


unsigned   int   BPHash ( const  std :: string &  str )
{
    unsigned   int  hash  =   0 ;
    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  =  hash  <<   7   ^  str [ i ];
    }

    return  hash ;
}
/* End Of BP Hash Function */


unsigned   int   FNVHash ( const  std :: string &  str )
{
    const   unsigned   int  fnv_prime  =   0x811C9DC5 ;
    unsigned   int  hash  =   0 ;
    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  *=  fnv_prime ;
      hash  ^=  str [ i ];
    }

    return  hash ;
}
/* End Of FNV Hash Function */


unsigned   int   APHash ( const  std :: string &  str )
{
    unsigned   int  hash  =   0xAAAAAAAA ;

    for ( std :: size_t i  =   0 ;  i  <  str . length ();  i ++ )
    {
      hash  ^=   (( i  &   1 )   ==   0 )   ?   (    ( hash  <<    7 )   ^  str [ i ]   *   ( hash  >>   3 ))   :
                                ( ~ (( hash  <<   11 )   +   ( str [ i ]   ^   ( hash  >>   5 ))));
    }

    return  hash ;
}
/* End Of AP Hash Function */

GeneralHashFunctions_-_CPP/GeneralHashFunctions.h

/* ************************************************************************** * * * General Purpose Hash Function Algorithms Library * * * * Author: Arash Partow - 2002 * * URL: http://www.partow.net * * URL: http://www.partow.net/programming/hashfunctions/index.html * * * * Copyright notice: * * Free use of the General Purpose Hash Function Algorithms Library is * * permitted under the guidelines and in accordance with the MIT License. * * http://www.opensource.org/licenses/MIT * * * ************************************************************************** */ #ifndef INCLUDE_GENERALHASHFUNCTION_CPP_H #define INCLUDE_GENERALHASHFUNCTION_CPP_H #include <string> typedef unsigned int (*HashFunction)(const std::string&); unsigned int RSHash (const std::string& str); unsigned int JSHash (const std::string& str); unsigned int PJWHash (const std::string& str); unsigned int ELFHash (const std::string& str); unsigned int BKDRHash(const std::string& str); unsigned int SDBMHash(const std::string& str); unsigned int DJBHash (const std::string& str); unsigned int DEKHash (const std::string& str); unsigned int BPHash (const std::string& str); unsigned int FNVHash (const std::string& str); unsigned int APHash (const std::string& str); #endif

GeneralHashFunctions_-_CPP/HashTest.cpp

GeneralHashFunctions_-_CPP/HashTest.cpp

/*
 **************************************************************************
 *                                                                        *
 *           General Purpose Hash Function Algorithms Test                *
 *                                                                        *
 * Author: Arash Partow - 2002                                            *
 * URL: http://www.partow.net                                             *
 * URL: http://www.partow.net/programming/hashfunctions/index.html        *
 *                                                                        *
 * Copyright notice:                                                      *
 * Free use of the General Purpose Hash Function Algorithms Library is    *
 * permitted under the guidelines and in accordance with the MIT License. *
 * http://www.opensource.org/licenses/MIT                                 *
 *                                                                        *
 **************************************************************************
*/


#include   < iostream >
#include   < string >

#include   "GeneralHashFunctions.h"

int  main ( int  argc ,   char *  argv [])
{
    const  std :: string key  =   "abcdefghijklmnopqrstuvwxyz1234567890" ;

   std :: cout  <<   "General Purpose Hash Function Algorithms Test"   <<  std :: endl ;
   std :: cout  <<   "By Arash Partow - 2002        "   <<  std :: endl ;
   std :: cout  <<   "Key: "                            <<  key            <<  std :: endl ;
   std :: cout  <<   " 1. RS-Hash Function Value:   "   <<   RSHash    ( key )   <<  std :: endl ;
   std :: cout  <<   " 2. JS-Hash Function Value:   "   <<   JSHash    ( key )   <<  std :: endl ;
   std :: cout  <<   " 3. PJW-Hash Function Value:  "   <<   PJWHash   ( key )   <<  std :: endl ;
   std :: cout  <<   " 4. ELF-Hash Function Value:  "   <<   ELFHash   ( key )   <<  std :: endl ;
   std :: cout  <<   " 5. BKDR-Hash Function Value: "   <<   BKDRHash ( key )   <<  std :: endl ;
   std :: cout  <<   " 6. SDBM-Hash Function Value: "   <<   SDBMHash ( key )   <<  std :: endl ;
   std :: cout  <<   " 7. DJB-Hash Function Value:  "   <<   DJBHash   ( key )   <<  std :: endl ;
   std :: cout  <<   " 8. DEK-Hash Function Value:  "   <<   DEKHash   ( key )   <<  std :: endl ;
   std :: cout  <<   " 9. FNV-Hash Function Value:  "   <<   FNVHash   ( key )   <<  std :: endl ;
   std :: cout  <<   "10. BP-Hash Function Value:   "   <<   BPHash    ( key )   <<  std :: endl ;
   std :: cout  <<   "11. AP-Hash Function Value:   "   <<   APHash    ( key )   <<  std :: endl ;

    return   1 ;
}

GeneralHashFunctions_-_CPP/Makefile

# # General Hash Function Algorithms # By Arash Partow - 2000 # # URL: http://www.partow.net/programming/hashfunctions/index.html # # Copyright Notice: # Free use of this library is permitted under the # guidelines and in accordance with the MIT License. # http://www.opensource.org/licenses/MIT # COMPILER = -c++ OPTIONS = -ansi -pedantic -Wall -o OPTIONS_LIBS = -ansi -pedantic -Wall -c LINKER_OPT = -L/usr/lib -lstdc++ all: GeneralHashFunctions.o HashTest GeneralHashFunctions.o: GeneralHashFunctions.cpp GeneralHashFunctions.h $(COMPILER) $(OPTIONS_LIBS) GeneralHashFunctions.cpp HashTest: GeneralHashFunctions.cpp HashTest.cpp $(COMPILER) $(OPTIONS) HashTest HashTest.cpp GeneralHashFunctions.o $(LINKER_OPT) clean: rm -f core *.o *.bak *stackdump *# # # The End ! #