[PYTHON] SET은 왜 O(1)의 시간복잡도를 가질까

SET이 빠른 이유 

set은 데이터를 해싱하여 내부적으로 해시 테이블에 저장합니다. 해시 테이블의 경우 해시 함수를 주어진 입력에 대해서 해시 키 값이 존재하기에 인덱싱이 매우 빠르다. 또한 파이썬의 set은 내부적으로 c언어로 구현되어 있어 파이썬 인터프리터보다 빠르다. 또한

set은 중복을 허용하지 않기에 데이터의 크기가 작아져서 해시테이블의 충돌을 방지하며 연산 속도를 향상시킨다

 

따라서 set은 대용량 데이터를 다룰 때에도 빠른 속도를 보장할 수 있다.

 

하지만, set은 해시 함수의 충돌(Collision) 문제를 고려해야 한다. 충돌은 서로 다른 두 개의 키가 동일한 해시값을 가질 때 발생합니다. 충돌이 발생하면 set은 해시 테이블에서 다른 곳에 해당 요소를 저장합니다. 

 

Set에서 사용되는 해시 함수

MurmurHash 알고리즘을 사용한다고 되어 있다.

 

해시 함수의 충돌 처리 방법

파이썬의 set은 내부적으로 충돌 처리를 위해 해시 충돌 해결(Collision Resolution) 알고리즘 중 하나인 개방 주소법(Open Addressing)을 사용합니다. 개방 주소법은 충돌이 발생하면 해시 테이블에서 다른 빈 슬롯을 찾아 해당 요소를 저장합니다.

 

파이썬 set은 선형 조사(Linear Probing) 방식을 사용하여 해시 충돌을 처리합니다. 선형 조사 방식은 충돌이 발생한 슬롯 다음 슬롯부터 순차적으로 빈 슬롯을 찾아 저장하는 방식입니다.

 

아래의 코드는 연결리스트 체이닝 방식을 사용한 선형 조사 방식을 구현한 것입니다.

class HashTable:
    def __init__(self, size=10):
        """
        HashTable 클래스의 생성자입니다.
        size: 해시 테이블의 크기입니다. 기본값은 10입니다.
        """
        self.size = size
        # 빈 리스트로 구성된 리스트를 생성합니다.
        # 리스트의 각 원소는 해당 인덱스에 대응하는 연결 리스트를 저장합니다.
        self.table = [[] for _ in range(self.size)]

    def _hash_function(self, key):
        """
        키에 대한 해시값을 반환하는 내부 함수입니다.
        key: 해싱할 키입니다.
        """
        return hash(key) % self.size

    def insert(self, key, value):
        """
        키와 값을 받아서 해시 테이블에 저장합니다.
        이미 존재하는 키라면 값을 업데이트합니다.
        key: 해싱할 키입니다.
        value: 키에 대응하는 값입니다.
        """
        # 키의 해시값을 구합니다.
        index = self._hash_function(key)
        # 해당 인덱스의 연결 리스트를 가져옵니다.
        slot = self.table[index]
        # 연결 리스트를 순회하면서 같은 키를 갖는 데이터를 찾습니다.
        for item in slot:
            if item[0] == key:
                # 같은 키를 갖는 데이터가 이미 존재한다면 값을 업데이트하고 함수를 종료합니다.
                item[1] = value
                return
        # 같은 키를 갖는 데이터가 존재하지 않는다면 연결 리스트에 새로운 데이터를 추가합니다.
        slot.append([key, value])

    def search(self, key):
        """
        키를 받아서 해당하는 값을 반환합니다.
        존재하지 않는 키라면 None을 반환합니다.
        key: 검색할 키입니다.
        """
        # 키의 해시값을 구합니다.
        index = self._hash_function(key)
        # 해당 인덱스의 연결 리스트를 가져옵니다.
        slot = self.table[index]
        # 연결 리스트를 순회하면서 같은 키를 갖는 데이터를 찾습니다.
        for item in slot:
            if item[0] == key:
                # 같은 키를 갖는 데이터가 존재하면 해당 값을 반환합니다.
                return item[1]
        # 같은 키를 갖는 데이터가 존재하지 않으면 None을 반환합니다.
        return None

    def delete(self, key):
        """
        키를 받아서 해당하는 데이터를 삭제합니다.
        key: 삭제할 키입니다.
        """
        # 키의 해시값을 구합니다.
        index = self._hash_function(key)
        # 해당 인덱스의 연결 리스트를 가져옵니다.
        slot = self.table[index]
        # 연결 리스트를 순회하면서 같은 키를 갖는 데이터를 찾습니다.
        for i, item in enumerate(slot):
            if item[0] == key:
                # 같은 키를 갖는 데이터가 존재하면 해당 데이터를 삭제합니다.
                del slot[i]
                return