   [C++] specializaing std::hash
  I was looking through the specializations for std::hash and came across:template<>class hash<_STD string>: public unary_function<_STD string, size_t>{// hash functorpublic:typedef _STD string _Kty;size_t operator()(const _Kty& _Keyval) const{// hash _Keyval to size_t value by pseudorandomizing transformsize_t _Val = 2166136261U;size_t _First = 0;size_t _Last = _Keyval.size();size_t _Stride = 1 + _Last / 10;for(; _First < _Last; _First += _Stride)_Val = 16777619U * _Val ^ (size_t)_Keyval[_First];return (_Val);}};What struck me as weird was:size_t _Stride = 1 + _Last / 10;I've never seen a hash function use variable size strides.  What would happen for large strings?  For say a string of 100 characters long, does it really only hash every 11th character?  Am I missing something here?
Quote:Original post by Ryan_001What would happen for large strings?It would use every size/10-th character.Quote:For say a string of 100 characters long, does it really only hash every 11th character?Yes.Quote:Am I missing something here?Yes - the fact that hashes can and inevitably will collide. It may make little difference if all data is hashed or only part of it.Hash value is 32 bits. That is only 4 billion distinct strings. For any string larger than 5 characters (assuming mostly alphanumeric strings) collisions will start occurring.Assuming 3 hashes:1) computes CRC of all chars2) computes CRC of first half of characters3) uses function above,  using only 10% of charactersWithout knowing the type of strings which appear most commonly, nothing can be said about chance of collision. In practice, 2 might be worse than 1, simply because many words have common prefix.3 however might be a good compromise. It takes into account prefix and suffix as well as middle.It cannot be said whether the hash function used above exhibits desirable behavior, but there is nothing fundamentally wrong with it. Each hash function has inputs for which it degenerates. Only question is whether those are commonly encountered.   ;Quote:Original post by AntheusYes - the fact that hashes can and inevitably will collide. It may make little difference if all data is hashed or only part of it.I know hashes can collide.  I guess what stumped me was the 10.  Why 10?  But in retrospect, on a 64 bit system after around 8 characters collisions will start occurring.  So 10 is probably a good number to use.