Browse Prior Art Database

Converting Key Values for Hashing Coding

IP.com Disclosure Number: IPCOM000077116D
Original Publication Date: 1972-Jun-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 29K

Publishing Venue

IBM

Related People

Ling, H: AUTHOR [+2]

Abstract

In the use of a direct-access file, programmers frequently have to transform the primary key of a record to obtain an address where the record may be stored. Often there are gaps comprising bit patterns that can never occur within the range of key values. The impossible patterns are known as holes in the key range. In many applications, these holes occur in known regular patterns. Under these circumstances, oonversion of the various key values to eliminate the holes and to pack the possible patterns into a shorter key length, before transforming the key to an address can be useful. A detailed arithmetic algorithm for accomplishing the packing is described below.

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

Page 1 of 2

Converting Key Values for Hashing Coding

In the use of a direct-access file, programmers frequently have to transform the primary key of a record to obtain an address where the record may be stored. Often there are gaps comprising bit patterns that can never occur within the range of key values. The impossible patterns are known as holes in the key range. In many applications, these holes occur in known regular patterns. Under these circumstances, oonversion of the various key values to eliminate the holes and to pack the possible patterns into a shorter key length, before transforming the key to an address can be useful. A detailed arithmetic algorithm for accomplishing the packing is described below.

Each character, represented by a bit pattern in the computer is converted into another bit pattern, such that no unused bit pattern can fall between any two meaningful bit patterns. Each converted character is then weighed by its position and the number of symbols possible in each character. The results are added together arithmetically.

To illustrate the procedure, consider the case of EBCDIC encoding. Here, each character or symbol of a key is represented by a byte (8 bits) and the symbols are alpha numeric. In EBCDIC, we have internally in the computer the following representation:

(Image Omitted)

The bit patterns 1100 1010, 1100 1011, etc. can never occur in any eight-bit byte. These are the "holes" in the key range. With a key length of 10 symbols, or 80 bit p...