[문법] 해시테이블 개념 및 구현(Python)

해시 테이블

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다.

 

해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다.

덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다.

 

해시 함수

해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.

• 해시 함수 값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 값이 균일하게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높을 것

 

해싱

해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 말한다.     h(x) = x mod m

 

 

• 로드 팩터(Load Factor)

해시테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다.     load factor = n / k

자바 10에서는 해시맵의 디폴트 로드 팩터를 0.75로 정했으며 '시간과 공간 비용의 적절한 절충안'이라고 얘기한다.

 

• 개별 체이닝

1. 키의 해시 값을 계산한다.
2. 해시 값을 이용해 배열의 인덱스를 구한다.
3. 같은 인덱스가 있다면 연결 리스트로 연결한다.

 

• 오픈 어드레싱

1. 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식 (선형 탐사)
2. 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.
3. 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다.
4. 오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없다.

 

구현 (Python)

from hashtable.structures import MyHashTable


def test_hashtable():
    ht = MyHashTable()

    ht.put(1, 1)	# key값과 value값을 넣어준다
    ht.put(2, 2)
    assert ht.get(1) == 1
    assert ht.get(3) == -1	# key값이 없다면 -1을 출력

    ht.put(2, 1)
    assert ht.get(2) == 1	# key값에 새로운 value를 넣어주면 대체된다.

    ht.remove(2)
    assert ht.get(2) == -1	# remove시 삭제


def test_birthday_problem():
    import random
    TRIALS = 100000
    same_birthdays = 0

    for _ in range(TRIALS):
        birthdays = []
        for i in range(23):
            birthday = random.randint(1, 365)
            if birthday in birthdays:
                same_birthdays += 1
                break
            birthdays.append(birthday)

    print(f"{same_birthdays / TRIALS * 100}%")


if __name__ == "__main__":
    test_birthday_problem()
    test_hashtable()