我目前正在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