Method and system for implementing an array using different data structures

A method comprising:

• creating, in a memory of a computer system, a first data structure having a plurality of slots of the memory, the slots configured to store key-value pairs of an array, and each of the slots corresponding to a key of the key-value pairs;
• creating, in the memory of the computer system, a second data structure having a plurality of contiguous buckets of the memory, the buckets configured to store pointers pointing to the slots containing key-value pairs, each of the pointers associated with one of the key-value pairs, and the buckets further configured to store the pointers in the order in which the key-value pairs are inserted into the array, 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;
• obtaining, upon insertion of a new key-value pair into the array,
• a new slot from the first data structure corresponding to a new key of the new key-value pair, and
• a new bucket from the second data structure to store a pointer to the new slot, the new bucket being contiguous in the memory to previously filled bucket;
• storing, in the new slot, the key-value pair;
• and
• storing, in the new bucket, a pointer that points to the new slot.

A method comprising:

• receiving, by a computer system, a request to create an array data structure for implementing an array of a programming language;
• selecting, by the computer system and based on a pre-defined selection criteria, one of a plurality of implementations of the array data structure, the implementations including at least one of a first implementation and a second implementation,
• the first implementation including:
• a first data structure having a plurality of contiguous buckets of the memory, the buckets configured to store key-value pairs in the order in which the key-value pairs are inserted into the array, and
• a second data structure having a plurality of slots of the memory, each of the slots corresponding to one of keys of the key-value pairs, each of the slots configured to store a pointer that points to a bucket of the first data structure containing a key-value pair of a key represented by the slot, wherein the first data structure and the second data structure are different data structures, wherein the first data structure and the second data structure together form a first combined data structure that represents the array, and wherein the first combined data structure includes a first pointer to the first data structure and a second pointer to the second data structure, and
• the second implementation including:
• a third data structure having a plurality of slots of the memory, the slots configured to store key-value pairs of an array, and each of the slots corresponding to a key of the key-value pairs, and
• a fourth data structure having a plurality of contiguous buckets of the memory, the buckets configured to store pointers pointing to the slots containing key-value pairs, each of the pointers associated with one of the key-value pairs, and the buckets further configured to store the pointers in the order in which the key-value pairs are inserted into the array, wherein the third data structure and the fourth data structure are different data structures, wherein the third data structure and the fourth data structure together form a second combined data structure that represents the array, and wherein the second combined data structure includes a third pointer to the third data structure and a fourth pointer to the fourth data structure;
• and
• creating the array data structure based on the selected implementation.

An apparatus comprising:

• a processor;
• a memory to store instructions which, when executed by the processor, cause the processor to create an array data structure in the memory using one of a first implementation or a second implementation,
• the first implementation including:
• a first data structure having a plurality of contiguous buckets of the memory, the buckets configured to store key-value pairs in the order in which the key-value pairs are inserted into the array, and
• a second data structure having a plurality of slots of the memory, each of the slots corresponding to one of keys of the key-value pairs, each of the slots configured to store a pointer that points to a bucket of the first data structure containing a key-value pair of a key represented by the slot, wherein the first data structure and the second data structure are different data structures, wherein the first data structure and the second data structure together form a first combined data structure that represents the array, and wherein the first combined data structure includes a first pointer to the first data structure and a second pointer to the second data structure, and
• the second implementation including:
• a third data structure having a plurality of slots of the memory, the slots configured to store key-value pairs of an array, and each of the slots corresponding to a key of the key-value pairs, and
• a fourth data structure having a plurality of contiguous buckets of the memory, the buckets configured to store pointers pointing to the slots containing key-value pairs, each of the pointers associated with one of the key-value pairs, and the buckets further configured to store the pointers in the order in which the key-value pairs are inserted into the array, wherein the third data structure and the fourth data structure are different data structures, wherein the third data structure and the fourth data structure together form a second combined data structure that represents the array, and wherein the second combined data structure includes a third pointer to the third data structure and a fourth pointer to the fourth data structure;
• an implementation selection module that selects, based on a pre-defined selection criteria, one of the first implementation and the second implementation;
• and
• a data structure creation module that creates the array data structure based on the selected implementation.