해시 테이블 (Hash Table) with 파이썬

C언어로 해시 테이블을 먼저 구현해 본 나에게는 파이썬에서 이렇게 간단하게 불러서 쓸 수 있다니.. 놀랍기만 합니다.

 

파이썬에서의 해시 테이블은 딕셔너리라는 이름으로 구현되어 있습니다.

 

딕셔너리가 없는 언어에서는

 

1. 배열로 hash Table 생성

2-1. 키값을 입력 시 해시값을 변환해주는 함수 생성

2-2. 해시으로 해시테이블에 저장하는 함수

 

이렇게.. 보통 해시 테이블은 연속되지 않은 값들 혹은 문자가 들어간 값들을 한번에 찾을 때 사용하면 시간이 많이 단축됩니다.

 

해시 테이블의 장점 단점

 

장점

• 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
• 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움

 단점

• 일반적으로 저장공간이 좀더 많이 필요하다.
• 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함

주요 용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현시 (중복 확인이 쉽기 때문)

 

list의 어떤 자료를 검색할 때 드는 시간복잡도 O(n)
Hash Table의 자료를 검색할 때 드는 시간복잡도 O(1)

 

무려 시간복잡도가 n >> 1로 바뀌는 결과를 볼 수 있습니다.

---------------------------------------------------------------

 

 

이를 활용한 문제를 풀어보면

 

 

완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

def solution(participant, completion):
    sum = 0
    dic = {}
    for x in participant:
        dic[hash(x)] = x
        sum += hash(x)
    for x in completion:
        sum -= hash(x)
    answer = dic[sum]
    return answer

 

이 문제는 응용이 필요하다 다른 사람의 풀이를 보면 collections의 counter를 사용하기도 하는데

핵심은 키값 >> 해시값 >> 키값 의 왕래가 자유롭다는 점이다.

 

 

전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

def solution(phone_book):
    dic = {}

    for x in phone_book:
        dic[x] = 0

    for x in phone_book:
        temp = ""
        for y in x:
            temp += y
            if temp in dic and temp != x:
                return False

    return True

 

 

다른 풀이들을 참고하면 sort를 하여 x번과 x+1번의 숫자만 검사하도록 풀이를 하는 사람들도 있었습니다.

하지만 이 풀이 방법에서 볼 것은 sort를 하지 않았는데도 통과할 수 있는 시간이 되었는데 그 비밀은

문자를 한 글자씩 추가해서 돌지만 temp in dic 을 실행할 때 딕셔너리 즉 해시로 탐색을 하기 때문에

list처럼 O(n)이 아닌 O(1)번씩 탐색하게 됩니다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

def solution(clothes):
    dic = {}

    for i in clothes:
        if i[1] in dic:
            dic[i[1]] += 1
        else:
            dic[i[1]] = 1

    cnt = 1
    for i in dic.values():
        cnt *= (i + 1)

    return cnt - 1

이번 문제는 위에 완주하지 못한 선수와 비슷한 문제로 종류별로 갯수를 구한 뒤 곱해주면 됩니다..

 

 

 

 

 

 

참고:

https://wikidocs.net/154782