myhash - library with hash functions

Question

I had a file with 2 hash functions (DJB2, NMEA0183), written in C-like way, e.g. something like this:

uint8_t NMEA0183Hash(const char *s, size_t const size){
    uint8_t hash = 0;

    for(const char *c = s; c < s + size; ++c)
        hash = hash ^ (uint) c;

    return hash;
}

Everything looked nice. However, I needed those to be functors. I also wanted to see how FNV1 will compare, for this reason I refactor a bit.

Then I saw I have one and same loop in all functors. Then I saw how one can optimize FNV1 to avoid multiplication. I refactored bit more and result is this monstrosity.

I did not test final version, but gcc and clang clean the abstractions and result code is same as standard functions I started with.

Speed is the same, too. Usage is almost the same. Note I do like <uint64_t> part.

uint64_t const x = FNV1AHash<uint64_t>()("Hello");

Note - I did not tested SDBM.

Let me know if I can simplify it.

myhash.h

#include <cstdint>
#include <cstdlib>  // size_t

// DJB Hash function from CDB
template <typename uint>
struct DJB2Hash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};

template <typename uint>
struct DJB2AHash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};



// SDBM is reimplementation of NDBM
template <typename uint>
struct SDBMHash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};



// FNV1 http://www.isthe.com/chongo/tech/comp/fnv/index.html
template <typename uint>
struct FNV1Hash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};

template <typename uint>
struct FNV1AHash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};



// NMEA0183
struct NMEA0183Hash{
    using uint = uint8_t;

    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};

myhash.cc

#include "myhash.h"

//#include <cstdio>

namespace{

    template <class HASH>
    class Hash_base_{
    public:
        using uint = typename HASH::uint;

        constexpr static uint offset_basis = HASH::offset_basis;

    public:
        uint calc(const char *s) const{
            uint hash = offset_basis;

            for(const char *c = s; *c; ++c)
                h_.add(hash, *c);

            return hash;
        }

        uint calc(const char *s, size_t const size) const{
            uint hash = offset_basis;

            for(const char *c = s; c < s + size; ++c)
                h_.add(hash, *c);

            return hash;
        }

    private:
        HASH h_;
    };



    // =====================================



    template <typename UINT>
    struct DJB2_base_{
        using uint = UINT;

        constexpr static uint offset_basis = 5381u;
    };

    template <typename uint>
    struct DJB2_ : public DJB2_base_<uint>{
        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) + (uint) c;
        }
    };

    template <typename uint>
    struct DJB2A_ : public DJB2_base_<uint>{
        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) ^ (uint) c;
        }
    };



    // =====================================



    template <typename UINT>
    struct SDBM_{
        using uint = UINT;

        constexpr static uint offset_basis = 0;

        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) ^ (uint) c;
        }
    };



    // =====================================



    template <typename UINT, UINT BASIS, UINT PRIME>
    struct FNV1_base_{
        using uint = UINT;

        constexpr static uint offset_basis = BASIS;
        constexpr static uint fnv_prime    = PRIME;

        void calc1(uint &hash, char const c) const{
            hash ^= (uint) c;
        }

        void calc2(uint &hash, char const c) const{
            hash *= fnv_prime;
        }
    };

    template <typename UINT>
    struct FNV1_base2_;

    template <>
    struct FNV1_base2_<uint32_t> : public FNV1_base_<uint32_t, 2166136261ul, 16777619ul>{
        constexpr static unsigned char ZERO_HASH[] = { 0x01, 0x47, 0x6c, 0x10, 0xf3, 0x00 };

        void calc2(uint &hash, char const c) const{
            (void)ZERO_HASH;

            // multiply by the 32 bit FNV_prime prime mod 2^32
            hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
        }
    };

    template <>
    struct FNV1_base2_<uint64_t> : public FNV1_base_<uint64_t, 14695981039346656037ull, 1099511628211ull>{
        constexpr static unsigned char ZERO_HASH[] = { 0x92, 0x06, 0x77, 0x4c, 0xe0, 0x2f, 0x89, 0x2a, 0xd2, 0x00 };

        void calc2(uint &hash, char const c) const{
            (void)ZERO_HASH;

            // multiply by the 64 bit FNV_prime prime mod 2^64
            hash += (hash << 1) + (hash << 4) + (hash << 5) +
                (hash << 7) + (hash << 8) + (hash << 40);
        }
    };

    // uint128_t
    // 144066263297769815596495629667062367629
    // 309485009821345068724781371

    template <typename uint>
    struct FNV1_ : public FNV1_base2_<uint>{
        void add(uint &hash, char const c) const{
            this->calc1(hash, c);
            this->calc2(hash, c);
        }
    };

    template <typename uint>
    struct FNV1A_ : public FNV1_base2_<uint>{
        void add(uint &hash, char const c) const{
            this->calc2(hash, c);
            this->calc1(hash, c);
        }
    };



    // =====================================



    struct NMEA0183_{
        using uint = uint8_t;

        constexpr static uint offset_basis = 0;

        void add(uint &hash, char const c) const{
            hash = hash ^ (uint) c;
        }
    };

} // namespace



