4. Hashing Multiple Values Together

この節では FNV の RFC テキストを保持し, FNV primes, offset_basis, endianism, XOR folding, constants, non-cryptographic security guidance, source code, test code, Makefile, SHA-1 and SHA-256 との比較を扱う.

RFC 原文

4.  Hashing Multiple Values Together

   Sometimes, there are multiple different component values, say three
   strings X, Y, and Z, where a hash over all of them is desired.  The
   simplest thing to do is to concatenate them in a fixed order and
   compute the hash of that concatenation, as in

                             hash ( X | Y | Z )

   where the vertical bar character ("|") represents string
   concatenation.  If the components being combined are of variable
   length, some information is lost by simple concatenation.  For
   example, X = "12" and Y = "345" would not be distinguished from X =
   "123" and Y = "45".  To preserve that information, each component
   should be preceded by an encoding of its length or should end with
   some sequence that cannot occur within the component, or some similar
   technique should be used.

   For FNV, the same hash results if 1) X, Y, and Z are actually
   concatenated and the FNV hash is applied to the resulting string or
   2) FNV is calculated on an initial substring and the result is used
   as the offset_basis when calculating the FNV hash of the remainder of
   the string.  This can be done several times.  Assuming that
   FNVoffset_basis ( v, w ) is the FNV of w using v as the offset_basis,
   then in the example above, fnvx = FNV ( X ) could be calculated and
   then fnvxy = FNVoffset_basis ( fnvx, Y ), and finally fnvxyz =
   FNVoffset_basis ( fnvxy, Z ).  The resulting fnvxyz would be the same
   as FNV ( X | Y | Z ).

   This means that if you have the value of FNV ( X ) and you want to
   calculate FNV ( X | Y ), you do not need to find X.  You can simply
   calculate FNVoffset_basis ( FNV ( X ), Y ) and thereby get FNV ( X |
   Y ).

   Sometimes, such a hash needs to be repeatedly calculated; the
   component values vary, but some vary more frequently than others.
   For example, assume that some sort of computer network traffic flow
   ID, such as the IPv6 Flow Label [RFC6437], is to be calculated for
   network packets based on the source and destination IPv6 addresses
   and the Traffic Class [RFC8200].  If the Flow Label is calculated in
   the originating host, the source IPv6 address would likely always be
   the same or would perhaps assume one of a very small number of
   values.  By placing this quasi-constant IPv6 source address first in
   the string being FNV-hashed, FNV ( IPv6source ) could be calculated
   and used as the offset_basis for calculating the FNV of the IPv6
   destination address and Traffic Class for each packet.  As a result,
   the per-packet hash would be over 17 bytes rather than over 33 bytes,
   saving computational resources.  The source code in this document
   includes functions facilitating the use of a non-standard
   offset_basis.

   An alternative method of hashing multiple values is to concatenate
   the hashes of those values and then hash the concatenation -- that
   is, compute something like

                    hash ( hash (X) | hash (Y) | hash (Z) )

   This will involve more computation than simply computing the hash of
   the concatenation of the values and thus, unless parallel
   computational resources are available, greater latency; however, if
   parallel computational resources are available and the values being
   hashed together are long enough to overcome any initial/final hash
   function overhead, which is very small for FNV, latency can be
   reduced by hashing the concatenation of the hashes of the values.

   For another example of a similar technique, assume a desire to use
   FNV-N to hash a byte string of length L.  Let B = N/8, the number of
   bytes of FNV-N output.  If that string is divided into k successive
   substrings of equal length and assuming, for simplicity, that L is an
   integer multiple of k, hashing the substrings and then hashing the
   concatenation of their hashes will hash a total of L + k*B bytes,
   clearly more than the initial string size L.  However, if sufficient
   parallel computational resources are available to hash all the
   substrings simultaneously, the elapsed time can be changed
   approximately from on the order of L to on the order of L/k + k*B.
   For sufficiently large L, this parallelization will reduce the
   elapsed time to produce the overall hash.