Back to results
US 9,311,348 B2Granted
Method and system for implementing an array using different data structures
AssigneeFacebook, Inc.
InventorsEdwin Thur Gideon Smith, Keith Adams, Jason Owen Evans
Life of this patent
Estimating the term…
Abstract
Disclosed are a method and system for implementing an array data type of a programming language using various data structures. The disclosed method includes a plurality of implementations in which the array data type may be implemented. The implementations provide an efficient way to retrieve elements from the array, especially in the order they are inserted into the array. The data structures also minimize the computing resources required to manage and access the array. The disclosed technique also selects one of the many implementations based on criteria such as access pattern or size of the array.
Claims19
A method, comprising:
- creating, in a memory of a computer system, a first data structure having multiple contiguous buckets of the memory, the buckets configured to store multiple key-value pairs in the order in which the key-value pairs are inserted into an array;
- and
- creating, in the memory of the computer system, a second data structure having multiple slots of the memory, a specified slot of the slots corresponding to a specified key of the key-value pairs, the specified slot configured to store a specified pointer that points to a specified bucket of the first data structure storing a value of the specified key, the specified slot of the second data structure determined as a function of the specified key stored in the first data structure, the first data structure and the second data structure being different data structures, wherein the first data structure and the second data structure together form a combined data structure that represents the array, and wherein the combined data structure includes a first pointer to the first data structure and a second pointer to the second data structure.
A computer-readable storage device storing computer-readable instructions, the instructions comprising:
- instructions for creating, in a memory of a computer system, a first data structure having multiple slots of the memory, the slots configured to store key-value pairs of an array, the slots including a specified slot storing a specified key-value pair of the key-value pairs;
- and
- instructions for creating, in the memory of the computer system, a second data structure having multiple contiguous buckets of the memory, the buckets configured to store pointers pointing to the slots storing the key-value pairs, a specified pointer of the pointers associated with the specified key-value pair, and the buckets further configured to store the pointers in the order in which the key-value pairs with which the pointers are associated are inserted into the array, the specified slot of the first data structure determined as a function of a specified key of the specified key-value pair stored in the second data structure, wherein the first data structure and the second data structure together form a combined data structure that represents the array, and wherein the combined data structure includes a first pointer to the first data structure and a second pointer to the second data structure.
An apparatus, comprising:
- a hardware processor;
- a data structure creation module configured to receive a request to create an array data structure for implementing an array of a programming language, the array data structure configured to store multiple key-value pairs;
- and
- an implementation selection module to select, based on a pre-defined selection criteria, one of multiple implementations of the array data structure to generate a selected implementation, the implementations including a first implementation and a second implementation, the first implementation storing the key-value pairs in the order in which the key-value pairs are inserted into the array, the second implementation storing multiple pointers that point to the key-value pairs in the order in which the key-value pairs are inserted into the array, wherein the data structure creation module is configured to create the array data structure based on the selected implementation, wherein the array data structure created based on the selected implementation includes a first pointer to a first data structure and a second pointer to a second data structure, the first data structure and the second data structure together forming the array data structure, wherein the first data structure stores the key-value value pairs and the second data structure stores pointers to the key-value pairs stored in the first data structure, wherein the second data structure stores the pointers in the order in which the key-value pairs are inserted into the array or as a function of keys of the key-value pairs pointed to by the pointers.
1 more element
Dependencies are inferred from the claim text.