python 해시 테이블

이번 시간에는 python 해시 관련하여 알아본다. python 해시 테이블 방식과 dict 자료형을 알아보고 자주 사용되는 모듈을 알아본다.

1. 파이썬 해시 테이블

chaining vs Linear probing

 파이썬에서 해시 테이블로 구현된 자료형은 딕셔너리다. 그렇다면 파이썬의 해시 테이블은 충돌 시 어떤 방식을 사용할까? 파이썬에는 오픈 어드레싱 방식으로 구현되어 있다. 파이썬에서 오픈 어드레싱 방식을 사용한 이유는 체이닝 시 malloc으로 메모리 할당하는 오버헤드가 높아서 오픈 어드레싱을 선택했다고 한다.

오픈 어드레싱 방식은 체이닝에 비해 성능이 좋다. 하지만 슬롯이 80% 이상 차게 되면 급격하게 성능 저하가 일어나며, 체이닝과 달리 로드 팩터 1 이상은 저장할 수 없다. 따라서 파이썬은 오픈 어드레싱 방식을 택해 성능을 높이지만 로드 팩터를 작게 잡아 성능 저하 문제를 해결한다. 파이썬 로드 팩터는 0.66으로 설정되어 있다.

언어	방식
C++	개별 체이닝
Java	개별 체이닝
Go	개별 체이닝
Ruby	오픈 어드레싱
Python	오픈 어드레싱

---

2. 파이썬 딕셔너리

파이썬 딕셔너리는 키/값 구조로 이뤄져 있다. 파이썬 3.7 이상에서는 입력 순서가 유지되며, 내부적으로는 해시 테이블로 구현되어 있다. 대부분의 언어에서는 딕셔너리는 입력 순서가 유지되지 않는다. 파이썬도 3.6 이하에서는 입력 순서가 보장되지 않아 순서를 유지하고 싶은 경우 collections.OrderedDict()를 사용해야한다.

2-1. 딕셔너리 주요 연산 시간 복잡도

딕셔너리의 시간 복잡도는 아래와 같다. dict 타입 외 다른 타입은 위키 사이트에서 확인한다.

연산	평균 시간복잡도	설명
len(a)	O(1)	요소의 개수 리턴
a[key]	O(1)	키를 조회하여 값 리턴
a[key] = value	O(1)	키/값을 삽입
key in a	O(1)	딕셔너리에 키가 존재하는지 확인

2-2. 딕셔너리 사용 방법

# 1. dict 선언 
a = dict()   # 혹은  a = dict()
a = {"key1":1, "key2": 2}
a["key3"] = 3

# 2. KeyError 예외처리
print(a['key4'])    # KeyError: 'key4'

try:
    print(a['key4'])
except KeyError:
    print('존재하지 않는 키')

# 3. 예외처리 대신 키 존재 확인
if 'key4' in a:   # '없다' 출력 
    print('존재')
else:
    print('없다')

# 4. dict 반복문
for k, v in a.items():  # key, vlaue 모두 얻음
    print(k,v)

for k in a:   # key만 얻음
    print(k)

for v in a.values():  # value만 얻음 
    print(v)

# 5. 삭제
del a['key1']  
print(a)      # {'key2': 'value2', 'key3': 'value3'}

 

---

3. 딕셔너리 모듈

딕셔너리와 관련된 모듈에 대해서 알아본다.

3-1. defaultdict 객체

defaultdict 객체는 이름 그대로 디폴트 값이 있는 dict이다. 원래 dict는 존재하지 않는 키를 조회하는 경우, 에러가 발생한다. 하지만 이 객체를 사용하면 에러를 출력하는 대신 디폴트 키를 기준으로 해당 키에 대한 딕셔너리를 생성합니다. 자세한 객체 사용법은 python doc 사이트에서 확인 가능하다. 

일반적인 dict 사용하는 경우

해당 키를 정의하지 않고, 호출하는 경우 KeyError 에러가 발생한다.

my_dict = dict()
my_dict["a"]

> 실행 결과: KeyError: 'a'

defaultdict 사용하는 경우

에러가 발생하지 않고, 기본 값으로 디폴트를 정해준다.

import collections    # defaultdict 사용하기 위한 모듈     

default_dict = collections.defaultdict(int)  # int로 디폴트 dict 생성
default_dict['a']
default_dict['b'] += 1                       # 기본값 0에 +1 
print(default_dict)

> 실행 결과: defaultdict(<class 'int'>, {'a': 0, 'b': 1})

 

3-2. Counter 객체

 동일한 값이 몇 개가 존재하는지 dict 형식으로 리턴한다. 아래의 예제를 보면 알파벳 값이 몇 개 있는지 출력한다. 자세한 객체 사용법은 python doc 사이트에서 확인 가능하다. 

import collections    # Counter 사용하기 위한 모듈 

a = ["a", "b", "c", "a", "b", "b" ]
counter_dict = collections.Counter(a)
print(counter_dict)                      # Counter({'b': 3, 'a': 2, 'c': 1})
print(counter_dict.most_common(2))       # 상위 2개 리턴. [('b', 3), ('a', 2)]
print(counter_dict.most_common(1)[0][0]) # 가장 우선순위가 높은 것.  b

 

3-3. OrderedDict 객체

대부분의 언어에서는 해시 테이블을 이용한 자료형은 입력 순서가 유지되지 않는다. 파이썬 3.6 이하에서도 마찬가지로 입력 순서가 유지되지 않아서 OrderedDict라는 별도의 객체를 제공한다. 입력 순서가 중요한 경우는 해당 객체를 사용해서 적용하도록 한다.

파이썬 3.6 이하에서 진행한 경우

아래는 파이썬 2.7에서 진행하였는데, 입력한 그대로 순서가 유지되지 않고 출력되는 것을 확인할 수 있다.

my_dict = dict()
my_dict['a'] = 1
my_dict['b'] = 2
my_dict['c'] = 3
print(my_dict)     # {'a': 1, 'c': 3, 'b': 2}

파이썬 3.6 이하에서 진행한 경우 + OrderedDict 사용

OrderedDict를 써서 dict 순서가 유지되는 것을 확인할 수 있다.

import collections
ordered_dict = collections.OrderedDict()
ordered_dict['a'] = 1
ordered_dict['b'] = 2
ordered_dict['c'] = 3
print(ordered_dict)  # OrderedDict([('a', 1), ('b', 2), ('c', 3)])

---

4. 해시 관련 문제

 해시 관련 문제는 아래와 같다. 해시를 잘 다루기 위해 아래 문제들을 푸는 것을 권장한다. 

문제명	사이트 종류	url
완주하지 못한 선수	프로그래머스	programmers.co.kr/learn/courses/30/parts/12077
전화번호 목록	프로그래머스	programmers.co.kr/learn/courses/30/lessons/42577
위장	프로그래머스	programmers.co.kr/learn/courses/30/lessons/42578
베스트 앨범	프로그래머스	programmers.co.kr/learn/courses/30/lessons/42579
771. Jewels and Stones	리트코드	leetcode.com/problems/jewels-and-stones/
듣보잡	백준	www.acmicpc.net/problem/1764
회사에 있는 사람	백준	www.acmicpc.net/problem/7785
347. Top K Frequent Elements	리트코드	leetcode.com/problems/top-k-frequent-elements/