HashGenerator_test Class Reference

Description

Test:

cover various detail aspects regarding hash value generation

• weakness of boost::hash

See also

HashIndexed_test

EntryID_test

Definition at line 49 of file hash-generator-test.cpp.

Private Types
typedef boost::hash< string >	BoostStringHasher
typedef std::map< size_t, string >	StringsTable

Private Member Functions
virtual void	run (Arg)
void	demonstrate_boost_hash_weakness ()
void	verify_Knuth_workaround ()

Member Typedef Documentation

BoostStringHasher

typedef boost::hash<string> BoostStringHasher

private

Definition at line 61 of file hash-generator-test.cpp.

StringsTable

typedef std::map<size_t, string> StringsTable

private

Definition at line 62 of file hash-generator-test.cpp.

Member Function Documentation

run()

virtual void run ( Arg  )

inlineprivatevirtual

Definition at line 53 of file hash-generator-test.cpp.

References HashGenerator_test::demonstrate_boost_hash_weakness(), and HashGenerator_test::verify_Knuth_workaround().

Here is the call graph for this function:

demonstrate_boost_hash_weakness()

void demonstrate_boost_hash_weakness ( )

inlineprivate

Test:

demonstrate a serious weakness of boost::hash for strings. When hashing just the plain string representation of integers, we get collisions already with small numbers below 100000. This is counter-intuitive, as the generated hash values are 17 digits long and could span much wider scale.

This problem is especially dangerous when storing objects keyed by a string-id, which is generated from running numbers.

Remarks

as of 2018 the boost::hash function does not show this weakness anymore

Definition at line 76 of file hash-generator-test.cpp.

Referenced by HashGenerator_test::run().

Here is the caller graph for this function:

verify_Knuth_workaround()

void verify_Knuth_workaround ( )

inlineprivate

Test:

verify a well-known pragmatic trick to help with unevenly spaced hash values. The boost::hash function is known to perform poorly on strings with common prefix plus running number. The mentioned trick (attributed to Donald Knuth) is spread the input numbers by something below the full domain, best close to the golden ratio; bonus points if this number is also a prime. An additional factor of 2 does not hurt (so in case of 64bit platform).

In our case, it is sufficient to apply this trick to the trailing four digits; without this trick, we get the first collisions after about 20000 running numbers.

Note

on x86_64, even just spreading the trailing two digits seem to be sufficient to remove any collisions from the first 100000 numbers.

See also

BareEntryID

Definition at line 124 of file hash-generator-test.cpp.

References lib::rani().

Referenced by HashGenerator_test::run().

Here is the call graph for this function:

Here is the caller graph for this function:

Inheritance diagram for HashGenerator_test:

Collaboration diagram for HashGenerator_test:

---

The documentation for this class was generated from the following file:

• hash-generator-test.cpp