Building of a hash table

1. A computer-implemented method for improving an efficiency of a computer processor by building a hash table having memory space efficiency and high throughput, the method comprising:

dividing a hash table into plural blocks, the plural blocks including a set of memory slots configured to store hash keys and corresponding key values; and

dividing each block into plural sub-blocks, each sub-block having a sub-set of the set of memory slots,

wherein a certain sub-block uses a first pattern of association between a key and a location for storing the key, and another sub-block which belongs to the same block comprising the certain sub-block uses a second pattern which is different from the first pattern.

2. The method according to claim 1 , wherein a pattern of association, used in a certain sub-block which belongs to a first block, between a key and a location for storing the key is the same with a pattern of association, used in a certain sub-block which belongs to a second block, between a key and a location for storing the latter key.

3. The method according to claim 1 , wherein the number of a type of the patterns of association, used in a certain sub-block which belongs to a first or a second block, between a key and a location for storing the key is less than the number of all sub-blocks which belong to the hash table.

4. The method according to claim 1 , wherein a pattern of association between a key and a location for storing the key is determined using a hash value obtained by calculation using a hash function.

5. The method according to claim 4 , wherein the length of a key is at most n bits, n being a positive integer, the length of a hash value is m bits, m being a positive integer, and m<=n;

if n is divisible by m, each hash function used by the sub-blocks can be defined as h: {0,1} n →{0,1} m ; and

if n is not divisible by m, each hash function used by ┌n/m┐−1 among ┌n/m┐ of the sub-blocks in a certain block can be defined as h: {0,1} n →{0,1} m , and the hash function used by the remaining one block can be defined as h: {0,1} n →{0,1} q , where q is the remainder when n is divided by m.

6. The method according to claim 4 , wherein the hash functions, h 1 , h 2 . . . , h d of the d sub-blocks of a certain block have at most only one key e which satisfies h 1 (e)=a 1 , h 2 (e)=a 2 , . . . , h d (e)=a d , where a i (i=1, 2, . . . , d) are integers (0≤a i ≤2 m −1).

7. The method according to claim 4 , wherein each hash function calculates a bit of a hash value by an XOR operation of bits selected from a key e or by a selection of a bit from a key e.

8. The method according to claim 4 , wherein the hash functions belong to a universal family of universal hashing scheme.

9. The method according to claim 4 , the method further comprising each of the hash functions outputs all 2 m hash values in response to the inputting 2 m keys {2 m a, 2 m a+1, 2 m a+2, . . . , 2 m (a+1)−1} to the hash function where a is a non-negative integer.

10. The method according to claim 1 , wherein the length of a key is at most n bits, n being a positive integer, the length of a hash value is m bits, m being a positive integer, and m<=n;

if n is divisible by m, the division of each block into plural sub-blocks comprises dividing each block into d sub-blocks where d=n/m; and

if n is not divisible by m, the division of each block into plural sub-blocks comprises dividing each block into d sub-blocks where d=┌n/m┐ and ┌n/m┐ is the smallest integer greater than or equal to n/m.

11. The method according to claim 1 , wherein the length of a key is at most n bits, n being a positive integer, the length of a hash value is m bits, m being a positive integer, and m<=n;

if n is divisible by m, each sub-block stores 2 m pieces of keys, wherein hash values are different from each other; and

if n is not divisible by m, ┌n/m┐−1 among ┌n/m┐ of the sub-blocks in a certain block store 2 m pieces of keys, wherein hash values are different from each other, and the remaining one sub-block stores 2 q pieces of keys, where q is the remainder when n is divided by m.

12. The method according to claim 1 , wherein the length of a key is at most ri bits, n being a positive integer, the length of a hash value is m bits, m being a positive integer, and m<=n;

if n is divisible by m, each sub-block has memory slots numbered {0, 1, . . . , 2 m −1}; and

if n is not divisible by m, ┌n/m┐−1 among ┌n/m┐ of the sub-blocks in a certain block have memory slots numbered {0, 1, . . . , 2 m −1} and the remaining one sub-block has memory slots numbered {0, 1, . . . , 2 q −1}, where q is the remainder when n is divided by m.

