Portable hash

The Taligent Application Environment sometimes stores objects in disk files that are accessed via a hash. Examples of classes that do this are TDiskSetOf and TDiskDictionaryOf . In order for the index structures in these files to work when the files are transported across platforms, the hash functions used must return the same result on every platform.

To do a portable hash, follow these rules:

Only use other portable-hash results or portably converted primitives as elements in your calculations.

Store the hash result as a value; never interpret it as a sequence of bytes.

All of the primitives that you use must be converted to a portable form, with precisely the same results on all machines. This means that you convert all primitive values to HashResult (unsignedlong), using only 32 bits.

For all integer values, this is a simple mask and cast (assume kMask32
is a named constant that stands for the masking value 0xFFFFFFFFU):
This works because:
1. If one operand is unsignedlong, the other is converted to unsignedlong.
2. If a shorter unsigned value is converted to a longer one, the value is preserved.
3. If a signed value is converted to unsigned, it must have the correct value mod 2^n, where n is the number of bits in the unsigned type. So, a conversion to unsignedlong yields identical values on different machines as long as the number of bits in an unsignedlong is the same.
4. If the number of bits in an unsignedlong is greater than or equal to 32, the least 32 bits of the result in from the previous step (c.) is the same across all such machines.
For double and float, the Hash supplied by Numerics.h is portable.

All arithmetic operations that you perform in combining elements must be portable; they must have precisely the same results on all hardware. This means that every operation on HashResult must be masked to 32 bits afterwards. Restrict yourself to the arithmetic operations (+, -, *, /, %) and logical operations (^, &, |, ~, >>, <<, RotateUp, RotateDown).

result = (x + y) & kMask32

You must guarantee to all clients that you will never change the hashing algorithm, even if there are bugs in it. The only exception to this would be if you had a bug in your algorithm so severe that its prior results were useless. For example, if Hash() returns TRandomNumberGenerator::First(), the old data isn't retrievable. So changing Hash() to return 0 is permissible because it allows new applications to work, while the old ones already don't work.

Strive for uniform distribution

If you want your hash function to return hash values that are uniformly distributed across what the return type can represent, send your result as a seed to a random number generator that returns values of that type. Because the semantics of the random number generator are to return numbers that are uniformly distributed, this makes your hash function also generate values with the same property.

In the future, the Taligent Application Environment will define APIs to assist in computing portable hashes. In the meantime, you might want to write your own helpers, such as a masking function.

Do not implement Hash via member functions

For many objects, Hash (and comparison) aren't intrinsic properties of the objects, but of the collections they are inserted into. Thus, they shouldn't be implemented via member functions. To illustrate why this is a problem, consider TFontIdentifierStyle, which identifies the font to use for text in style sets and line layout. A hash function was added for line layout so that TFontIdentifierStyles could be found. This Hash function was based on the name of the font. However, no one realized that TStyle already defined a Hash function based on the type of the style--it was a TFontIdentifierStyle. So, when this new Hash function was introduced, TFontIdentifierStyles stopped working in style sets.

[Contents] [Previous] [Next]

Click the icon to mail questions or corrections about this material to Taligent personnel.

Generated with WebMaker