Method and system for implementing an array using different data structures

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, and
• the second implementation including
• 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, and
• 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;
• 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, and
• the second implementation including
• 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, and
• 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;
• 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.