在LinkedHashMap上,TreeSet与LinkedHashSet和TreeMap的成本增加了多少？

Question

LinkedHashSet - 此实现使其客户端免受HashSet提供的未指定的,通常是混乱的排序,而不会导致与TreeSet相关的成本增加.

关于LinkedHashMap与TreeMap的说法相同

这个增加的成本(LinkedHashMap vs TreeMap)究竟是什么？

这是否意味着TreeSet每个元素需要更多内存？LinkedHashSet需要更多内存用于两个额外的链接,但TreeSet需要额外的内存来存储Map.Entry元素对(因为隐式地基于TreeMap),除了LinkedHashSet基于HashMap,它还具有Map.Entry元素开销对......

所以区别在于添加新元素的速度有多快(在TreeSet的情况下,由于某些"排序",它需要更长的时间).

什么是其他显着增加的成本？

Answer 1

TreeSet/ TreeMap有操作的更高的时间复杂度这样的屁股add(),contains()(对于TreeSet)put(),containsKey()(对TreeMap),等等,因为它们需要对数时间在树中找到的元素(或元素添加到树),而LinkedHashSet/ LinkedHashMap需要预设定时间对于那些操作.

在内存要求方面,存在很小的差异:

• TreeMap条目包含键,值,3个Entry引用(左,右,父)和a boolean.

• LinkedHashMap条目包含键,值,3个Entry引用(下一个,之前,之后)和一个int.