Pythonのlist、setにおける time complexity について

217. Contains Duplicateを解いていた際に、time exeedエラーになってしまったので、少し詳しく調べてみました。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hash_map = set()
        for n in nums:
            if n in hash_map:
                return True
            hash_map.add(n)
        return False

上記は submit （hash_map.add は hash_map.append に変更した上）できるが、

hash_map = [] 

として、（hash_map.add は hash_map.append に変更した上）submit したところ、
time exeedエラーになってしまった。

エラーが発生したと考えられる原因

• 追加における time complexty の差
• 検索における time complexity の差

list set の追加について

Time complexity for adding elements to list vs set in pythonの回答によると、
list と set の追加は、
O(1) amortized time-complexity

ただし、setへの追加は、hash関数を使ったり、hash collisions をチェック、処理が必要となる。

なぜ、hash関数を使う必要があるか？
Python の set は hashtable を使って実装されているため。

How is set() implemented?

list と set の検索について

Python wikiによると、setのほうが早いことがわかる。

	Average	Worst
list	O(n)
set	O(1)	O(n)

まとめ

追加は list の方が少しだけ早く、
検索についてsetの方が早いということを確認すると、
list の検索が遅いのが原因で、
timeexeedエラーになったように見受けられる。