爲什麼Java ArrayLists不會自動縮小

很久以前，我觀看了Princeton Coursera MOOC的視頻講座：算法介紹，可以找到here。它解釋了在添加或刪除元素時調整類似結構的大小的成本。事實證明，如果我們想爲我們的數據結構提供調整大小，我們將從O(n)到amortized O(n)爲add和remove操作。爲什麼Java ArrayLists不會自動縮小

我幾年來一直在使用Java ArrayList。我一直確定它們會自動增長和縮小。直到最近，令我非常吃驚的是，我在this post中被證明是錯誤的。 Java ArrayList不會自動縮小（儘管它們當然會增長）。

這裏是我的問題：

在我看來在提供小號ArrayList萎縮不作任何傷害的表現已經是amortized O(n)。爲什麼Java創作者沒有在設計中包含此功能？
我知道像HashMap這樣的其他數據結構也不會自動縮小。 Java中是否有任何其他數據結構構建在支持自動收縮的數組之上？
其他語言的趨勢是什麼？在Python/C＃中的列表，字典，地圖，集合等情況下，自動縮小是如何進行的？如果它們與Java所做的相反，那麼我的問題是：爲什麼？

來源

2017-01-30 GA1

讓容器縮小的缺點是，如果添加更多元素，您將不得不再次增長容器。只是因爲你從列表中刪除了元素，圖書館不能認爲你仍然不需要這個空間。我不知道像ArrayList這樣的數組封裝器會自動縮小，我很驚訝地發現有一個這樣做。如果您作爲'ArrayList'用戶知道您的列表容量現在可以減少，那麼可以使用['trimToSize（）']（https://docs.oracle.com/javase/7/docs/api/java/util /ArrayList.html#trimToSize（））。 – khelwood

我知道還有更多工作要做，但用'O'的術語來說，如果您提供自動縮小功能（如視頻中介紹的那樣），就會失去「無」。 'add'和'remove'的複雜性仍然是'攤銷O（n）' – GA1

btw，如果有人給出'-1'，我很樂意閱讀一個建設性的反饋。 – GA1

該評論已經涵蓋了大部分你所要求的。這裏就你的問題的一些想法：

當創建象Java中ArrayList結構，開發者也會在運行期/性能的某些決定。他們顯然決定從「正常」操作中排除收縮，以避免需要額外的運行時。
問題是你爲什麼想自動縮小。 ArrayList不會增長太多（確切地說，因子約爲1.5; newCapacity = oldCapacity + (oldCapacity >> 1)）。也許你也插入到中間，而不是僅僅追加到最後。然後一個LinkedList（它不基於數組 - >不需要縮小）可能會更好。這真的取決於你的用例。如果你認爲你真的需要所有的東西，但是在刪除元素時它必須縮小（我懷疑你真的需要這個），只需擴展ArrayList並覆蓋方法。不過要小心！如果您在每次移除時收縮，則返回O(n)。
C＃List和C++ vector在刪除元素時收縮列表的行爲相同。但自動增長的因素各不相同。甚至一些Java實現使用不同的因素。

來源

2017-01-30 11:53:05 Bambino

爲什麼Java ArrayLists不會自動縮小

回答

相關問題