Codility性能差異：陣列VS散列

Question

我在codility做了一個試驗：https://codility.com/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）空間複雜度像一個List，但它似乎不是，爲什麼？

Answer 1

這不是空間複雜性，而是時間複雜性。具體而言，查找數組中的元素（include?）是N次操作，因爲它需要檢查每個元素直到匹配。哈希查找[]是恆定時間。

這樣的回答解釋了爲什麼散度爲O（1）搜索時間：https://stackoverflow.com/a/4363602/1034681