13. The method according to claim 1 , wherein the length of a key is at most n bits, n being a positive integer, the length of a hash value is m bits, m being a positive integer, and m<=n;

if n is divisible by m, the rank of n×n matrix G is n when g k,(j-1)m+p , an element of k-th row and (j−1)m+p-th column in G, is set to one if the k-th bit of the n-bit key is used for the XOR operation in the hash function used by j-th sub-block, in a specific order, of a certain block to calculate the p-th bit of the m-bit hash value, otherwise the element in G is set to zero; and

if n is not divisible by m, the rank of n×n matrix G is n when g k,p+l , an element of k-th row and p+l-th column in G, is set to one if the k-th bit of the n-bit key is used for the XOR operation in the hash function used by j-th sub-block, in a specific order, of a certain block to calculate p-th bit of the hash value, and if l=0 when j=1, otherwise l=Σ i=1 j-1 m i , where m j =m or q that is the bit-length of the hash value generated by the hash function used by the j-th sub-block, and where q is the remainder when n is divided by m, otherwise the element in G is set to zero.

14. The method according to claim 1 , wherein the number of the sub-blocks is the same among the blocks.

15. The method according to claim 1 , wherein each sub-block further stores data associated with a key.

16. The method according to claim 1 , wherein the same hash function is used in the j-th sub-blocks, in a specific order, of different blocks in the plural blocks.

17. The method according to claim 1 , the method further comprising building a hash table by using memory blocks in a Field Programmable Gate Array.

18. The method according to claim 1 , further comprising:

inserting a key into the hash table by determining, using a hash function, a position in the sub-block of an inserting key and inserting the key into the determined position;

retrieving a key from the hash table by determining, using the hash function, a possible position in the sub-block where there is possibility that a retrieving key is stored and retrieving the key which exists in the determined position; or

deleting a key from the hash table by determining, using the hash function, a possible position in the sub-block where there is possibility that a deleting key is stored and deleting the key which exists in the determined position.

19. The method according to claim 18 , wherein the insertion of the key comprises selecting an empty memory slot of a sub-block, wherein the memory slot is determined by the hash function and putting the key into the slot.

20. The method according to claim 19 , wherein the selection of the empty memory slot and putting of the key comprises, when there are plural sub-blocks having an empty memory slot, selecting a sub-block, based on a specific order, selecting the empty memory slot of the selected sub-block and putting the key into the slot.

21. The method according to claim 18 , wherein the retrieval of data comprises determining whether the key stored in the memory slot determined by the hash function in the sub-block is the same with the retrieving key or not.

22. The method according to claim 18 , wherein the deletion of the determined key comprises:

retrieving a deleting key e in the hash table; and

copying the element of a slot of a sub-block of which a specific order is the same with a sub-block where the deleting key was found and which the sub-block is in the current block b to the slot of a sub-block of which the specific order is the same with the sub-block where the deleting key was found and which the latter sub-block is in the block b-1 placed before the current block b.

23. A system having improved computer processor efficiency by building a hash table having memory space efficiency and high throughput, comprising:

a processor; and

a memory storing a program, which, when executed on the processor, performs an operation for building a hash table, the operation comprising:

dividing a hash table into plural blocks, the plural blocks including a set of memory slots configured to store hash keys and corresponding key values; and

dividing each block into plural sub-blocks, each sub-block having a sub-set of the set of memory slots, wherein a certain sub-block uses a first pattern of association between a key and a location for storing the key, and another sub-block which belongs to the same block comprising the certain sub-block uses a second pattern which is different from the first pattern.

24. A computer program product for improving an efficiency of a computer processor by building a hash table having memory space efficiency and high throughput, the computer program product comprising a computer usable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal, the program instructions executable by a computer to cause the computer to perform a method comprising:

dividing a hash table into plural blocks, the plural blocks including a set of memory slots configured to store hash keys and corresponding key values; and

dividing each block into plural sub-blocks, each sub-block having a sub-set of the set of memory slots, wherein a certain sub-block uses a first pattern of association between a key and a location for storing the key, and another sub-block which belongs to the same block comprising the certain sub-block uses a second pattern which is different from the first pattern.