Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

c++ hash function for an int array

Tags:

c++

hash

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.

like image 407
gewizz Avatar asked Aug 22 '11 14:08

gewizz


People also ask

How do you hash an array of ints?

The most commonly used method for hashing integers is called modular hashing: we choose the array size M to be prime, and, for any positive integer key k, compute the remainder when dividing k by M. This function is very easy to compute (k % M, in Java), and is effective in dispersing the keys evenly between 0 and M-1.

Can I hash an array?

While an array can be used to construct hash tables, array indexes its elements using integers. However, if we want to store data and use keys other than integer, such as 'string', we may want to use dictionary. Dictionaries in Python are implemented using hash tables.

What is a good hash function for integers?

A good hash function to use with integer key values is the mid-square method. The mid-square method squares the key value, and then takes out the middle r bits of the result, giving a value in the range 0 to 2r−1. This works well because most or all bits of the key value contribute to the result.

Is there a hash function in C?

A Hash Table in C/C++ (Associative array) is a data structure that maps keys to values. This uses a hash function to compute indexes for a key. Based on the Hash Table index, we can store the value at the appropriate location.


1 Answers

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

like image 59
vromanov Avatar answered Sep 24 '22 17:09

vromanov