编码性能差异:数组与哈希

Question

我进行了代码性测试：https：//codility.com/programmers/programmers/lessons/2-arrays/odd_occurrences_in_array/，我注意到两个不同的解决方案之间的性能差异：

1-列表解决方案：

def solution(list)
  unmatched_elements = []
  list.each{ |el|
    if unmatched_elements.include? el
      unmatched_elements.delete el
    else
      unmatched_elements.push el
    end
  }
  unmatched_elements[0]
end

2-哈希解决方案

def solution(a)
  unmatch = {}
  a.each do |e|
    if unmatch[e].nil?
      unmatch[e] = 1
    else
      unmatch.delete e
    end
  end
  unmatch.keys.first
end

第一个为我带来了25％的表现得分。第二个给了我100％的性能得分。这是为什么？我竭尽全力将hash推到列表中会导致o（n）空间的复杂性，但似乎不是，为什么？

Answer 1

这与空间复杂性无关，而是时间复杂性。具体来说，在数组中查找元素（include?）是n时间操作，因为它需要检查每个元素直到有匹配。哈希查找[]是恒定的时间。

此答案解释了为什么哈希有o（1）搜索时间：https：//stackoverflow.com/a/4363602/1034681