为什么迭代地图比迭代列表要慢？

Question

在面试中有人问我这个问题，面试官想讨论我能想到的所有方法的权衡问题：

设计并实现TwoSum类。它应该支持以下操作：添加和查找。

添加-将数字添加到内部数据结构中。
find-查找是否存在总和等于该值的数字对。

我首先提出了以下解决方案，这非常简单。

设计1：

public class TwoSumDesign1 {
  private final Map<Integer, Integer> map = new HashMap<Integer, Integer>();

  public void add(int number) {
    map.put(number, map.getOrDefault(number, 0) + 1);
  }

  public boolean find(int value) {
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
      int i = entry.getKey();
      int j = value - i;
      if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {
        return true;
      }
    }
    return false;
  }
}

但是经过一些研究，我发现我们可以使用List来存储所有数字，并且迭代列表比迭代要快keySet，但是我仍然不明白为什么？

引用自：https : //docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

集合视图上的迭代所需的时间与HashMap实例的“容量”（存储桶数）及其大小（键-值映射数）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得过高（或负载因子过低），这一点非常重要。

设计2：

public class TwoSumDesign2 {
  private final List<Integer> list = new ArrayList<Integer>();
  private final Map<Integer, Integer> map = new HashMap<Integer, Integer>();

  // Add the number to an internal data structure.
  public void add(int number) {
    if (map.containsKey(number))
      map.put(number, map.get(number) + 1);
    else {
      map.put(number, 1);
      list.add(number);
    }
  }

  // Find if there exists any pair of numbers whose sum is equal to the value.
  public boolean find(int value) {
    for (int i = 0; i < list.size(); i++) {
      int num1 = list.get(i), num2 = value - num1;
      if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2)))
        return true;
    }
    return false;
  }
}

谁能解释在这个问题上我们应该考虑的所有折衷方案，以及为什么第二个解决方案比迭代地图更快keySet？

Answer 1

首先，让我提一下，我们正在谈论的性能差异几乎不值得考虑。“因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低）非常重要”这句话具有误导性。这不是很重要。我宁愿说“因此，您可能不想设置初始容量......”

既然我们已经涵盖了这一点，让我们继续讨论实际答案。

与列表的简单组织相比，它与哈希映射的内部数据结构的组织方式有关。

散列映射的标准实现采用“桶”列表，其中每个桶是节点的链表。键和值存储在这些节点中。存储桶列表并不密集，这意味着许多条目都是null.

因此，为了遍历映射的所有键，您必须遍历桶列表，并且对于每个桶，遍历桶中的节点。

由于节点的数量和键的数量一样多，节点的遍历与整个遍历的时间复杂度相同ArrayList，但是在哈希映射的情况下，我们还必须计算遍历的开销存储桶列表。并且hashmap的“初始大小”越大，或者填充因子越小，nullbucket就会越多，这意味着bucket列表中的条目会越多，你会徒劳地访问，才发现出他们是null并继续下一个条目。

因此，遍历 aHashMap比遍历 an 稍贵ArrayList。

但相信我，差异是如此之小，以至于不值得考虑。没有人会注意到。为您的目的使用正确的数据结构要好得多，而不必担心性能上的微小提升。正确的数据结构始终是产生最优雅解决方案的数据结构。最优雅的解决方案是最容易阅读和理解它做什么以及它是如何做的。