我目前正在C语言中开发一种编程语言，并且我希望允许用户创建明显具有数字索引的“无限制”数组而不牺牲过程中的性能。例如，table [1000000000]理想情况下可以立即创建并访问，而无需1,000,000,000个项目的表的内存开销，其中999,999,999个未使用;但是当table [n]被定义为1≤n≤1000000时，阵列也会表现良好。使用散列表创建无限数组
您是否对这种数组处理系统的实现有什么建议？
你正在创建一个Sparse Array添加尽可能多的元素，维基百科的文章中提到，这些都可以用链表来表示。
链表中的每个节点都可能是一个动态分配的数组，因此您不会承受连续索引的额外开销。
我想你已经自己回答了。 看看CMPH - C Minimal Perfect Hashing Library。
编辑：
或者你可以使用一个B+ Tree到整数映射到阵列中的真正指标。使用B Trees还有另一个好处：您可以进行范围查询。
你已经有了一个完美的散列函数，在这种情况下，它是索引。 – Hasturkun 2010-06-24 10:01:32
完美的哈希函数是否需要提前知道密钥（例如，将月份的月份...月份映射到1 ... 12）？ – 2010-06-24 10:10:14
如何使用指针，你不必为它定义元素的数量，你可以根据需要
理论上我认为这是可能的。你需要的是非常好的散列算法（以避免冲突）。所以如果有人说table [100..0];您无需一次分配空间。根据需要分配空间。因此，如果在表[100..0]中试图填充前5个值，那么我将只存储这5个值，如果我尝试访问让我们说表[100]，那么我应该得到像'undef'或“零” ....
由the_void提到的库似乎不错...虽然我没有测试过... :)
使用CMPH不会帮帮我。您需要事先知道所有密钥才能创建（最小）完美散列函数。
你想要的是一个简单的关联映射结构，它可以让你实现一个稀疏数组。任何散列表或树结构都可以。您可以使用hash_map或从C++ stl实现或任何类似的数据结构开箱即用。如果你想变得很花哨，你可以使用Judy Arrays，但是我会怀疑它会产生什么影响，除非你能够正确地对基准进行基准测试，并且愿意考虑更复杂的数据结构，这些数据结构会对你的特定用例做假设。
做简单的事情。最简单的可用哈希表是您的最佳答案。甚至不用担心散列函数等问题，无论你的平台提供什么样的功能，都可以运行得很好。
稀疏数组可能效率更低，具有'O（N）' - 'N'个实际项目的“get/set”复杂性（http：//www.itl.nist。gov/div897/sqg/dads/HTML/hugeSparseArray.html） – 2010-06-24 11:37:01
为什么downvote？就我可以告诉这是一个稀疏数组而言，我并不是建议通过@the_void链接到的实现，而是将其作为可能随时间统一的数组的链接列表 – Hasturkun 2010-07-14 15:01:28