# Brute Force Perfect Hash with GPU?

This topic is 2167 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Any brute force Multiply-Add-Shift lib to calculate a perfect hash for ~50 unqiue integers?

I can Multiply-Shift on the CPU but throwing the other unknown in just slows it down too much.

gperf works well but I'd like something with fewer lookup tables.

I'm grabbing the Cuda SDK/Thrust tonite.

( sorry if this is in the wrong section )

Edited by aqrit

##### Share on other sites
Why do you need a perfect hash on merely 50 integers?

##### Share on other sites

Why do you need a perfect hash on merely 50 integers?

Indeed, and equally curiously, why would any mention of the GPU come into it?

I get the impression that what you are actually after is a "minimal perfect hash".

http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function

Again, the question comes up... why?

##### Share on other sites

Wouldn't that just be a count of unique integers? So sort the numbers, and remove duplicates. The hash function is to find the element in the array, and get it's index.

##### Share on other sites

Wouldn't that just be a count of unique integers? So sort the numbers, and remove duplicates. The hash function is to find the element in the array, and get it's index.

That would get the job done, but being O(n) would of course defeat the purpose of it being a hash.

I'm still wondering if this is just a self-educational thing, or whether the poster believes that a minimal perfect hash is necessary when it almost certainly isn't.

##### Share on other sites

Wouldn't that just be a count of unique integers? So sort the numbers, and remove duplicates. The hash function is to find the element in the array, and get it's index.

That would get the job done, but being O(n) would of course defeat the purpose of it being a hash.

I'm still wondering if this is just a self-educational thing, or whether the poster believes that a minimal perfect hash is necessary when it almost certainly isn't.

It's O(log(N)). Although with 50 integers it hardly matters.

• 12
• 33
• 12
• 15
• 15