3 values hashing


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: 3 values hashing

  1. #1
    Join Date
    Nov 2008
    Posts
    37

    3 values hashing

    Hello,
    I know how I can hash 2 values:
    Code:
    unsigned int 
    geo_hash::hash_value( bin_index bin ) const
    {
      return std::abs( bin.i() * 378551 + bin.j() * 63689 );
    }
    but I do not know how can I hash 3 values?

    Thank you in advance.

    Best regards

  2. #2
    Join Date
    Dec 2003
    Posts
    3,366
    that looks like you are shift + add, for example, if you need to hash 5 and 8, you multiply by 10 and add and it becomes 58 as a unique key, right? You can do the same with as many values as you like so long as they fit into the destination; for example, you can put 4 16 bit numbers into a 64 bit number by shifting (I prefer to just use the << and >> operators, but you can find the base 10 constant if you like, its the same result but I find shifting N bits to be easier to think about).

    The problem, then, is what if you have more bits of keys than destination? You cannot fit 4 32 bit numbers into 1 64 bit number, of course, so you have to "trim" the values somehow. This is where hashing actually becomes interesting, as you must now concoct a key that is as unique as you can make it yet the potential for collisions now exists (cannot do a perfect hash now) so you also have to handle that issue.

    One method that has worked well as a first cut at this problem for me is to simply use the built in random number generator against the data to make a key.
    for example, if you had the 4 32 bit numbers I mentioned, and want a 16 bit key, try this:

    srand(abs(key1/key2 + key3 - key4));
    donotuse = rand();
    actualhash = rand()%65536; //16bit key

    You can play around with the srand portion based upon any knowledge you have of the keys or a bajillion other things, this is just a concept of how to use the random numbers in this manner. Of course, this implies you are doing it by hand (which I often prefer, the STL hash stuff is very heavy handed compared to simply dropping data or pointers into an array)

    If you can, though, use the stl hash stuff, unless you *need* some sort of high speed setup. As I recall, the stl ones manage the keys and such for you so there is no need for the mess.

  3. #3
    Join Date
    Dec 2007
    Posts
    401
    > how can I hash 3 values?

    any number of integral values can be put next to each other and thought of as a sequence of bytes. and there are a number of well-known algorithms to hash a sequence of bytes: Bernstein's, FNV, Cessu, Hsieh's, and the cryptographic hashes like MD5 and SHA. it would be prudent to use a well-known algorithm that has been empirically observed to distribute hash values uniformly.

    for efficient hash table look-up, the hash function should be fast, and it should cause as few collisions as possible. the algorithms that Bob Jenkins has developed are a good choice for this. http://www.burtleburtle.net/bob/hash/doobs.html

    a couple of months back, i needed a function to generate a 32 bit hash from many 32 bit integers. here's the code for what it is worth - it is just a translation of Jenkins' C code http://www.burtleburtle.net/bob/c/lookup3.c into C++09.

    Code:
    #include <cstdint>
    #include <vector>
    #include <random>
    #include <ctime>
    #include <set>
    #include <iostream>
    
    using std::uint32_t ;
    
    inline uint32_t rotate( uint32_t x, uint32_t k )
    {
      return ( x << k ) | ( x >> ( 32U - k ) ) ;
    }
    
    inline void prelim_mix( uint32_t& a, uint32_t& b, uint32_t& c )
    {
      a -= c ; a ^= rotate( c, 4U ) ; c += b ;
      b -= a ; b ^= rotate( a, 6U ) ; a += c ;
      c -= b ; c ^= rotate( b, 8U ) ; b += a ;
      a -= c ; a ^= rotate( c, 16U ) ; c += b ;
      b -= a ; b ^= rotate( a, 19U ) ; a += c ;
      c -= b ; c ^= rotate( b, 4U ) ; b += a ;
    }
    
    inline void final_mix( uint32_t& a, uint32_t& b, uint32_t& c )
    {
      c ^= b ; c -= rotate( b, 14U ) ;
      a ^= c ; a -= rotate( c, 11U ) ;
      b ^= a ; b -= rotate( a, 25U ) ;
      c ^= b ; c -= rotate( b, 16U ) ;
      a ^= c ; a -= rotate( c, 4U ) ;
      b ^= a ; b -= rotate( a, 14U ) ;
      c ^= b ; c -= rotate( b, 24U ) ;
    }
    
    // hash a sequence of 32 bit numbers and generate a 32 bit hash
    uint32_t hash( const std::vector< uint32_t >& values )
    {
      static uint32_t seed = 0U ;
    
      std::size_t num_values = values.size() ;
      uint32_t a,b,c ;
      a = b = c = 0xdeadbeef + ( num_values << 2U ) + seed ;
    
      std::vector< uint32_t >::const_iterator iterator = values.begin() ;
    
      while( num_values > 3U )
      {
        a += iterator[0] ;
        b += iterator[1] ;
        c += iterator[2] ;
        prelim_mix( a, b, c) ;
    
        num_values -= 3U ;
        iterator += 3 ;
      }
    
      switch( num_values ) // all case statements fall through
      {
          case 3 : c += iterator[2] ;
          case 2 : b += iterator[1] ;
          case 1 : a += iterator[0] ;
                        final_mix( a, b, c ) ;
          case 0 : ;
      }
    
      return seed = c ;
    }
    
    int main() // small test driver for hash of three numbers
    {
    
       int collitions = 0 ;
       enum { N = 1024 * 1024 } ;
    
       std::mt19937 twister( std::time(0) ) ;
       std::set< uint32_t > set ;
    
       for( int i = 0 ; i < N ; ++i )
       {
            std::vector< uint32_t > vec = { twister(), twister(), twister() } ;
            if( set.insert( hash( vec ) ).second == false ) ++collitions ;
       }
    
       std::cout << "collitions: " << ( double(collitions) / N ) * 100 << " percent\n" ;
    }

Similar Threads

  1. SQL Help
    By carbon_13 in forum Database
    Replies: 14
    Last Post: 03-14-2008, 05:03 PM
  2. Replies: 0
    Last Post: 08-30-2007, 08:15 AM
  3. Replies: 0
    Last Post: 08-23-2006, 01:21 AM
  4. Replies: 0
    Last Post: 08-23-2006, 01:19 AM
  5. losing Form values from option boxes
    By Paul Klanderud in forum ASP.NET
    Replies: 2
    Last Post: 07-26-2000, 11:13 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center