这种数组数据结构叫什么名字？

Question

如果您有一个数据结构的想法，可以用于研究项目，并且想知道它是否已经有名称或STL等效物：

创建一个大小为n的稀疏数组，作为sqrt(n)指针的数组。

要在i插入项，请转到i/sqrt(n)处的指针。如果该指针为null，则将其分配给大小为sqrt(n)的新数组。在位置i mod sqrt(n)中在新数组中插入您的项。

优点很简单：它允许您创建一个最初只占用O(sqrt(n))空间的大数组。您可以在恒定时间内访问任何元素，并且它允许您填充数组的部分而无需为所有n个位置分配空间。

这可能已经用于哈希表存储桶，并且我还有另一种应用方式（在非常大的DNA序列中进行contigs记忆化）。我的问题是：这个有没有名字？有什么常见的实现可以使用吗？

- Nathan Fig

---

对于那些寻找实现的人来说，Google几乎使用了所谓的稀疏表来完成这个任务，只不过使用的是常量大小的桶而不是与表大小成比例的桶。http://google-sparsehash.googlecode.com/svn/trunk/doc/implementation.html - Nathan Fig

Answer 1

这种数据结构与哈希数组树（HAT）数据结构密切相关。哈希数组树的结构就像你上面描述的那样——你有一个大小为√n的顶级数组，每个条目都是指向一个具有√n个元素的数组的指针。这使得插入和查找相当快，并且与传统动态数组的O(n)内存开销相比，只有O(√n)内存开销。

您的结构与HAT在几个方面不同。首先，您的结构似乎没有一种方法来扩展结构，如果需要更多空间，而HAT是设计为可扩展的。此外，您的结构允许随机插入，而HAT是设计用于顺序插入。话虽如此，HAT没有必要表现出这种行为，因此您可以将您的数据结构视为对HAT的轻微修改。实际上，您可能需要查看HAT的增长方式，以使您的数据结构支持增长。

希望这有所帮助！

- templatetypedef

---

我认为 HAT 就是我要找的 - 它显然比我想象中更精细，但我预计无论出现什么，情况都会是这样。 - Nathan Fig

Answer 2

我会称之为具有行向量的方阵。如果未完全填充，则为具有行向量的稀疏方阵。这里有两个优化。第一个是稀疏内存分配，第二个是对行下标计算的强度减少。这种优化可能在超标量CPU执行乱序指令并且编译器通常进行全局流优化的时代并不那么重要。但它确实允许通过指针解除引用而不是通过行大小乘法进行行索引。

---

^{1. 在数值分析中，稀疏矩阵指的是大部分元素都为零的矩阵，因此稀疏数据结构在形式上具有相同的定义。在这种情况下，它更像是一个“部分”数据结构，但据我所知，目前还没有被广泛接受的术语来描述这些东西。}

- DigitalRoss

---

是的，这确实是一个非常奇怪的描述。可能是有人试图混淆他的学生 :-) - Šimon Tóth

这是一个哈希表，具有非常简单的哈希函数，仅适用于整数。 - ArgumentNullException

@ArgumentNullException 如果函数是1:1映射，那么它实际上并不是哈希。此外，我绝对不会将其称为除动态（二维）数组以外的任何其他名称，好吧，也许是动态稀疏数组。 - Šimon Tóth

我不同意你的“强度降低”论点。这个数据结构的公共接口只需要一个索引，而不是行/列对；行下标计算之所以必要，是因为你首先执行了反向操作。 - John Bartholomew

换句话说，如果您使用单个（平坦）数组，则索引是最小的 base+index*element_size。如果您拆分数组，则可以减少内存使用量，但无法减少索引到数组的成本，因为现在需要进行 divmod 操作以将索引拆分为行和列索引（并且您需要支付额外的间接成本，这可能会大大超过索引计算成本）。 - John Bartholomew

Answer 3

这是一个桶的数组。

Java的哈希表实现是一种“基于桶的哈希表”。
这里有一个关于这种桶的图形

还有其他结构，比如四叉树，也使用这样的桶。

在您的情况下，您有sqrt(n)个桶。

- AlexWien

Answer 4

我称之为分段数组。 我在将句柄映射到指针时使用它们。

- brian beuning

Answer 5

它也非常类似于Van Emde Boas Tree的第一层。

Van Emde Boas树在第一层存储sqrt(n)个指针，但是在较低的层级上有额外的树，而不仅仅是像这个问题中的简单数组。

- Peter de Rivaz

Answer 6

它本身并不是一种数据结构。看起来这种技术可以用于其他集合类型的数据结构中。

编辑： 它绝对是一种存储或组织数据的机制，但我总是将数据结构与存储/检索（读/写）机制联系在一起。

- ArgumentNullException

---

为什么这不算作数据结构呢？ - templatetypedef

我只是在想，你可以使用它来实现向量、列表或其他任何数据结构。 - ArgumentNullException