// =====================================

template <typename uint>
uint DJB2Hash<uint>::operator()(const char *s) const{
    Hash_base_<DJB2_<uint> > hb;
    return hb.calc(s);
}

template <typename uint>
uint DJB2Hash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<DJB2_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

template <typename uint>
uint DJB2AHash<uint>::operator()(const char *s) const{
    Hash_base_<DJB2A_<uint> > hb;
    return hb.calc(s);
}

template <typename uint>
uint DJB2AHash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<DJB2A_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

template <typename uint>
uint SDBMHash<uint>::operator()(const char *s) const{
    Hash_base_<SDBM_<uint> > hb;
    return hb.calc(s);
}

template <typename uint>
uint SDBMHash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<SDBM_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

template <typename uint>
uint FNV1Hash<uint>::operator()(const char *s) const{
    Hash_base_<FNV1_<uint> > hb;

    return hb.calc(s);
}

template <typename uint>
uint FNV1Hash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<FNV1_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

template <typename uint>
uint FNV1AHash<uint>::operator()(const char *s) const{
    Hash_base_<FNV1A_<uint> > hb;
    return hb.calc(s);
}

template <typename uint>
uint FNV1AHash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<FNV1A_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

uint8_t NMEA0183Hash::operator()(const char *s) const{
    Hash_base_<NMEA0183_> hb;
    return hb.calc(s);
}

uint8_t NMEA0183Hash::operator()(const char *s, size_t const size) const{
    Hash_base_<NMEA0183_> hb;
    return hb.calc(s, size);
}

// =====================================

template struct DJB2Hash<uint32_t>;
template struct DJB2Hash<uint64_t>;

template struct DJB2AHash<uint32_t>;
template struct DJB2AHash<uint64_t>;

template struct SDBMHash<uint32_t>;
template struct SDBMHash<uint64_t>;

template struct FNV1Hash<uint32_t>;
template struct FNV1Hash<uint64_t>;

template struct FNV1AHash<uint32_t>;
template struct FNV1AHash<uint64_t>;

Toby Speight · Accepted Answer · 2022-12-05 16:12:53Z

The first thing that sprung out at me is that you are missing an include guard. You may have simply not posted it, so ignore that if that is the case.

First, a word about the API. Generally this is fine, but it seems clunky. It may be sensible to provide a general hash wrapper that chooses one specific hash function and then uses that.

For example:

template <typename uint, typename Hash = DJB2Hasher<uint>>
struct Hasher {
    uint operator()(const char *s) const {
      return Hash(s);
    }
    uint operator()(const char *s, size_t const size) const {
      return Hash(s, size);
    }
};

In the same vein, it may be sensible to have wrapper functions that provide syntactic sugar. For example

template <typename uint>
struct DJB2Hasher{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};

template <typename uint>
uint hashDJB2(const char *s) {
  DJB2Hasher hasher;
  return hasher(s, size);
}

template <typename uint>
uint hashDJB2(const char *s, size_t const size) {
  DJB2Hasher hasher;
  return hasher(s, size);
}

