TreeMap或HashMap更快 [英] TreeMap or HashMap faster

问题描述

我正在编写一个字典，它大量使用String作为 Map< String，Index> 中的键。我关心的是 HashMap 和 TreeMap 中的哪一个会在搜索中的一个键时获得更好（更快）的性能map？

I am writing an dictionary that make heavily use of String as key in Map<String, Index>. What I concern is which one of HashMap and TreeMap will result in better (faster) performance in searching a key in the map?

推荐答案

鉴于没有太多的碰撞，hashmaps会给你o（1）性能（这有很多的结果）可以降级到潜在的O（n），其中N是任何一个桶中的条目数（colissions）。另一方面，如果您想要某种平衡的树结构来生成O（logN）检索，则使用TreeMaps。所以它真的取决于你的特定用例。但是如果你只想访问元素，不管它们的顺序如何都使用HashMap

Given that there are not many collissions hashmaps will give you o(1) performance (with a lot of colissions this can degrade to potentially O(n) where N is the number of entries (colissions) in any single bucket). TreeMaps on the other hand are used if you want to have some sort of balanced tree structure which yields O(logN) retrieval. So it really depends on your particular use-case. But if you just want to access elements, irrespective of their order use HashMap

这篇关于TreeMap或HashMap更快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！