A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value.

A dense 1D array is commonly encoded as a linear array of values [value1, value2, ..., valueN], consecutive in memory.

If an array is encoded as a sparse array, but grows in density, until it becomes dense, then it uses 2X the memory of the array encoded as a dense array.

The question is, there is an encoding that gradually changes from sparse to dense, without wasting memory, and being fast to randomly read and write?

For example, to manage arrays which may be sparse or dense, anything in the middle, and change sparsity as they get manipulated.

A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value.

A dense 1D array is commonly encoded as a linear array of values [value1, value2, ..., valueN], consecutive in memory.

If an array is encoded as a sparse array, but grows in density, until it becomes dense, then it uses 2X the memory of the array encoded as a dense array.

The question is, is there an encoding that gradually changes from sparse to dense, without wasting memory, and being fast to randomly read and write?

For example, to manage arrays which may be sparse or dense, anything in the middle, and change sparsity as they get manipulated.