Nat*_*Fig 6 arrays algorithm data-structures
实现一个大小n数组作为sqrt(n)指针数组.
要插入项目i,请转到指针i/sqrt(n).如果该指针是null,则将其分配给新的大小数组sqrt(n).将您的项目插入新阵列的位置i mod sqrt(n).
优点很简单:它允许您创建一个最初只O(sqrt(n))占用空间的大型数组.您可以在恒定时间内访问任何元素,它允许您填充数组的部分,而无需为所有n位置分配空间.
这可能已经用于哈希表,我还有另一个应用程序.我的问题是:这有名字吗？我可以使用任何常见的实现？
该数据结构与散列数组树(HAT)数据结构密切相关.散列数组树的结构与上面描述的类似 - 你有一个大小为√n的顶级数组,其中每个条目都是一个指向带有√n元素的数组的指针.这使得插入和查找相当快,并且与传统动态数组的O(n)内存开销相比仅具有O(√n)内存开销.
您的结构在某些方面与HAT不同.对于初学者来说,如果你需要更多的空间,你的结构似乎没有办法增长结构,而HAT的设计是可以增长的.此外,您的结构允许随机插入,而HAT设计用于顺序插入.也就是说,HAT必须以这种方式运行没有根本原因,因此您可以将您的数据结构视为对HAT的轻微修改.实际上,您可能希望了解HAT如何增长,以使您的数据结构支持增长.
希望这可以帮助!