# US 2014/0156708 A1 · Method and system for implementing an array using different data structures

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0156708 A1
- Document ID: US20140156708A1
- Status: Published application
- Kind: A1
- Application number: 13/691,622
- Filed: 2012-11-30
- Published: 2014-06-05
- Earliest claimed: 2012-11-30
- Assignees: Facebook, Inc.
- Applicants: Facebook, Inc.
- Inventors: Keith Adams; Andrew John Paroski; Jason Owen Evans
- Web page: https://patentgrep.com/patent/US20140156708A1

## CPC

- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 9/34: Addressing or accessing the instruction operand or the result {; Formation of operand address; Addressing modes (address translation G06F12/00)}
- G06F 16/168: {Details of user interfaces specifically adapted to file systems, e.g. browsing and visualisation, 2d or 3d GUIs (query results presentation G06F16/156)}
- G06F 16/2255: {Hash tables}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

A method comprising:
creating, in a memory of a computer system, 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 an array; and
creating, in the memory of the computer system, a second data structure having a plurality of slots of the memory, each of the slots corresponding to a particular key 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 value of a key to which the slot corresponds.

### Claim 2 (depends on 1)

The method of claim 1 further comprising:
obtaining, upon insertion of a new key-value pair into the array,
a new bucket from the first data structure, the new bucket being contiguous in the memory to a previously filled bucket, and
a new slot from the second data structure, the new slot corresponding to a new key of the new key-value pair;
storing, in the new bucket, the new key-value pair; and
storing, in the new slot, a new pointer that points to the new bucket.

### Claim 3 (depends on 2)

The method of claim 2, wherein the second data structure is a hashtable.

### Claim 4 (depends on 3)

The method of claim 3, wherein obtaining, from the second data structure, the new slot corresponding to the new key includes obtaining the new slot by using a hash function on the new key.

### Claim 5 (depends on 2)

The method of claim 2, wherein the first data structure and the second data structure 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.

### Claim 6 (depends on 5)

The method of claim 5, wherein the new pointer that points to the new bucket includes an offset of the new bucket in the first data structure.

### Claim 7 (depends on 1)

The method of claim 1, wherein the pointer that points to the bucket of the first data structure is an offset of the bucket in the first data structure.

### Claim 8 (depends on 1)

The method of claim 1 further comprising:
reading the buckets of the first data structure contiguously to obtain the key-value pairs in the order the key-value pairs are inserted into the array.

### Claim 9 (depends on 1)

The method of claim 1, wherein the first data structure and the second data structure are created in a single contiguous block of the memory.

### Claim 10 (depends on 1)

The method of claim 1, wherein at least one of the first data structure or the second data structure are created in separate blocks of the memory.

### Claim 11

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; and
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.

### Claim 12 (depends on 11)

The method of claim 11 further comprising:
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.

### Claim 13 (depends on 12)

The method of claim 12, wherein the first data structure is a hashtable.

### Claim 14 (depends on 13)

The method of claim 13, wherein obtaining, from the first data structure, the new slot corresponding to the new key includes obtaining the new slot by using a hash function on the new key.

### Claim 15 (depends on 12)

The method of claim 12, wherein the first data structure and the second data structure 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.

### Claim 16 (depends on 11)

The method of claim 11 further comprising:
reading the buckets of the second data structure contiguously to obtain an ordered set of pointers; and
reading slots pointed to by the ordered set of pointers to obtain the key-value pairs in the order in which the key-value pairs are inserted into the array.

### Claim 17

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.

### Claim 18 (depends on 17)

The method of claim 17, wherein the pre-defined selection criteria includes at least one of (i) an access pattern of the array, or (ii) size of the array.

### Claim 19 (depends on 18)

The method of claim 18, wherein the access pattern includes at least one of (i) a frequency of fetching values of the array in the order they were inserted, (ii) a frequency of fetching the values in a random order, (iii) number of reads/writes performed on the array, or (iv) number of values read from or written into the array.

### Claim 20 (depends on 19)

The method of claim 19, wherein selecting one of the implementations based on the access pattern of the array includes selecting the first implementation if at least one of (i) the frequency of fetching the values of the array in the order they were inserted exceeds a first predefined threshold, or (ii) if the size of the array is below a second predefined threshold.

### Claim 21 (depends on 19)

The method of claim 19, wherein selecting one of the implementations based on the access pattern of the array includes selecting the second implementation if at least one of (i) the frequency of fetching the values of the array in a random order exceeds a first predefined threshold, (ii) the size exceeds a second predefined threshold, (iii) number of reads/writes performed on the array exceeds a third predefined threshold, or (iv) the number of values read from or written into the array exceeds a fourth predefined threshold.

### Claim 22 (depends on 19)

The method of claim 19 further comprising:
tracking, by the computer system, the access pattern and size of the array over a number of executions of a program the array is part of; and
generating a report containing details of the access pattern and size of the array.

### Claim 23 (depends on 17)

The method of claim 17 further comprising:
resolving a collision in the array data structure using a collision resolution method, the collision resolution method including at least one of (i) chaining, (ii) linear probing, (iii) quadratic probing, (iv) double hashing, or (v) cuckoo hashing.

### Claim 24

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.