Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Dynamic Replacement Hashing Algorithm for Dictionaries

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

Publishing Venue

IBM

Related People

Helman, D: AUTHOR [+2]

Abstract

A method is described for structuring variable length data in storage consisting of most frequently referenced words organized into a dictionary. As illustrated in the figure, the storage 10 is divided into N partitions, each of which is to be used to store words of the same length. In general, a word W with length L is stored in one of the partitions, and the address of the word within the partition is given by an index h(W) which is the result of a hash function h performed on the characters of W. Assume that a word W1 with length L3 already exists at address h(W1) of a partition 11 designated for L3. Assume further that another word W2 with the same length L3 needs to be stored. If the index h(W2) of W2 equals h(W1), then a new partition 12 for words of L3 would be designated to store W2.

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

Page 1 of 2

Dynamic Replacement Hashing Algorithm for Dictionaries

A method is described for structuring variable length data in storage consisting of most frequently referenced words organized into a dictionary. As illustrated in the figure, the storage 10 is divided into N partitions, each of which is to be used to store words of the same length. In general, a word W with length L is stored in one of the partitions, and the address of the word within the partition is given by an index h(W) which is the result of a hash function h performed on the characters of W. Assume that a word W1 with length L3 already exists at address h(W1) of a partition 11 designated for L3. Assume further that another word W2 with the same length L3 needs to be stored. If the index h(W2) of W2 equals h(W1), then a new partition 12 for words of L3 would be designated to store W2. Similarly, if space is needed for a third word W3 having the same length L3 and the same index h(W3) as W1 and W2, a third partition 13 is designated. Partitions designated for words of a given length are chained together, and words belonging to the same chain are bubble sorted in the order of their recent usage. This can be accomplished, as illustrated, where an array of N pointers 14, each belonging to a partition, is used with the pointer of a partition (15, 16, or 17) pointing to the next most recent partition. In the figure, two partitions (18, 19) which are chained by pointer 15 are designated to store words with le...