HashMap vs ArrayList性能我是正确的

Question

我目前相信:

• 当您需要一个随机检索项目的结构时 - 使用a HashMap
• 当您按顺序检索项目时(例如使用for循环) - 使用 ArrayList

我一般都对吗？是否存在不正确的情况？

Answer 1

Map是地图或"关联数组".它有一个键 - >值布局.另一方面,List是一个列表,它是一个有序的元素集合.

更直接的比较可能是在Set和List 之间:这两个都保持值,其中列表是显式排序的(你可以获得元素#x),并且该集合(通常)不是有序的(好吧,除非它是SortedSet,在这种情况下,迭代订单将由比较器订购).

Set和List的两个最常见的实现是HashSet和ArrayList.要检查元素是否属于arraylist(contains(element)),实现将遍历它的所有元素,检查是否使用equals()方法找到了元素.要检查元素是否属于散列集,首先计算元素的hashCode(),然后"直接"到该元素应该驻留的位置,并检查它是否存在.

因此,ArrayList和HashSet之间的显着差异是contains()的速度.

在列表中,您可以询问元素#x,以及您可以对集合执行的操作,即添加,删除,询问是否存在(包含)以及迭代所有元素.

在地图上,您可以按键来索取元素,而不是像列表那样索引索引.

HashSet目前仅由HashMap实现,其中不使用key-> value关系的值部分.这是完全荒谬的,除了浪费至少4个字节之外没有任何用处,可以争论12,插入HashSet中的每个和所有元素.

Answer 2

一般来说,是的,你是对的.还有一个组合数据结构LinkedHashMap,它提供对任意元素的快速访问以及可预测的排序.

但是,值得注意的是ArrayList和HashMap分别只是List和Map接口的两种实现.每种方法的其他实现可能更适合更具体的要求.例如,对于某些排队/出队要求,LinkedList可能比ArrayList提供更高的性能.

Answer 3

我会说你一般都是正确的,但并不完全准确.您使用HashMap数据检索,但不总是随机.您使用ArrayListfor迭代,但您也可以通过索引使用它进行查找.

更一般地说,Map当您需要通过查找有效地检索项目时,即使用基于密钥检索某些内容(例如字典,高速缓存,存储库等)时,可以使用实现.

您可以使用一个List实现时,你只想要一个数据结构,其中,当你希望他们在预定的和/或可预测的顺序,你可以遍历数据,通常.

换句话说,您使用Maps作为索引数据结构,并使用Lists,就像通常使用数组一样.

Answer 4

别忘了，使用映射（如果有键）到达一个特定项的速度比从数组中获得特定项的速度要快得多（除非有索引，但是键总是可以为您提供正确的值，而拥有键如果插入了新元素或删除了旧元素，则索引可能无法工作）。