What is the name of this array data structure?

Question

Implement an array of size n as an array of sqrt(n) pointers.

To insert an element in i , go to the pointer in i/sqrt(n) . If this pointer is null , assign it to a new sqrt(n) sized array. Insert your element into a new array at position i mod sqrt(n) .

The advantage is simple: it allows you to create a large array, initially occupying only O(sqrt(n)) space. You can access any element in constant time and allow you to fill parts of the array without taking up space for all n positions.

This may already be used for hash tables, and I have another application. My question is: is there a name? Any general implementation I can use?

Answer 1

This data structure is closely related to the hashed array tree (HAT) data structure. The hashed array tree is structured as you described above - you have a top-level array size & radic; n, where each entry is a pointer to an array with & radic; n This makes inserts and searches reasonably fast and only has O (& radic; n) memory overhead compared to the O (n) memory overhead of a traditional dynamic array.

Your structure differs from HAT in several ways. Firstly, your structure does not have the ability to grow the structure if you need more space, while the HAT is designed to be stable. In addition, your structure allows for random inserts, while the HAT is for sequential inserts. However, there is no fundamental reason why the HAT should behave this way, so you can think of your data structure as a small modification to the HAT. In fact, you can see how the HAT grows so that your data structure supports growth.

Hope this helps!

Answer 2

Well, I would call it a square matrix with row vectors. If not completely filled, this is a sparse square matrix with row vectors. ^1.

There are two optimizations here. The first is sparse memory allocation, and the second is the reduction in row index reduction . This optimization is probably not that important when the superscalar processor executes the instructions out of order and at an age when compilers usually perform optimization of global threads.

But it allows you to index rows by dereferencing the pointer, rather than multiplying by the size of the row.

---

^{1. However, in numerical analysis, a sparse matrix is ​​one that is basically zero, and therefore the sparse data structure formally has the same definition. In this case, it is rather part of the partial data structure, but as far as I know, I do not accept the conditions for these things.}

Answer 3

This is an array of buckets.

Java hastable implementation is such a “bucket-based hash table”.
Here are the graphics for such buckets

There are other structures, such as ATVs, which also use such buckets.

In your case, you have sqrt (n) squares.

Answer 4

I call it a segmented array. I use them when matching pointer handles.

Answer 5

It is also very similar to the first level of Van Emde Boas Tree .

A Van Emde Boas Tree stores sqrt (n) pointers at the first level, but has additional trees at lower levels instead of a simple array, as in this question.

Answer 6

This is not a data structure per se. It looks like this method can be used in other data structures like collection.

Edit: This is definitely a mechanism for storing or organizing data, but I have always associated the data structure with storage / retrieval (read / write) mechanisms.