Hash table implementation for GPU [closed]

Question

I am looking for a hash table implementation that I can use for CUDA coding. are there any good one's out there. Something like the Python dictionary . I will use strings as my keys

Answer 1

Alcantara et al have demonstrated a data-parallel algorithm for building hash tables on the GPU. I believe the implementation was made available as part of CUDPP.

That said, you may want to reconsider your original choice of a hash table. Sorting your data by key and then performing lots of queries en masse should yield much better performance in a massively parallel setting. What problem are you trying to solve?

Answer 2

When I wrote an OpenCL kernel to create a simple hash table for strings, I used the hash algorithm from Java's String.hashCode(), and then just modded that over the number of rows in the table to get a row index.

Hashing function

uint getWordHash(__global char* str, uint len) {
  uint hash = 0, multiplier = 1;
  for(int i = len - 1; i >= 0; i--) {
    hash += str[i] * multiplier;
    int shifted = multiplier << 5;
    multiplier = shifted - multiplier;
  }
  return hash;
}

Indexing

uint hash = getWordHash(word, len);
uint row = hash % nRows;

I handled collisions manually of course, and this approach worked well when I knew the number of strings ahead of time.