Method, apparatus and computer program product for improved storage of key-value pairs

摘要

A method, computer program product and apparatus provide an improved data structure for storing key-value pairs. The data structure comprises six arrays. The method, computer program product and apparatus provide for efficient searching, adding, removal, and iteration of elements. The data structure utilizes a scaled hash code and may store multiple values associated with a same scaled hash code. The required memory is allocated at the time of instantiation, resulting in improved performance. An insertion time of a new key-value pair is a linear function of the total number of key-value pairs.

主权项

1. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code instructions stored therein, the computer-executable program code instructions comprising program code instructions to:
receive an indication of a key for which to identify a corresponding value, wherein the key is an element associated with a key index of a first array; calculate a scaled hash code of the key, wherein the scaled hash code is calculated based on at least a maximum number of key value pairs to be stored; access a second array to identify a third array start index based on the calculated scaled hash code; traverse a plurality of key indices in the third array to determine the key index with which the key is associated, wherein the traversal begins from the identified third array start index; access a fourth array based on the determined key index to identify a last value index of a list of values in a fifth array; traverse a plurality of value indices in a sixth array, beginning at the identified last value index, to determine an actual value index by which to access the corresponding value in the fifth array; and cause the corresponding value to be returned in response to a request for the value, wherein the arrays are of primitive types and are allocated upon instantiation.