JPH0471228B2 - - Google Patents

Description

[Detailed Description of the Invention] [Summary] In a data processing system that accesses a database by hashing using key items, the key items to be hashed are converted into a standard form, and the unit data is converted into a seed. By performing addition with , shifting odd bits, and reversing the bits of the even result, it is possible to perform homogeneous hashing at high speed not only for numbers but also for strings of different lengths. .

[Industrial application field]

The present invention provides a method for storing records in a database/
The present invention relates to a data processing system that determines a search position by hashing, and particularly to a homogeneous hashing processing method that enables homogeneous hashing even for variable character string keys.

When storing records in a database depending on the content of key items, it is necessary to perform hashing as homogeneously as possible to eliminate bias in storage locations.

[Conventional technology]

Traditionally, storing records in a database/
Various methods are used for hashing required for searching. Hashing for numerical type key items in these methods is mostly satisfactory. However, in database key searches, it is relatively often necessary to use not only numerical values but also character strings of different lengths as hashing keys.

Conventionally, when using such a variable-length character string as a key item for hashing, for example, each character code of the character string is added and converted to a numerical value.
A fixed-length portion of a variable-length character string is extracted and used for hashing.

[Problem that the invention seeks to solve]

When a character string is a key item to be hashed, there is a problem in that the hashing results are likely to be biased due to the characteristics of the character data. If the hashing results are biased, the storage addresses of different records will have the same value, which may require extra storage space and processing, and the performance of the database will deteriorate. Therefore, if many randomization processes are performed to prevent bias in the hashing results, a homogeneous hashing result can be obtained, but there is a problem in that efficiency deteriorates as the processing time becomes longer.

The present invention aims to solve the above-mentioned problems and provides a homogeneous hashing processing method suitable for hashing variable-length character string keys, etc., which takes a relatively short processing time and can obtain homogeneous hashing results. .

[Means for solving problems]

FIG. 1 shows a block diagram of the principle of the present invention.

In FIG. 1, 10 is a hashing processing unit that performs hashing on key items to be hashed, 11 is a standard form conversion processing unit that converts each numeric key and character key to be hashed into a standard form, and 12 is a standard form conversion processing unit. 13 is a shift processing unit that mixes the calculation results of the calculation unit 12 by shifting an odd number; 14 is a shift processing unit that performs calculations including addition by extracting the key converted into a shape for each unit data; This is an inversion processing section that performs bit inversion.

Each key item K _i to be hashed is converted by the standard form conversion processing unit 11 into a standard form key N _i common to various numerical values and characters. this key
N _i is sequentially extracted by the calculation unit 12, for example, in units of 1-byte data, and is added to I _i , which is a seed for randomization, or r _j , which is an intermediate result. The shift processing unit 13 performs a process of mixing the calculation results of the calculation unit 12 by cyclically shifting odd-numbered bits or the like. Reversal processing section 14
When the shift result by the shift processing unit 13 is a corner number, the intermediate result is made an odd number by performing an exclusive OR with the hexadecimal number 'FFF...FF'.

If the calculation is repeated for each unit data of key N _i and all unit data (l pieces) included in key N _i are processed, the result r _l is
Let R _i be the randomization result of key N _i .

[Effect]

Key items include numeric keys and character keys, and there are various types of numeric keys, such as so-called external decimal, internal decimal, and binary. According to the invention,
Since the standard format conversion processing unit 11 converts various types of numerical values and character keys into standard formats, various types of numerical values and characters can be similarly randomized.

Since the calculation unit 12 sequentially processes all the unit data included in the key converted to the standard form, especially when the key to be hashed is a variable length string, all the unit data included in the variable length string is characters will be used in the calculation for randomization, and a good result will be obtained.

The shift processing section 13 performs an odd number shift on the intermediate result, and the inversion processing section 14 performs bit inversion when the result is an even number. In the randomization process, better randomization results can be obtained when odd numbers are used as the calculation targets than when even numbers are used as the calculation targets, so that more homogeneous hashing is performed.

