java – treemap vs arraylist – 迭代/添加/编辑值时的性能和资

如果我们讨论的是排序数据,因为ArrayList是一个列表/数组,如果它已经排序,你可以得到O(log n)速度的值.但是要插入,它是O(n),因为在插入新元素时可能需要移动整个数组.

TreeMap数据结构实现为红黑树,插入时间和搜索时间均为O(log n).

所以,简而言之：

Data Structure         Insertion Speed    Search Speed
ArrayList (sorted)     O(n)               O(log n)
TreeMap                O(log n)           O(log n)

我肯定会选择TreeMap.它还有额外的好处,就是让它现在就准备好了(你必须自己实现一些代码才能使ArrayList工作).

注意：
如果没有得到O(n)(称为big-Oh)表示法,可以将其视为结构具有n个元素时所需的秒数的公式.因此,如果你有一个包含1000个元素(n = 1000)的ArrayList,则需要3秒(log 1000 = 3)才能在那里找到一个项目.虽然插入新元素需要1000秒.

另一方面,TreeMap需要3秒才能搜索和插入.