Hash Map slower than Map.

[Amit Bhatia]

Hi,
I am trying to write a hash function that works on a pair of integers.

so I have a pair<int,intof integers. Let the first element be called
"a" and second as "b".

I know before hand that:

0<=a<30
-2^a<=b<=2^a-1.

In more detail, I am using this to keep a record of lattice points seen
on a multi resolution hierarchical grid. A resolution level "l" has
2^{l*d} elements where d is the dimension of the space.

Also, there can be at most two different instantiations of the same
region in the grid for my work. To distinguish them, I add +1 and put
-ve sign in front of one copy.
So <a,b>, and <a,-(b+1)represent the same region in the grid.
As a result, there can be a key <4,3and another key <4,-3>
If all the b's were >0, then I could already think of a very simple
perfect hash function:
size_t value = 1<<a+b;

However, if b<0 is also possible, then, I can only think of

size_t value;
if(b>=0) value = 1<<a+b;
else value = 2^30 + 1<<a+-(b+1); // I know a<30 for sure.

Now I used this in my code, and did some profiling and I found that I am
spending almost 80 % of the time just looking up if a key exists in this
hash map. (there are no other major calculations in the program function
where this "find" operation is called).

So for example, in one particular execution of the program, the function
which calls this key lookup is called

158905316 times and takes 100 sec (~80%) of the time.

My question is: can I do much faster than this? I am not an expert, and
I am using g++ 4.2 on a pentium 4 2.4 Ghz with 512 MB RAM. But still
this should be much faster.

What is really surprising is that if I use maps instead, they are
running faster.

So for about, 83127320 calls, I take 16.06 sec (~47.26%) if I use a stl map.

thanks,
-amit.

[Gianni Mariani]

Amit Bhatia wrote:

size_t value;
if(b>=0) value = 1<<a+b;
else value = 2^30 + 1<<a+-(b+1); // I know a<30 for sure.

This would yield very poor keys.

Why not print out the values from your hash function. Your problem is
probably there.

[Ben Rudiak-Gould]

Amit Bhatia wrote:

If all the b's were >0, then I could already think of a very simple
perfect hash function:

size_t value = 1<<a+b;

+ has higher precedence than << in C++, so the expression above means
1<<(a+b), which is probably not what you intended.

-- Ben

[Amit Bhatia]

Ben Rudiak-Gould wrote:

Amit Bhatia wrote:

>If all the b's were >0, then I could already think of a very simple
perfect hash function:

size_t value = 1<<a+b;

+ has higher precedence than << in C++, so the expression above means
1<<(a+b), which is probably not what you intended.

-- Ben

Thanks a lot. It works a lot better now. :) For the same example, for
about 83805820 calls it takes about 12.85 seconds. There are two
distinct hash maps, and each has about ~1800 objects.

I am wondering is there a better function that is even faster than what
I am doing? When b<0, since I add 2^30, it kind of takes the value to
very huge numbers. But I am not sure what can be used. Most of the
examples I have seen online talk about mapping strings to keys.

thanks,
amit.

[James Kanze]

On Oct 9, 5:52 am, Amit Bhatia <[e-mail]:

Ben Rudiak-Gould wrote:

Amit Bhatia wrote:

If all the b's were >0, then I could already think of a very simple
perfect hash function:

size_t value = 1<<a+b;

+ has higher precedence than << in C++, so the expression above means
1<<(a+b), which is probably not what you intended.

Thanks a lot. It works a lot better now. :) For the same example, for
about 83805820 calls it takes about 12.85 seconds. There are two
distinct hash maps, and each has about ~1800 objects.

I am wondering is there a better function that is even faster than what
I am doing? When b<0, since I add 2^30, it kind of takes the value to
very huge numbers.

I'm not sure about what you're doing, but if you actually have
written 2^32, the value is the constant 34 in C++. Which may
not be what you wanted.

But I am not sure what can be used. Most of the examples I
have seen online talk about mapping strings to keys.

Most hashing functions (even for strings) actually hash
sequences of unsigned integral values. In your place, I'd just
convert the two values to unsigned, then adopt one of the
classical hash codes, say by multiplying the first by a prime
number, then adding the second (e.g.: "127 * (unsigned)( a ) +
(unsigned)( b )").

Most hash tables I know have functions which allow you to verify
the distribution, but a priori, something like the above should
give very good results, and is not very expensive to calculate.
(On machines with slow multiplication, the compiler will convert
the 127*x to a left shift and a subtraction.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]