有一个对研究项目有用的数据结构的想法，并想看看它是否已经有一个名称或 STL 等价物：
创建一个大小n为sqrt(n)指针数组的稀疏数组。
要在 处插入项目i，请转到 处的指针i/sqrt(n)。如果该指针是null，则将其分配给一个新的大小数组sqrt(n)。将您的项目插入新数组的位置i mod sqrt(n)。
优点很简单：它允许您创建一个最初只O(sqrt(n))占用空间的大型数组。您可以在恒定时间内访问任何元素，它允许您填充数组的某些部分，而无需为所有n位置分配空间。
这可能已经用于哈希表分桶，并且我想到了另一个应用程序（在非常大的 DNA 序列中记忆重叠群）。我的问题是：这个有名字吗？我可以使用任何常见的实现吗？
该数据结构与哈希数组树 (HAT)数据结构密切相关。散列数组树的结构与您在上面描述的一样 - 您有一个大小为 √n 的顶级数组，其中每个条目都是指向具有 √n 个元素的数组的指针。这使得插入和查找相当快，并且与传统动态数组的 O(n) 内存开销相比，只有 O(√n) 内存开销。
您的结构在几个方面与 HAT 不同。对于初学者来说，如果您需要更多空间，您的结构似乎没有办法扩大结构，而 HAT 被设计为可增长的。此外，您的结构允许随机插入，而 HAT 是为顺序插入而设计的。也就是说，没有根本原因 HAT 必须以这种方式运行，因此您可以将数据结构视为对 HAT 的轻微修改。事实上，您可能想查看 HAT 如何增长，以使您的数据结构支持增长。
希望这可以帮助！
好吧，我称之为带有行向量的方阵。如果没有完全填充，它是一个带有行向量的稀疏方阵。1.
这里有两个优化工作。一是稀疏内存分配，二是行下标计算强度降低。对于超大规模 CPU 的乱序执行指令，以及在编译器经常进行全局流优化的时代，这种优化可能并不那么重要。
但它确实允许通过指针取消引用而不是乘以行大小来进行行索引。
1. 然而，在数值分析中，稀疏矩阵是一个大部分为零的矩阵，因此稀疏数据结构在形式上具有相同的定义。在这种情况下，它更像是一种部分数据结构，但据我所知，这些东西还没有被接受的术语。
我称之为分段数组。我在将句柄映射到指针时使用这些。
它也与Van Emde Boas Tree的第一层非常相似。
Van Emde Boas 树在第一级存储 sqrt(n) 指针，但在较低级别有额外的树，而不是这个问题中的简单数组。
它本身不是数据结构。似乎这种技术可以用于其他集合类型的数据结构。
编辑：这绝对是一种存储或组织数据的机制，但我总是将数据结构与存储/检索（读/写）机制相关联。