Browse Prior Art Database

Universal Hash Function

IP.com Disclosure Number: IPCOM000099340D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 2 page(s) / 61K

Publishing Venue

IBM

Related People

Barzilai, T: AUTHOR [+4]

Abstract

Disclosed is a fast method of hashing that is provably unlikely to produce an unexpectedly large number of collisions.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 54% of the total text.

Universal Hash Function

       Disclosed is a fast method of hashing that is provably
unlikely to produce an unexpectedly large number of collisions.

      Many computer algorithms rely on hashing (1,2) to distribute
data relatively evenly.  The Universal Hashing approach (3)
eliminates the danger that a systematic bias to the data will degrade
performance.  Universal Hashing requires a set of hash functions that
satisfies a certain technical property (informally, that for any pair
of data items, almost all of the functions map the two items to
different values).

      This disclosure presents a good set of hashing functions which
is suitable for machines that can multiply two 4-byte integers and
get an 8-byte result.  The technique represents an improvement to
state-of- the-art Universal Hashing techniques (3,4).  Comparable
performance is achieved by (5), but this method is not known to be
Universal.

      Let c=2,147,483,646 (which is 2 to the 31st power minus 2).
Each hash function in the set is specified by two numbers A and B in
the range of 0 to c, inclusive.  Given an 8-byte quantity X to be
hashed, perform the following computations: 1.   Separate X into two
4-byte quantities, X1 and X2.  We require that both X1 and X2 be
between 0 and c (inclusive), and that the mapping from X to the pair
(X1, X2) be one-to-one. (If these requirements are not met, then the
resulting set of hash functions will not be Universal, though still
may perform w...