A few things about names; struct / class names should be nouns and functions verbs. Now, yes hash is both to hash (verb) and a hash (noun); in this context, without getting to much into Kingom of the Nouns, I would prefer Hasher for the class and hash for the function.

To me names like Hash_base_ don't look nice. I would rather use HashBase, Hash_Base or even hash_base. Being consistent with your naming makes code look nicer.

The same can be said about leading and trailing underscores; with very few exceptions, don't do that. It makes things less readable; especially once you add the arrow or dot operators.

Hash_base_->add(foo);
hash_base->add(foo);

Why are you hiding the implementation of the hashes inside the *.cc file? The moment you use templates, jumping though hoops to hide the implementation in a cpp/cc file makes little sense.

The way you lay it out means that the templates are almost not used. If the hash algorithms only work for specific sizes of integers, then you probably should just expose without jumping though template hoops.

What looks better to you?

uint64_t const x = FNV1AHash<uint64_t>()("Hello");
uint64_t const y = FNV1AHash64()("Hello");

I like the way you reduce duplicated code with the help of Hash_base_. Now your approach to using classes is fine, but it feels like the classes don't pull their weight.

Have you considered using functions?

Now the downside is that you need to derive offset_basis somehow. Traits may help.

Just an idea, but how about this:

    template <typename uint> using HashFunction = uint (*) (const uint, const char); 

    template <typename uint, HashFunction func>
    struct HashTraits;

    template <typename uint, djb2a<uint>>
    struct HashTraits 
    {
        static constexpr offset_basis = 5381u;
    };

    template <typename uint>
    uint djb2a(const uint hash, const char c)
    {
        return ((hash << 5) + hash) ^ static_cast<uint>(c);
    };

    template <typename uint, HashFunction func>
    class Hasher
    {
    public:
        uint calc(const char* str) const
        {
            uint hash = HashTraits<uint, func>::offset_basis;

            for(const char *c = str; *c; ++c)
            {
                hash = func(hash, *c);
            }

            return hash;
        }
        // removed other calc for brevity
    };

Just an idea to ponder. Not everything needs to be a class and this also heeds a usable hash function.

A few final words:

Please put curly braces around each condition and loop. Not doing so is a common way to introduce errors when adding to code.
Use the C++ casts, such as static_cast. They make sure you are expressing the right casing behavior.
No big deal in your code, but using single character arguments, such as c or s can quickly lead to confusion.

Nick · Accepted Answer · 2016-12-13 15:04:56Z

Here is what I came up.

It is header only library now.

I believe is much more clear like this.

myhash.h

#ifndef MY_HASH_H_
#define MY_HASH_H_

#include <cstdint>
#include <cstdlib>  // size_t

#include "myhash_impl.h"

namespace myhash{

// DJB Hash function from CDB
template <typename uint>
using DJB2 = impl::MyHashBase<impl::DJB2<uint> >;

template <typename uint>
using DJB2A = impl::MyHashBase<impl::DJB2A<uint> >;


// SDBM is reimplementation of NDBM
template <typename uint>
using SDBM = impl::MyHashBase<impl::SDBM<uint> >;


// FNV1 http://www.isthe.com/chongo/tech/comp/fnv/index.html
template <typename uint>
using FNV1 = impl::MyHashBase<impl::FNV1<uint> >;

template <typename uint>
using FNV1A = impl::MyHashBase<impl::FNV1A<uint> >;


// NMEA0183
using NMEA0183 = impl::MyHashBase<impl::NMEA0183>;

} // namespace

#endif

myhash_impl.h

namespace myhash{
namespace impl{
namespace {

    template <class HASH>
    class MyHashBase{
    public:
        using uint = typename HASH::type;

        constexpr static uint offset_basis = HASH::offset_basis;

    public:
        uint operator()(const char *s) const{
            uint hash = offset_basis;

            for(const char *c = s; *c; ++c)
                h_.add(hash, *c);

            return hash;
        }

        uint operator()(const char *s, size_t const size) const{
            uint hash = offset_basis;

            for(const char *c = s; c < s + size; ++c)
                h_.add(hash, *c);

            return hash;
        }

