Browse Prior Art Database

Uniform Hashing Algorithm

IP.com Disclosure Number: IPCOM000080411D
Original Publication Date: 1973-Dec-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 54K

Publishing Venue

IBM

Related People

Arnold, RF: AUTHOR [+5]

Abstract

The primary objective of a hashing algorithm is to map the virtual address space onto the real address space. The following properties are desirable characteristics of the mapping: 1) The virtual space should distribute uniformly over the real space. (At most, the distribution should differ from uniform only by virtual capacity modulo real capacity.) 2) Sequential virtual addresses distribute randomly over the real space. (A certain minimum granularity below which this property does not apply exists and is related to paging characteristics and sequential performance.) 3) Below the granularity mentioned in (2) sequential virtual addresses map onto sequential real addresses.

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 54% of the total text.

Page 1 of 3

Uniform Hashing Algorithm

The primary objective of a hashing algorithm is to map the virtual address space onto the real address space. The following properties are desirable characteristics of the mapping:
1) The virtual space should distribute uniformly over the real

space.

(At most, the distribution should differ from uniform only by

virtual capacity modulo real capacity.)
2) Sequential virtual addresses distribute randomly over the real

space. (A certain minimum granularity below which this property

does not apply exists and is related to paging characteristics

and sequential performance.)
3) Below the granularity mentioned in (2) sequential virtual

addresses

map onto sequential real addresses.
4) Addition of an incremental amount of capacity, delta to an

existing

capacity, C, should only cause remapping of delta/C+delta of the

addresses

contained in C. Further, none of those remappings should result

in addresses originally in C mapping into different locations

within C.
5) The computation should be rapid. (If the mapping is by an

iterative process, the process must converge; the mean time to

termination must be short and the variance must be small.)
6) The mapping must be repeatable.

The algorithm described below achieves a uniform distribution of the virtual space onto the real space. If the functions defined in the algorithm have the further property of uniform random distribution, the properties in 1, 2 and 3 may be satisfied also. The algorithm further meets the requirements listed in 4, and 6. The property described in 5 is insured by truncation of the algorithm and the resulting error shown to be small. The Mapping Algorithm. Definitions. X The input address X = 0, 1, 2, . . . N The number of points in the real address space currently allowed N = 1, 2, . . . N(max) The least integer power of two greater than the maximum possible number of real address space points N(max) = 1, 2, .
. . b The largest integer such that 2/b/ < N b(max) The integer such that 2/b/max = N(max) G(k)(X) A function which distributes {X} uniformly across {ph...