5
\$\begingroup\$

I usually take my school code as a playground to mess around with things. I was given a bunch of premade hash functions and had to test their output and find when they reach a specific lower range. Since the functions all have the same structure, I made a check function that uses a function pointer parameter(I think this is the most efficient way to deal with this problem?). Which I'm iterating through the potential keys to feed to all of the functions it I wanted it to stop at the first one of each, but couldn't think of a way to do so without using 11 individual flags or for loops. I've never messed with bitmasks (I specifically only remember the gist of them because there was a couple commands in quake3 that used them!), but I did that instead and it turned out to not be as pretty/elegant as I thought it would in practice.

in short:

How would you approach the assignment "Using the given 11 hash functions, find each of their first 'low' output?"

void findLowHash();
bool foundLow(unsigned int (*hash)(const std::string &key), std::string key);

void findLowHash() {
  string key;
  key.push_back(0);
  int mask = 2047;
  for (int i = 0; i < 100000; ++i) {
    incrStr(key);
    carryStr(key);
    if (mask == 0)
      break;
    if (mask >> 0 & 1) {
      if (foundLow(RSHash, key)) {
        mask -= 1;
        cout << "RSHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 1 & 1) {
      //cout<<JSHash(key)<<" "<<key<<endl;
      if (foundLow(JSHash, key)) {
        mask -= 2;
        cout << "JSHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 2 & 1) {
      if (foundLow(PJWHash, key)) {
        mask -= 4;
        cout << "PJWHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 3 & 1) {
      if (foundLow(ELFHash, key)) {
        mask -= 8;
        cout << "ELFHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 4 & 1) {
      if (foundLow(BKDRHash, key)) {
        mask -= 16;
        cout << "BKDRHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 5 & 1) {
      if (foundLow(SDBMHash, key)) {
        mask -= 32;
        cout << "SDBMHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 6 & 1) {
      if (foundLow(DJBHash, key)) {
        mask -= 64;
        cout << "DJBHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 7 & 1) {
      if (foundLow(DEKHash, key)) {
        mask -= 128;
        cout << "DEKHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 8 & 1) {
      if (foundLow(FNVHash, key)) {
        mask -= 256;
        cout << "FNVHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 9 & 1) {
      if (foundLow(BPHash, key)) {
        mask -= 512;
        cout << "BPHash"
             << " " << mask << endl;
      }
    }
    if (mask >> 10 & 1) {
      if (foundLow(APHash, key)) {
        mask -= 1024;
        cout << "APHash"
             << " " << mask << endl;
      }
    }
  }
}

bool foundLow(unsigned int (*hash)(const std::string &key), std::string key) {
  if ((*hash)(key) < 10000) {
    std::cout << "key: " << key << " Output:" << ((*hash)(key)) << " ";
    return true;
  }
  return false;
}
\$\endgroup\$
5
\$\begingroup\$

Your code does seem open to some improvement. Right now, you're not really getting much good out of using a pointer to a function. You could just about as well invoke each hash function directly in findLowHash as call it via a pointer in foundLow.

In this case, we have a number of functions that all have the same signature, so we can create an array of the pointers to functions. Of course, array should also set off alarm bells--you should almost always prefer std::array or std::vector. In this case, I'll use st::vector, but if you're using a compiler new enough to include it, std::array would be an excellent choice as well.

typedef unsigned int (*hash)(std::string const &key);

std::vector<hash> hashes{
    RSHash, JSHash, PJWHash, ELFHash, BKDRHash, 
    SDBMHash, DJBHash, DEKHash, FNVHash, BPHash, APHash
};

Depending on the age of compiler you're using, it might not support the braced init-list like I've used above. At that point, it's open to argument that (under the circumstances) it would be easier to use an actual array instead.

In any case, once you have your pointers to functions in something you can index like array, you can use a loop to walk through the array of functions, and use each function in turn:

for (int h=0; h<hashes.size(); h++)
    for (int i=0; i<100000; i++) {
       incrStr(key);
       carryStr(key);
       if (hashes[h](key) < 10000) {
           std::cout << // ...
           break; // breaks inner loop, so goes to testing next hash function
       }
    }

Again, if you have a new enough compiler (C++11) available, you can make the outer loop a little prettier using a range-based for loop:

for (auto &&hash : hashes) 
    // ...
    if (hash(key) < 10000) 
        // ...

Once you've done that, there are a few more fairly obvious points, such as replacing the magic numbers like 100000 and 10000 with defined constants with more meaningful names.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.