Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1995-08-28
2002-08-27
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06442553
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and a method for hashing data, and more particularly, to a system and a method for transforming a group of records to be hashed stored in a secondary storage into a referenceable storage form using hash function values, each of which corresponds to a key value of the record.
2. Description of the Related Art
A hash process, in which a group of records stored in a secondary storage, such as a disc storage unit, are transformed into a referenceable storage form using hash function values, each of which corresponds to the key values of the record, is widely used in a conventional data processing system.
FIG. 1
shows a conventional hash process and
FIG. 2
shows a flow chart of the conventional hash process.
In the conventional hash process, a hash list
1
of a group of records to be hashed stored in, for example, a disc storage unit of a computer system, is read into an input buffer
3
in a processor
2
, and hash function values, which respectively correspond to key values of the records to be hashed, are calculated according to a hash function as shown in FIG.
1
. Then, each of the records in the input buffer
3
is stored in one of record buffers
4
according to the hash function values of the record. If a record buffer
4
, which corresponds to one of the hash function values, is filled with records, the records in the record buffer are output into a storage region of a hashed list
5
of a group of hash lists which respectively correspond to the record buffers
4
.
As shown in
FIG. 2
, after starting the hash process, a group of records is read into the input buffer
3
from the hash list
1
(step S
1
). Next, one record is output from the input buffer
3
(step S
2
), the hash function value of the record is calculated based on the key value of the record using a hash function (step S
3
), and the record is stored in one of the record buffers
4
which corresponds to the hash function value of the record (step S
4
).
After that, whether or not the record buffer
4
is full is determined (step S
5
), and then all of the records stored in the record buffer
4
are output to the corresponding one of the hashed lists
5
in the disc storage unit (step S
6
) if the record buffer
4
is full (YES, in step S
5
), and the process goes to step S
7
. If the record buffer
4
is not full (NO, in step S
5
), the process directly goes to step S
7
, and whether or not there is a record left in the input buffer
3
is determined (step S
7
).
If there is a record left in the input buffer (YES, in step S
7
), the process goes back to step S
2
. If there is no record left in the input buffer (NO, step S
7
), whether or not there is a record to be hashed left in the hash list
1
is determined (step S
8
). If there is a record to be hashed in the hashed list
1
(YES, in step S
8
), the record or a group of records to be hashed is read into the input buffer
3
from the hash list
1
(step S
9
), and then the process goes back to step S
2
.
If there is no record left in the hash list
1
(NO, step S
8
), all of the records left in each of the record buffers
4
are output to the corresponding hashed list
5
(step
10
) and the process is completed.
In the process described above, each of the output processes, in which all of the records in a record buffer
4
are output to the corresponding hash lists
5
, is performed individually, and the records stored in one of the record buffers
4
are sequentially read into the corresponding one of the hashed lists
5
. Therefore, in each of the hashed list
5
, each record is stored in a region next to a region in which the previous record is stored.
However, from the viewpoint of a memory region of the disc storage unit in which all of the hashed lists
5
are included, the record reading processes are not sequentially performed, and the records output from each of the record buffers
4
are discontinuously stored in the memory region. Therefore, according to the conventional hash process, many empty regions are formed in the memory region of the disc storage unit, and this reduces the available storage capacity of the disc storage unit and the operating performance of the computer system.
SUMMARY OF THE INVENTION
The objects of this invention are, therefore, to provide a method and a system in which the performance of the secondary storage is improved and the hash process is performed at high speed by reading and outputting the records to be hashed in larger blocks.
The hash method of this invention is for transforming a group of records to be hashed stored in a storage unit into a referenceable storage form using hash function values, which respectively correspond to key values of the records. The hash method includes steps of; temporarily storing the records in a record storing unit; storing pointers, each of which indicates a storing position of a record stored in the record storing unit, in a pointer storing unit in association with a hash function value obtained by a calculation based on a key value of the record; and outputting the record indicated by a pointer, which is stored in the pointer storing unit and corresponding to a designated hash function value, from the record storing unit to the storage unit.
The hash system of this invention is for transforming a group of records to be hashed stored in a storage unit into a referenceable storage form using hash function values, which respectively correspond to key values of the records. The hash system comprises; record storing unit for temporarily storing the group of the records; a pointer storing unit for storing pointers, each of which indicates a storing position of a record stored in the record storing unit, in association with a hash function value obtained by a calculation based on a key value of the record; and an output unit for receiving the record indicated by a pointer, which is stored in the pointer storing unit and corresponding to a designated hash function value, from the record storing unit, and outputting the record to the storage unit.
Records stored in the record storing unit and having the same function value may be linked to each other, and the pointer storing unit may store one of pointers indicating storing positions of the records.
The record storing unit may output records into the storage unit in a block form.
Auxiliary information used for retrieving records in the block by the hash function value may be stored in an auxiliary information storing unit.
The records in the block may be sequentially stored in a hashed list in the storage unit, and the auxiliary information may be stored in an auxiliary information list in the storage unit.
The auxiliary information may include, an address of the block in the hashed list, and the maximum value and the minimum value of the hash function values corresponding to the records in the block.
The hash function value corresponding to the record output from the record storing unit may be designated by an output hash value storage unit.
A record output from the storage unit may be temporarily stored in an input record storing unit and then output to the record storing unit.
The input record storing unit may output a record to an available region resulting from an output of a record from the record storing unit.
If record storing regions of the record storing unit are all empty, all of the records stored in the input record storing unit may be output to the record storing unit.
If record storing regions of the record storing unit are filled with records, the record storing unit may sequentially output records to the output.
REFERENCES:
patent: 4215402 (1980-07-01), Mitchell et al.
patent: 4680700 (1987-07-01), Hester et al.
patent: 4780816 (1988-10-01), Connell
patent: 5287499 (1994-02-01), Nemes
patent: 5339398 (1994-08-01), Shah et al.
patent: 5420982 (1995-05-01), Take
patent: 5621908 (1997-04-01), Akaboshi et al.
patent: 5640554 (1997-06-01), Take
patent: 5680622 (1997-10-01), Even
patent: 5687361 (1997-11-01), Sarkar
pa
Black Thomas
Fujitsu Limited
Rones Charles L.
Staas & Halsey , LLP
LandOfFree
Hash system and hash method for transforming records to be... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hash system and hash method for transforming records to be..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hash system and hash method for transforming records to be... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2971562