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

Publishing Venue

IBM

Related People

Authors:
Rubin, F [+details]

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.