Key hashing in data processors

Claim 2

In a data processing system having a central processing unit (CPU) and memory, a computerized method for locating a data item using a key stored in the memory comprising a plurality of digits by calculating a hash value from the key (100), comprising the steps of: logically combining (20) in the memory, by means of the CPU, each digit (130,160) in the key with a corresponding digit (140,170) from a first predefined table (120) of digits stored in the memory, according to a first logical combination; overwriting (30) each of the logically combined digits (205,220) in the memory with a substitute digit (215,230) obtained from a second predefined table (200) of digits stored in the memory, the location of the substitute digit in the second table being determined by the CPU from the value of the digit to be replaced combining in the memory, by means of the CPU, the substituted digits using a second logical combination (40); and using the results of the second logical combination to locate the data item.

Claim 3

A method as claimed in claim 1, in which: the first and second logical combinations are such that an inversion of a single bit in either combination's operand causes the invention of one bit in that combination's output.

Claim 4

A method as claimed in claim 1, in which the second logical combination (40) comprises the steps of: (i) dividing the set of substituted digits in the memory, by means of the CPU, into three or more groups of digits; (ii) logically combining two of the groups in the memory, by means of the CPU, according to a third logical combination, to produce a result word; (iii) overwriting the result word in the memory, by means of the CPU, with the logical combination of the result word and a further group, according to the third logical combination; and (iv) repeating step (iii) until the third logical combinations has been applied to each of the groups.

Claim 5

A method as claimed in claim 3 in which the third logical combination is the exclusive-OR operation.

Claim 6

A method as claimed in claim 1, in which each key digit (130,160) is combined with the corresponding digit (140,170) in the first predefined table (120) using an exclusive-OR operation.

Claim 7

A method as claimed in claim 1, further comprising the step of copying the key to a working area of memory before the first logical combining step.

Claim 8

A method as claimed in claim 1, in which: the location of the substitute digit (215,230) in the second table (200) is the numerical value of the digit (205,220) to be replaced; and the second predefined table (200) contains an entry at each location corresponding to a possible value of the digits to be replaced.

Claim 9

A method as claimed in claim 1, further comprising the following steps (50), carried out following the second logical combination: (a) multiplying the result of the second logical combination by a predetermined constant; (b) dividing the result of step (a) into two groups of digits; and (c) combining the two groups of digits using an exclusive-OR operation.

Claim 10

A method as claimed in claim 1, in which a single predefined table is used as the first (120) and the second (200) tables.

Claim 11

Data processing apparatus (600) comprising means for performing the method as claimed in claim 1.

Claim 12

In a data processing system having a central processing unit (CPU), memory and a database, a computerized method for retrieving a data item stored in the database using a key stored in the memory, by calculating a hash value from the key comprising a plurality of digits, comprising the steps of: (a) logically combining in the memory, by means of the CPU, each of said digits in said key with a corresponding digit from a first predefined table of digits stored int he memory using a first logical combination to produce a plurality of logically combined digits; (b) overwriting in memory, by means of the CPU, each of said logically combined digits with a substitute digit obtained from a second predefined table of digits stored in the memory to produce a set of substituted digits, the location of the substitute digit in said second table being determined from the value of the digit to be replaced; (c) dividing said set of substituted digits in memory, by means of the CPU, into at least three groups of digits; (d) logically combining two of said groups in memory, by means of the CPU, according to a second logical combination to produce a result word; (e) overwriting in memory, by means of the CPU, said result word with the logical combination of said result word and a further group stored in the memory, according to a second logical combination; (f) repeating step (e) until said second logical combination has been applied to each of said groups; and (g) retrieving the data item from the database using the result of step (f) to determine the location of the data item in the database.

Claim 13

In a data processing system having a central processing unit (CPU), memory and a database, a computerized method for retrieving a data item stored in the database using a key stored in the memory, by calculating a hash value from the key comprising a plurality of digits, comprising the steps of: (a) logically combining in the memory, by means of the CPU, each of said digits in said key with a corresponding digit from a first predefined table of digits stored int he memory using a first logical combination to produce a plurality of logically combined digits; (b) overwriting in memory, by means of the CPU, each of said logically combined digits with a substitute digit obtained from a second predefined table of digits stored in the memory to produce a set of substituted digits, the location of the substitute digit in said second table being determined from the value of the digit to be replaced; (c) dividing said set of substituted digits in memory, by means of the CPU, into at least three groups of digits; (d) logically combining two of said groups in memory, by means of the CPU, according to a second logical combination to produce a result word; (e) overwriting in memory, by means of the CPU, said result word with the logical combination of said result word and a further group stored in the memory, according to a second logical combination; (f) repeating step (e) until said second logical combination has been applied to each of said groups; and (g) retrieving the data item from the database using the result of step (f) to determine the location of the data item in the database.

Claim 14

A method as claimed in claim 11, further comprising the step of copying the key to a working area of memory before the first logical combination.

Claim 15

A method as claimed in claim 12, further comprising the following steps of: (a) multiplying in memory, by means of the CPU, said result word by a predetermined constant; (b) dividing the result of in memory, by means of the CPU, step (a) into two groups of digits; and (c) combining in memory, by means of the CPU, the two groups of digits using an exclusive-OR operation.

Claim 16

A method as claimed in claim 13 in which a single predetermined table is used as said first and second tables.

Claim 17

A method as claimed in claim 14, in which said first and second logical combinations are exclusive-OR operations.

Claim 18

A data processing apparatus for locating a data item by calculating a hash value from a key comprising a plurality of digits, said data processing apparatus comprising: means for storing the key in a working area of memory in the data processing apparatus; means for logically combining each of said key digits stored in the working area with a corresponding digit from a first predetermined table of digits stored in the data processing apparatus memory according to a first logical combination; means for overwriting in the working area each of the logically combined digits with a substitute digit obtained from a second predefined table of digits stored in the data processing apparatus memory, the location of the substitute digit in the second table being determined from the value of the digit to be replaced; means for combining the substitute digits in the working area using a second logical combination and; means for locating the data item using the results of the second logical combination.

Claim 19

A data processing apparatus for locating a data item by calculating a hash value from a key comprising a plurality of digits, said data processing apparatus comprising: means for storing the key in a working area of memory in the data processing apparatus; means for logically combining each of said key digits stored in the working area with a corresponding digit from a first predetermined table of digits stored in the data processing apparatus memory according to a first logical combination; means for overwriting in the working area each of the logically combined digits with a substitute digit obtained from a second predefined table of digits stored in the data processing apparatus memory, the location of the substitute digit in the second table being determined from the value of the digit to be replaced; means for combining the substitute digits in the working area using a second logical combination and; means for locating the data item using the results of the second logical combination.

Claim 20

The data processing apparatus of claim 16, wherein each key digit is combined with said corresponding digit in the first predetermined table using an exclusive-OR operation.

Claim 21

The data processing apparatus of claim 16, further comprising means for copying said key to a register.

Claim 22

The data processing apparatus of claim 16, wherein said means for combining the substituted digits using a second logical combination comprises: means for dividing the set of substitute digits into three or more groups of digits; means for logically combining two of the groups in the working area according to a third logical combination to produce a resulting word; and means for repeatedly overwriting the result word in the working area with the logical combination of the result word in a further group, according to the third logical combination.

Claim 23

The data processing apparatus of claim 19, further comprising: means for multiplying said result word by a predetermined constant; means for dividing said result word into two groups of digits; and means for combining the two groups of digits using an exclusive-OR operation.