Browse Prior Art Database

Class of Fast Hash Functions Using Exclusive OR

IP.com Disclosure Number: IPCOM000088342D
Original Publication Date: 1977-May-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 2 page(s) / 22K

Publishing Venue

IBM

Related People

Carter, JL: AUTHOR [+2]

Abstract

A class of functions H is described herein such that given any set of inputs, if f is chosen from H at random, then f is expected to perform well on the inputs.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 70% of the total text.

Page 1 of 2

Class of Fast Hash Functions Using Exclusive OR

A class of functions H is described herein such that given any set of inputs, if f is chosen from H at random, then f is expected to perform well on the inputs.

Let A = {0,1,...,a-1} and B = {0,1,...,b-1} where a = Alpha/i/ and b = 2/j/, where Alpha, i, and j are positive integers. The elements of A are considered to be i- digit numbers written in base Alpha.

Let M be the class of Boolean (0-1) matrices of size i Alpha x j. If m Epsilon M, then m(k) is the string of j bits in the k/th/ row of M. For x Epsilon A, let x(k) be the k/th/ digit of x written base Alpha.

(Image Omitted)

This class of functions is pairwise random, that is, given any x,y Epsilon A, the number of functions in H which map x and y onto the same element of B is less than Absolute H over b.

Having a pairwise random class of hash functions allows one to design a storage and retrieval system which on any application will have an average running time which is linear in the number of transactions.

The storage and retrieval system is basically a standard one where keys with the same index are stored in a linked list [See Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms, Addison Wesley, Reading, Mass., pp. 111-113]. The difference is that at the beginning of each application, the hash function f is chosen at random from H.

Now suppose r is a sequence of requests for storage and/or retrievals. Suppose r involves k requests. Defin...