A Simple Hash Map

Hash maps are used to store a mapping from one thing to another. In videogames they can be used to safely keep handles to objects that could be destroyed at any time. A unique handle is assigned to each game object and mapped to it’s pointer via a hash map. We can keep track of objects using handles instead of pointers so when an object is destroyed it doesn’t have to notify anyone else, just removing it’s handle from the hash map is enough. This is more or less the same method we’ve used on many of the industry titles I worked on (Starhawk, Red Faction, etc). The downside is of course is a longer look-up time, but I’ve found with proper engineering it’s negligible.

I am in the process of developing a new game engine for Sifteo Cubes, but the Sifteo SDK does not include a hash map. I was not satisfied with any of the implementations that I found online so I wrote my own. I based my hash map off this example, but fixed a few issues and cleaned it up. I mainly wanted to make it as simple and bulletproof as possible. I also tried to match up the syntax with STL’s hash_map.

The downside with this simple method is that if a key is not in the hash map it must search through the entire map to verify. There are many ways to alleviate that, for example implementing a linked list like structure to resolve hash collisions, but that would also hurt caching and add another level of complexity. For hashing the key to get a start index, I’m multiplying it by a large prime number that was recommended on stack overflow. This is done in order to help spread out the keys, but I’m sure that could also be improved.

// Simple Hash Map - Maps an unsigned int to an object pointer 

template < class T, unsigned maxMapSize >
struct HashMap 
{
    HashMap() { clear(); }

    void clear()
    {
        mapSize = 0;
        for (unsigned i = 0; i < maxMapSize; ++i)
        {
            map[i].key = 0;
            map[i].value = NULL;
        }
    }

    T* find(unsigned key)
    {
        if (!key)
            return NULL; // invalid key always returns NULL

        // check every key until we find a match
        unsigned i = hashKey(key) % maxMapSize;
        const unsigned iStart = i;
        do
        {
            if (map[i].key == key)
                return map[i].value;
            i = (i + 1) % maxMapSize;
        }
        while (i != iStart);

        return NULL;
    }

    void insert(unsigned key, T* value)
    {
        ASSERT(key && value && !full() && !find(key));

        unsigned i = hashKey(key) % maxMapSize;
        while (map[i].value)
            i = (i + 1) % maxMapSize;

        map[i].key = key;
        map[i].value = value;
        ++mapSize;
    }

    void erase(unsigned key)
    {
        ASSERT(key && find(key));

        unsigned i = hashKey(key) % maxMapSize;
        while (map[i].key != key)
            i = (i + 1) % maxMapSize;

        map[i].key = 0;
        map[i].value = NULL;
        --mapSize;
    }

    unsigned size()     const { return mapSize; }
    unsigned max_size() const { return maxMapSize; }
    bool empty()        const { return size() == 0; }
    bool full()         const { return size() == max_size(); }

private:

    // rehash the key so we make more efficient use of the map
    unsigned hashKey(unsigned key) { return key*2654435761; }

    struct HashEntry { unsigned key; T* value; };
    HashEntry map[maxMapSize];
    unsigned mapSize;
};
This entry was posted in Game Dev and tagged . Bookmark the permalink.

Leave A Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.