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 S1). Next, one record is output from the input buffer 3 (step S2), the hash function value of the record is calculated based on the key value of the record using a hash function (step S3), and the record is stored in one of the record buffers 4 which corresponds to the hash function value of the record (step S4).
After that, whether or not the record buffer 4 is full is determined (step S5), 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 S6) if the record buffer 4 is full (YES, in step S5), and the process goes to step S7. If the record buffer 4 is not full (NO, in step S5), the process directly goes to step S7, and whether or not there is a record left in the input buffer 3 is determined (step S7).
If there is a record left in the input buffer (YES, in step S7), the process goes back to step S2. If there is no record left in the input buffer (NO, step S7), whether or not there is a record to be hashed left in the hash list 1 is determined (step S8). If there is a record to be hashed in the hashed list 1 (YES, in step S8), the record or a group of records to be hashed is read into the input buffer 3 from the hash list 1 (step S9), and then the process goes back to step S2.
If there is no record left in the hash list 1 (NO, step S8), 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.
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.