leetcode easy : Design HashSet

https://leetcode.com/problems/design-hashset/

LeetCode - The World's Leading Online Programming Learning Platform

 

직접 해시셋을 만드는 문제다.

대충 해시함수를 만들고

버킷을 만들어서 구현했다.

class MyHashSet:
    def __init__(self):
        self.capacity = 10000
        self.buckets = [[] for _ in range(self.capacity)]
        
    def _hash(self, key) -> int:
        return (key * 84293461 + 347281) % self.capacity

    def add(self, key: int) -> None:
        h = self._hash(key)
        if key not in self.buckets[h]:
            self.buckets[h].append(key)

    def remove(self, key: int) -> None:
        h = self._hash(key)
        try:
            self.buckets[h].remove(key)
        except ValueError:
            pass

    def contains(self, key: int) -> bool:
        h = self._hash(key)
        return key in self.buckets[h]

시간복잡도는 대충 O(avg(bucket size))일거같긴 한데 해시함수를 그냥 아무 숫자나 적어서 만든거라 얼마나 고르게 분포될진 모르겠다.