    private:
        HASH h_;
    };

    // =====================================

    template <typename uint>
    struct DJB2_base_{
        using type = uint;

        constexpr static uint offset_basis = 5381u;
    };

    template <typename uint>
    struct DJB2 : public DJB2_base_<uint>{
        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) + (uint) c;
        }
    };

    template <typename uint>
    struct DJB2A : public DJB2_base_<uint>{
        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) ^ (uint) c;
        }
    };

    // =====================================

    template <typename uint>
    struct SDBM{
        using type = uint;

        constexpr static uint offset_basis = 0;

        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) ^ (uint) c;
        }
    };

    // =====================================

    struct NMEA0183{
        using type = uint8_t;

        constexpr static uint8_t offset_basis = 0;

        void add(uint8_t &hash, char const c) const{
            hash = hash ^ (uint8_t) c;
        }
    };

    // =====================================

    template <typename uint, uint BASIS, uint PRIME>
    struct FNV1_base_{
        using type = uint;

        constexpr static uint offset_basis = BASIS;
        constexpr static uint fnv_prime    = PRIME;

        void calc1(uint &hash, char const c) const{
            hash ^= (uint) c;
        }

        void calc2(uint &hash, char const c) const{
            hash *= fnv_prime;
        }
    };

    template <typename uint>
    struct FNV1_base2_;

    template <>
    struct FNV1_base2_<uint32_t> : public FNV1_base_<uint32_t, 2166136261ul, 16777619ul>{
        constexpr static unsigned char ZERO_HASH[] = { 0x01, 0x47, 0x6c, 0x10, 0xf3, 0x00 };

        void calc2(uint32_t &hash, char const c) const{
            (void)ZERO_HASH;

            // multiply by the 32 bit FNV_prime prime mod 2^32
            hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
        }
    };

    template <>
    struct FNV1_base2_<uint64_t> : public FNV1_base_<uint64_t, 14695981039346656037ull, 1099511628211ull>{
        constexpr static unsigned char ZERO_HASH[] = { 0x92, 0x06, 0x77, 0x4c, 0xe0, 0x2f, 0x89, 0x2a, 0xd2, 0x00 };

        void calc2(uint64_t &hash, char const c) const{
            (void)ZERO_HASH;

            // multiply by the 64 bit FNV_prime prime mod 2^64
            hash += (hash << 1) + (hash << 4) + (hash << 5) +
                (hash << 7) + (hash << 8) + (hash << 40);
        }
    };

    // uint128_t
    // 144066263297769815596495629667062367629
    // 309485009821345068724781371

    template <typename uint>
    struct FNV1 : public FNV1_base2_<uint>{
        void add(uint &hash, char const c) const{
            this->calc1(hash, c);
            this->calc2(hash, c);
        }
    };

    template <typename uint>
    struct FNV1A : public FNV1_base2_<uint>{
        void add(uint &hash, char const c) const{
            this->calc2(hash, c);
            this->calc1(hash, c);
        }
    };

} // namespace anonymous
} // namespace impl
} // namespace

Just rewriting the OPs code is not a code review. It doesn't say why or what was good/bad. — Emily L., Commented Jan 12, 2017 at 16:07
@EmilyL. point well taken. It was mostly about code repetition vs boilerplate code. I still not sure if it is better, but I did include - "I believe is much more clear like this." — Nick, Commented Jan 13, 2017 at 7:32
Thanks for posting this code. It's a good idea to summarise which changes you made, and why - a self-answer ought to review the code, just like any other answer. — Toby Speight, Commented Dec 5, 2022 at 16:13

Stack Exchange Network

myhash - library with hash functions

myhash.h

myhash.cc

2 Answers 2

myhash.h

myhash_impl.h

Your Answer

Not the answer you're looking for? Browse other questions tagged
c++
c++11
hashcode
or ask your own question.

Hot Network Questions

myhash - library with hash functions

myhash.h

myhash.cc

2 Answers 2

myhash.h

myhash_impl.h

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++c++11hashcode or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c++
c++11
hashcode
or ask your own question.