〔Example〕

FIG. 2 is an example of a system to which the present invention is applied, FIG. 3 is a conceptual diagram of randomization processing of a plurality of key items, FIG. 4 is a diagram illustrating standard form conversion processing according to an embodiment of the present invention, and FIG. The figure is an explanatory diagram of randomization processing according to an embodiment of the present invention, and FIG. 6 shows a processing flow of an embodiment of the present invention.

The present invention is applied to a system as shown in FIG. 2, for example. In Fig. 2, 10 is the same as the hashing processing section shown in Fig. 1, and 20 is the CPU.
21 is a database management system; 22 is a record storage unit;
23 is a record search unit that searches for records by key; 24 is an input/output unit; 25 is a record stored in a database; 26 is an external storage device such as a magnetic disk device; 27 is a database; 28 is a display; Represents the keyboard.

When storing a new record 25 in the database 27, the record storage unit 22 stores the record 25.
By calling the hashing processing unit 10 using a predetermined key, the storage position in the external storage device 26 is determined. For example, if a record in the database 27 is uniquely determined by the product name, production area, and variety number, the storage location of the record 25 will be the variable-length character strings "apple" and "AOMORI" and the numerical value "61105". It is determined by predetermined hashing.
In the case of a search by the record search unit 23, the position where the search target record exists is determined by similar hashing.

If this hashing is not homogeneous, collisions of storage positions will occur, and overflow processing will be required, resulting in poor efficiency.

Randomization for hashing using multiple key items is performed as shown in FIG. In Fig. 3, K ₁ to K _o are key items, and in the record 25 as shown in Fig. 2, the product name is K ₁ , the production area is K ₂ ,
The product number is _K3 . I _i is the so-called seed of randomization, and R _i is the randomization result by h(I _i , K _i ).

The species I ₁ used as the initial value is, for example, X'
It is an arbitrary constant such as AAAAAAAAA' (hexadecimal number). R ₁ is determined by a predetermined randomization function h using I ₁ and key item K ₁ as parameters. When processing the next key item K ₂ , an operation is performed using a randomization function h using R ₁ as a seed I ₂ and I ₂ and K ₂ as parameters. Proceed in the same way for each key K _i , and the last key K _o
The output result R _o of the processing for is used to determine the storage position by hashing.

Its storage location is as follows: Assuming that the number of prime pages in the database is P, the number of pages in one logical page is L, and the number of the entry logical page for which E is sought, E=[(|R _o | mod P )÷L]. Here, the symbol | | is the symbol of absolute value, and the symbol [ ] is a Gauss symbol meaning that the decimal part is rounded down.

The present invention provides efficient processing means for the randomization function h that enables homogeneous hashing. Hereinafter, a detailed explanation will be given according to examples.

The standard form conversion processing unit 11 shown in FIG. 1 performs conversion processing as shown in FIG. 4, for example.

If the key item is a character string, the entire string is taken into standard form as shown in Figure 4A. Also, for numbers, the original key is external decimal, internal
Regardless of whether it is in decimal or binary format, it is converted into a 10-byte internal decimal format as shown in FIG. S′, which indicates the sign after conversion, is a hexadecimal 'C' if the value is positive, and a hexadecimal ' if the value is negative.
It is D'.

Randomization processing as shown in FIG. 5, for example, is performed using the conversion result N _i to the standard form. Hereinafter, explanation will be made according to (a) to (e) shown in FIG.

(a) Add the (l-j)th byte from the left of N _i to r _j ,
Let this be the intermediate result RND. Note that l is N _i
j is a loop variable from 0 to (l-1). The randomization seed I _i is used for the initial value r ₀ . RND is a 4-byte binary number.

(b) Circularly shift the intermediate result RND to the right, for example by 7 bits.

(c) If the intermediate result RND after the shift is an even number,
Bit inversion is performed by exclusive OR with X'FFFFFFFF'.

(d) Circularly shift the intermediate result RND by an additional 7 bits to the right.

