Browse Prior Art Database

Fast Uniform String Hashing Algorithm

IP.com Disclosure Number: IPCOM000036688D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 2 page(s) / 31K

Publishing Venue

IBM

Related People

Rubin, F: AUTHOR

Abstract

The following algorithm provides a hashing of a character string, or other data, which is both fast and uniform, independent of the distribution of the strings. It is as much as 2.5 times as fast and as uniform as the previous best hash [*]. 1. Break the character string into 7-byte chunks. Treat each chunk as two 28-bit quantities. 2. Add a random number of each of the two 28-bit halves. Random numbers in the range 0 to X'70000000' are kept in a fixed table. This range prevents overflow during the addition. 3. Multiply the two sums to get a 62-bit product. 4. Exclusive-OR the 62-bit products from each of the 7-byte chunks of the string. 5. Any final chunk of 1 to 6 bytes is also split into two equal- sized halves, and treated as in steps 2-4. 6.

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

Page 1 of 2

Fast Uniform String Hashing Algorithm

The following algorithm provides a hashing of a character string, or other data, which is both fast and uniform, independent of the distribution of the strings. It is as much as 2.5 times as fast and as uniform as the previous best hash [*].
1. Break the character string into 7-byte chunks. Treat

each chunk as two 28-bit quantities.
2. Add a random number of each of the two 28-bit halves.

Random numbers in the range 0 to X'70000000' are kept

in a fixed table. This range prevents overflow during

the addition.
3. Multiply the two sums to get a 62-bit product.
4. Exclusive-OR the 62-bit products from each of the

7-byte chunks of the string.
5. Any final chunk of 1 to 6 bytes is also split into two

equal- sized halves, and treated as in steps 2-4.
6. Split the 62-bit result of the Exclusive-ORing process

into two 31-bit halves, and Exclusive-OR the halves to

get the final hash value.
7. If the result is to be scaled into a specified range 0

to N-1, multiply the hash value by N, and use the

high-order portion of the product.

Reference: J. Lawrence Carter and Mark N. Wegman, "Universal Classes of Hash Functions," J. Compu. and Sys. Sci. 18, 143-154 (April 1979).

1

Page 2 of 2

2

[This page contains 3 pictures or other non-text objects]