Using hashes instead of enums.

Post those lines of code you feel like sharing or find what you require for your project here; or simply use them as tutorials.
Post Reply
Josie
Posts: 44
Joined: Sat Jul 25, 2009 4:08 am
Location: Griffin, Georgia, US
Contact:

Using hashes instead of enums.

Post by Josie »

I wrote up a nice blog today about using hashes instead of enums for things like Object or Event types. It's saved me some heartache. The post is at my blog with syntax highlighting and whatnot, but I've copied and pasted verbatim for you here. I hope someone finds this useful.

-----------------------------------------------------------------------------------

For my Asteroids clone, I found myself at odds with my Object class. It had a nice enum called 'Type' that contained the natural "OBJ_ASTEROID", "OBJ_SHIP", etc. However, I found it to be a pain that every time I added a new object, all those other object would have to be recompiled, and I can greatly see this being a huge problem in a game that has more than 5 objects. Taking advice from "Game Coding Complete" (which is a fantastic book, by the way), I decided to just chunk the enum out of the window, and use hashes instead. Because Pheonix uses boost (and by extension, Asteroids uses boost), I decided to write my hash key class using boost. Because of this, it's rather small, but incredibly useful. Here's the entire header:

Code: Select all

#ifndef __HASH_KEY_H__
#define __HASH_KEY_H__

#include <boost/functional/hash.hpp>
#include <boost/algorithm/string.hpp>
#include <string>

class HashKey
{
public:

    HashKey()
        : hash(0)
    {}

    HashKey( const std::string&  _s )
        : hash( hash_function( _s ) )
    {}

    ~HashKey()
    {}

    /*!
        @brief The hash function for hash keys.
        This is the central function of this class,
        this essentially takes a string and turns it
        into a number. Also note that it lowercases
        the string, this is to avoid programmers
        mixing cases.
    */
    static size_t hash_function( const std::string& _s )
    {
        static boost::hash< std::string> string_hash;
        std::string tempstr( _s );
        boost::to_lower( tempstr );
        return string_hash( tempstr );
    }

    //! Standard assignment from string.
    const HashKey& operator = ( const std::string& _s )
    {
        (*this) = HashKey( _s );
        return *this;
    }

    //! Standard comparison.
    bool operator == ( const HashKey& other ) const
    {
        return hash == other.hash;
    }

    //! Comparison against a string, it hashes the string then compares.
    bool operator == ( const std::string& other ) const
    {
        return hash == hash_function( other );
    }

    //! Implicit conversion to size_t, so that we can easy print, store, or serialize the key.
    operator const std::size_t& ()
    {
        return hash;
    }

private:
    std::size_t hash;
};

#endif;
Pretty simple, eh? I choose to make it lowercase the strings before hashing because I have this bad tendency to forgot to capitalize things right.

Here's a small test of the class:

Code: Select all

#include <hashkey.hpp>
#include <iostream>


int main()
{
    HashKey test;
    test = "Hello, World!";
    std::cout<<test<<std::endl;
    std::cout<<HashKey("Hello, World!")<<std::endl;
    std::cout<<HashKey("helLo, woRld!")<<std::endl;
    std::cout<< ( test == "helLo, woRld!" ? "True" : "False" )<< std::endl;
    std::cin.get();
    return 0;
}

I hope that you can find some neat uses for this little snippet, it has saved me compile time all over the place (and it serializes well). Here's some snippets of how I used it Asteroids:

Code: Select all

ShipObject( ObjectManager& _m ):
: GameObject(_m), type( "ShipObject" )
{}

..............................................

collision( shared_ptr<GameObject> other )
{
    if( other.getType() == "ShipObject" )
    {
        ...
    }
}

..............................................

void onEvent( const Event& event )
{
    signals[ event.type ].sig();
}
drr00t
Posts: 14
Joined: Wed Aug 05, 2009 2:11 pm
Location: Brasilia/DF - Brasil

Post by drr00t »

Hi,

Nice work, i using something like this on my engine, but i use SuperFastHash from Paul Hsieh site, that is very fast hash to variable string size.

Mode information here: http://www.azillionmonkeys.com/qed/hash.html

Code: Select all

#include "pstdint.h" /* Replace with <stdint.h> if appropriate */
#undef get16bits
#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
  || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
#define get16bits(d) (*((const uint16_t *) (d)))
#endif

#if !defined (get16bits)
#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                       +(uint32_t)(((const uint8_t *)(d))[0]) )
#endif

uint32_t SuperFastHash (const char * data, int len) {
uint32_t hash = len, tmp;
int rem;

    if (len <= 0 || data == NULL) return 0;

    rem = len & 3;
    len >>= 2;

    /* Main loop */
    for (;len > 0; len--) {
        hash  += get16bits (data);
        tmp    = (get16bits (data+2) << 11) ^ hash;
        hash   = (hash << 16) ^ tmp;
        data  += 2*sizeof (uint16_t);
        hash  += hash >> 11;
    }

    /* Handle end cases */
    switch (rem) {
        case 3: hash += get16bits (data);
                hash ^= hash << 16;
                hash ^= data[sizeof (uint16_t)] << 18;
                hash += hash >> 11;
                break;
        case 2: hash += get16bits (data);
                hash ^= hash << 11;
                hash += hash >> 17;
                break;
        case 1: hash += *data;
                hash ^= hash << 10;
                hash += hash >> 1;
    }

    /* Force "avalanching" of final 127 bits */
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;

    return hash;
}

Josie
Posts: 44
Joined: Sat Jul 25, 2009 4:08 am
Location: Griffin, Georgia, US
Contact:

Post by Josie »

Excellent- I considered using that particular hash function, but being as I'm as I wanted to make this as 'simple' as possible, I just went with boost's (Which I'm sure is reasonably fast ). It should be trival to drop that hash function in instead of boost::hash<string>.
Post Reply