(e) As a result of the shift, RND is again shifted from the left of N _i (l
−j) Add byte. Add 1 to j, (j
Process (a) to process (e) in the same way until +1) becomes l.
repeat. Intermediate result of operation in process (e)
RND becomes the input for process (a). The final result r _L is taken as the randomization result R _i .

FIG. 6 is a flowchart of a specific embodiment of the present invention. The meanings of symbols such as variables used in FIG. 6 are as follows.

KEYITEM(N): Random key item group N: Index to key item S: Number of random key item groups X(I): Key byte number I: Key byte index RND: 4-byte random number P _S : First page of the target range or subrange P _E : End page of the target range or subrange P _EN : Entry page LP: Number of pages in one logical page mod: Function for calculating the remainder [ ]: Symbol for calculating the quotient All operations performed in FIG. 6 are performed without signs. ~ in the following explanation
corresponds to the processing shown in FIG.

Set the initial value “2863311530” to RND.
This is X'AAAAAAAAA' in hexadecimal.
Also, the index N for the key item is initialized to 1.

Determine whether the Nth key item is a numerical type or a character type.

If the Nth key item is of numeric type,
Convert it to internal decimal and call it X. I is the key length of 10. If it is a character type,
Let the character string of the key item be X as it is, and let I be the number of bytes of the character string.

Add the Ith byte of X to RND.

Perform a 7-bit clockwise circular shift on RND.

Determine whether RND is an odd number. If the number is odd, skip the next process.

Invert all bits for RND. In addition,
(2 ³² -1) is X'FFFFFFFF'.

Add the Ith byte of X to RND.

Perform a 7-bit clockwise circular shift on RND.

Subtract 1 from I.

Whether processing has been completed for all bytes of X is determined based on whether I has become 0 or less. If it is larger than 0, control is returned to the process and the process is repeated in the same way.

If I is less than or equal to 0, add 1 to N.

Determine whether processing has ended for all key items. If N is smaller than S, the process has not finished, so control is returned to the process and processing continues for the next key item.

When RND is viewed as a signed binary number, it is determined whether it is negative or positive. If it is positive, skip the next process.

Considering RND as a signed 32-bit binary number, find the absolute value of (RND+1).

Based on the final result RND, the entry page _PEN , which is the record storage/retrieval position, is calculated.

In the above processing, basic instructions and the like possessed by a normal computer can be used, so that calculations can be executed at high speed.

〔Effect of the invention〕

As explained above, according to the present invention, even when a variable length character string is used as a hashing key,
It becomes possible to easily perform homogeneous hashing. Furthermore, the content of the calculation process is relatively simple, and hashing can be performed at high speed.

[Brief explanation of drawings]

Fig. 1 is a block diagram of the principle of the present invention, Fig. 2 is an example of a system to which the present invention is applied, Fig. 3 is a conceptual illustration of randomization processing of multiple key items, and Fig. 4 is an example of an embodiment of the present invention. An explanatory diagram of the standard form conversion process,
FIG. 5 is an explanatory diagram of randomization processing according to an embodiment of the present invention, and FIG. 6 shows a processing flow of an embodiment of the present invention. In the figure, 10 represents a hashing processing section, 11 a standard form conversion processing section, 12 a calculation section, 13 a shift processing section, and 14 an inversion processing section.

Claims (1)

[Scope of Claims] 1. In a data processing system that determines the storage/search position of records in a database based on one or more key items that are subject to predetermined hashing, numeric keys and character keys that are the key items are Conversion processing means 11 for converting into a predetermined standard form
and a calculation means 12 which extracts the key converted into the standard form for each unit of data and performs calculations including addition.
, a shift processing means 13 that mixes the operation results by shifting odd numbers, and an inversion processing means 14 that performs bit inversion when the shift result is an even number, and converts the key converted into the standard form into each unit data. , the arithmetic means 12, the shift processing means 1
3. A homogeneous hashing processing method characterized in that randomization processing is performed by the reversal processing means 14.