很久以前,我观看了普林斯顿Coursera MOOC：算法简介的视频讲座,可以找到
here.它解释了在添加或删除元素时调整类似ArrayList结构的成本.事实证明,如果我们想要为我们的数据结构提供调整大小,我们将从O(n)转到摊销的O(n)以进行添加和删除操作.
我已经使用Java ArrayList几年了.我一直都很确定它们会自动增长和缩小.就在最近,令我惊讶的是,我在this post年被证明是错误的.Java ArrayLists不会自动缩小(当然,它们会增长).
这是我的问题：
>在我看来,在ArrayLists中提供收缩不会造成任何损害,因为性能已经摊销了O(n).为什么Java创建者没有将此功能包含在设计中？
>我知道像HashMaps这样的其他数据结构也不会自动缩小. Java中是否有任何其他数据结构构建在支持自动收缩的数组之上？
>其他语言的趋势是什么？如果列表,词典,地图,Python / C#中的集合等自动收缩看起来如何.如果它们与Java所做的相反,那么我的问题是：为什么？
解决方法
评论已经涵盖了您要求的大部分内容.这里有一些关于你问题的想法：
>在Java中创建类似ArrayList的结构时,开发人员会对运行时/性能做出某些决定.他们显然决定将“正常”操作中的收缩排除在外,以避免需要额外的运行时间.>问题是为什么你想要自动收缩. ArrayList不会增长那么多(因为大约是1.5; newCapacity = oldCapacity(oldCapacity>> 1),确切地说).也许你也插入中间而不只是追加到最后.然后,LinkedList(不基于数组 – >不需要收缩)可能会更好.这真的取决于你的用例.如果你认为你确实需要ArrayList所做的一切,但是在删除元素时它必须缩小(我怀疑你真的需要这个),只需扩展ArrayList并覆盖这些方法.不过要小心！如果每次移除都缩小,则返回O(n).> C#List和C向量在删除元素时缩小列表的行为相同.但自动增长的因素各不相同.甚至一些Java实现也使用不同的因素.
