Method and apparatus for data storage and retrieval
AssigneeTelefonaktiebolaget L M Ericsson (publ)
InventorQingsong Li
Life of this patent
Estimating the term…
Abstract
Methods and apparatuses for data storage and retrieval have been provided. More specifically, a hash table is provided. The hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots. Each slot of the first level slot array is associated with a hash code range, and each slot of the first level slot array is linked to at most one second level slot array. Various operations, such as PUT, GET, RANGE_SEARCH of the hash table have been described. Moreover, a hash method has been provided for network management information to use the proposed hash table.
Claims30
A method for processing data in a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, said method comprising:
- receiving data to be processed, said data being represented by a key and value pair;
- obtaining a first hash code which is generated from the key according to the first hash function;
- determining a slot of the first level slot array associated with a hash code range to which the first hash code corresponds;
- and
- storing said key and value pair into a second level slot array to which the determined slot of the first level slot array is linked.
A method for retrieving data from a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, and wherein said data represented by key and value pairs are stored as hash entries in the hash table, said method comprising:
- receiving a key;
- obtaining a first hash code which is generated from the key according to the first hash function;
- determining a slot of the first level slot array associated with a hash code range to which the first hash code corresponds;
- and
- retrieving a value corresponding to said key from a second level slot array to which the determined slot of the first level slot array is linked.
A method for searching data in a range of a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range in the order of hash codes generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, and wherein said data represented by key and value pairs are stored as hash entries in the hash table, said method comprising:
- obtaining a start hash code and an end hash code which define the range of the hash table;
- determining a slot range of the first level slot array, wherein a start slot of the slot range is associated with a hash code range to which the start hash code corresponds, and an end slot of the slot range is associated with a hash code range to which the end hash code corresponds;
- searching hash entries in each second level slot array to which each slot within the slot range is linked;
- and
- returning searched hash entries.
An apparatus for processing data in a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, said apparatus comprising:
- a receiving unit, configured to receive data to be processed, said data being represented by a key and value pair;
- a first level unit, comprising a first hashing unit configured to generate obtain a first hash code which is generated from the key according to the first hash function, and a first slot determination unit configured to determine a slot of the first level slot array associated with a hash code range to which the first hash code corresponds;
- and
- a second level unit, configured to store said key and value pair into a second level slot array to which the determined slot of the first level slot array is linked.
An apparatus for searching data in a range of a hash table, wherein said hash table comprises a first level slot array with a constant number of slots and at least one second level slot array with a variant number of slots, each slot of the first level slot array being associated with a hash code range in the order of hash codes generated with a first hash function, and each slot of the first level slot array being linked to at most one second level slot array, said apparatus comprising:
- a parameter obtaining unit, configured to obtain a start hash code and an end hash code which define the range of the hash table;
- a range determination unit, configured to determine a slot range of the first level slot array, wherein a start slot of the slot range is associated with a hash code range to which the start hash code corresponds, and an end slot of the slot range is associated with a hash code range to which the end hash code corresponds;
- a searching unit, configured to search hash entries in each second level slot array to which each slot within the slot range is linked;
- and
- a result output unit, configured to return searched hash entries.
30-33. (canceled)
Dependencies are inferred from the claim text.