有一个对研究项目有用的数据结构的想法，想看看它是否已经有了名称或 STL 等效项:
创建一个大小为 n 的稀疏数组作为 sqrt(n) 指针数组。
要在 i 处插入一个项目，请转到 i/sqrt(n) 处的指针。如果该指针为 null，则将其分配给大小为 sqrt(n) 的新数组。将您的项目插入新数组中的位置 i mod sqrt(n)。
优点很简单:它允许您创建一个最初只占用 O(sqrt(n)) 空间的大数组。您可以在恒定时间内访问任何元素，并且它允许您填充数组的一部分，而无需为所有 n 位置分配空间。
这可能已经用于哈希表分桶，我还有另一个应用(内存非常大的 DNA 序列中的重叠群)。我的问题是:这个有名字吗？我可以使用任何常见的实现吗？
最佳答案
这个数据结构与hashed array tree (HAT)密切相关数据结构。散列数组树的结构与您上面描述的一样——您有一个大小为 √n 的顶级数组，其中每个条目都是指向具有 √n 个元素的数组的指针。这使得插入和查找相当快，并且与传统动态数组的 O(n) 内存开销相比只有 O(√n) 内存开销。
您的结构在几个方面与 HAT 不同。对于初学者来说，如果您需要更多空间，您的结构似乎无法扩展结构，而 HAT 设计为可扩展。此外，您的结构允许随机插入，而 HAT 是为顺序插入而设计的。也就是说，没有根本原因 HAT 必须以这种方式运行，因此您可以将您的数据结构视为对 HAT 的轻微修改。事实上，您可能想看看 HAT 是如何增长的，以使您的数据结构支持增长。
希望这对您有所帮助!
关于arrays - 这个数组数据结构的名称是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16088606/