c++ hash function for an int array

Question

I need to specialize the hash function for unordered_map so I can use int arrays as keys. The array values are usually 0 or 1, e.g. int array = {0, 1, 0, 1}, but technically not bounded.

Can someone recommend a good hash function in this case? Alternatively, I can always convert the int array into a string and avoid specialization. But I am concerned about performance since I may have several million of these arrays.

Use or mimic Boost's "range hash". It's built up by repeatedly calling hash_combine, which is also in Boost and should really be in the standard. — Kerrek SB
– Kerrek SB, Commented Aug 22, 2011 at 14:02
If you do have several million of those arrays, I suggest new algorithms/data structures... — Blindy
– Blindy, Commented Aug 22, 2011 at 14:03
@Kerreck,boost.org/doc/libs/1_35_0/doc/html/boost/… says it is not appropriate for unordered containers. Does this not apply in my case? — gewizz
– gewizz, Commented Aug 22, 2011 at 14:10
@gewizz: that is sloppy wording. It is not appropriate to get a deterministic hash of an unordered container as a whole [the ordering could depend on the load factor and number of reallocations done]. However, of course it is appropriate to use as the element hash function to an unordered container — sehe
– sehe, Commented Aug 22, 2011 at 14:29

sehe · Accepted Answer · 2011-08-22 14:07:04Z

7

C++ TR1 contains a hash template function.

If you don't have that yet, you can use Boost Hash.

Idea for a handy helper:

#include <boost/functional/hash.hpp>

template <typename T, int N>
    static std::size_t hasharray(const T (&arr)[N])
{
     return boost::hash_range(arr, arr+N);
}

This would be (roughly?) equivalent to

 size_t seed = 0;
 for (const T* it=arr; it!=(arr+N); ++it)
     boost::hash_combine(seed, *it);
 return seed;

Don't forget to implement proper equality comparison operations if you're using this hash for lookup

answered Aug 22, 2011 at 14:07

sehe

400k49 gold badges475 silver badges673 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

outofthecave Over a year ago

I think it should be std::size_t N because std::size_t is guaranteed to be able to represent the size of the largest possible array, while int might overflow (depending on the system). Plus, it doesn't need to be a signed type.

sehe Over a year ago

@outofthecave fair points. However, unsigned is contagious and that makes it unwieldy for offsets (they can be negative, and N - 10 will just wrap around if N<10. Surprise!). Also, arrays statically typed at larger than 2³¹ elements? Those are rare. And you'd not often be hashing them, if you had them.

vromanov · Accepted Answer · 2020-12-29 18:19:02Z

7

Try to use lookup8 hash function. This function is VERY fast and good.

int key[100];
int key_size=10;
for (int i=0;i<key_size;i++) key[i]=i; //fill key with sample data
ub8 hash=hash((ub8*)key, sizeof(key[0])*key_size, 0);

UPD: Or use better function. - t1ha

edited Dec 29, 2020 at 18:19

answered Aug 22, 2011 at 18:25

vromanov

9296 silver badges11 bronze badges

4 Comments

vromanov Over a year ago

Usually hash functions are written in plain c. You can create C++ wrapper for it.

Puppy Over a year ago

Usually, hash functions are written in the language at hand.

vromanov Over a year ago

You always write function like crc32, sha, md5 or use existing well tested and hi-performance implementations? :)

vromanov Over a year ago

The function is too complex to be used at compile time

Collectives™ on Stack Overflow

c++ hash function for an int array

2 Answers 2

2 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related