Browse Prior Art Database

Mechanism for High-Speed Reference and Re-Hashing

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

Publishing Venue

IBM

Related People

Komatsu, H: AUTHOR [+2]

Abstract

Disclosed is a mechanism for managing information efficiently. This mechanism uses a kind of hash table for maintaining information. The table has intermediate hash values that enable this mechanism to realize high-speed reference and re-hashing.

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

Page 1 of 2

Mechanism for High-Speed Reference and Re-Hashing

Disclosed is a mechanism for managing information efficiently. This mechanism uses a kind of hash table for maintaining information. The table has intermediate hash values that enable this mechanism to realize high-speed reference and re-hashing.

The information table has intermediate hash values, keys and information. The figure shows an example where the key is the person's name and the information is his age. In order to determine where the information is saved, the mechanism calculates a hash value. A hash function has two phases. First, all character codes in the key are added, with some bit manipulation. The result is the intermediate hash value. The mechanism embeds the value into an information table. Then the value is divided by the table size, and the remainder is the final hash value, which points to the search point (table index). In the figure, the intermediate hash value for 'Komatsu' is 5198. The hash value is 2.

The decision as to whether a given key and a key in the table are the same is made by comparing the strings that constitute a key. In the end, it comes down to a comparison of characters. If there are many conflicts, numerous comparisons of characters will be necessary, which imposes a great burden on the system. However, with this mechanism it is very simple to make hit or miss decisions simply by comparing the embedded intermediate hash values.

When a hash table is full, re-hashing is nec...