Have Geek Brain

Is there any function in C ++ that calculates the footprint or hash of a string that must be at least 64 bits wide?

is there any function in C ++ that calculates the fingerprint or hash of a string that must be at least 64 bits?

I want to replace mine unordered_map<string, int>

with unordered_map<long long, int>

.

Given the answers I get (thanks to the Stack Overflow community ...) the technique I am describing is not known. The reason I want to get an unordered fingerprint card instead of lines is space and speed. The second map does not need to store rows, and it does not take extra extra cache misses when performing a search to retrieve those rows. The only drawback is the low probability of collision. Therefore, the key must be 64 bits: the probability 2 ^ (- 64) is basically impossible. Of course this is based on a good hash function, which is why my question is looking for.

Thanks again, Stack Overflowers.

+1


a source to share


4 answers


C ++ has no built-in 128-bit type and has no built-in hashing support. Such hashing extensions are supposed to be added to TR1, but as far as I know, 128 bit ints are not supported by many of my compilers. (Microsoft supports the type __int128

- x64 platforms only)

I would expect the functions included in unordered_map to be faster anyway.



If you really want to do this, MD5 provides a nice 128-bit hash.

+2


a source


unordered_map

always hashes the key to a variable size_t

. This is independent of the key type and only depends on the architecture you are working with.



+3


a source


If you want to match any string to a unique integer:

typedef std::map<string,long long> Strings;
static Strings s_strings;
long long s_highWaterMark = 0;
long long my_function(const string& s)
{
  Strings::const_iterator it = s_strings.find(s);
  if (it != s_strings.end())
  {
    //we've previously returned a fingerprint for this string
    //now return the same fingerprint again
    return it->second;
  }
  //else new fingerprint
  long long rc = ++s_highWaterMark;
  //... remember it for next time
  s_strings.insert(Strings::value_type(s, rc));
  //... and return it this time
  return rc;
}
+2


a source


What exactly are you trying to achieve? Your map will not perform better with a "large" hash function. It doesn't matter anyway.

0


a source






More articles:


All Articles