[Python 자료구조] Hash(해시)

 

파이썬에서 해시(Hash)는 어떻게 구현할 수 있을까요!?

파이썬에서는 Dictionary 라는 자료구조를 통해 해시를 제공합니다. 그리고 Dictionary는 dict클래스에 구현되어있습니다!

 

해시 언제 사용하면 좋을까?!

해시를 사용하면 좋을 때를 소개해드리고자 합니다 : )

 

1. 리스트를 쓸 수 없을 때 

리스트는 숫자 인덱스를 이용하여 원소에 접근하는데 즉 list[1]은 가능하지만 list['a']는 불가능합니다.

인덱스 값을 숫자가 아닌 다른 값 '문자열, 튜플'을 사용하려고 할 때 딕셔너리를 사용하면 좋습니다.

 

2. 빠른 접근  / 탐색이 필요할 때 

아래에서 표로 정리해 보여드릴 예정이지만, 딕셔너리 함수의 시간복잡도는 대부분 O(1)이므로 아주 빠른 자료구조 입니다!

 

3. 집계가 필요할 때

원소의 개수를 세는 문제는 코딩 테스트에서 많이 출제되는 문제입니다. 이때 해시와, collections 모듈의 Counter 클래스를 사용하면 아주 빠르게 문제를 푸실 수 있을 것입니다.

 

딕셔너리와 리스트의 시간 복잡도 차이

아까 위에서 딕셔너리의 시간 복잡도는 대부분 O(1)을 갖는다고 말씀드렸는데 리스트와 시간복잡도를 비교해보도록 하겠습니다.

Operation	Dictionary	List
Get Item	O(1)	O(1)
Insert Item	O(1)	O(1) ~ O(N)
Update Item	O(1)	O(1)
Delete Item	O(1)	O(1) ~ O(N)
Search Item	O(1)	O(N)

List에 비해 Dictionary가 매우 빠른 시간복잡도를 갖는 것을 보실 수 있습니다.

즉 , 원소를 넣거나 삭제, 찾는 일이 많을 때에는 딕셔너리를 사용하는 것이 좋습니다 

※ 파이썬 3.7 이상부터 딕셔너리는 원소가 들어온 순서를 보장합니다. 반면, 3.7 미만은 순서를 보장하지 않습니다. 딕셔너리를 이용해 문제를 풀 때에는 버전에 유의하세요.

 

Dictionary 사용법

📌 Init

{}를 사용하거나 dict함수 호출 시 빈 딕셔너리를 선언할 수 있습니다. 

key - value 쌍을 갖는 dictionary 선언도 바로 가능합니다.

# 빈딕셔너리 생성
dict1 = {} # {}
dict2 = dict() # {}

# 특정 key-value쌍을 가진 dictionary 선언

Dog = {
    'name': '동동이',
    'weight': 4,
    'height': 100,
}


'''
{'height': 100, 'name': '동동이', 'weight': 4}
'''

# dictionary를 value로 가지는 dictionary 선언

Animals = {
    'Dog': {
        'name': '동동이',
        'age': '5'
    },
    'Cat': {
        'name': '야옹이',
        'weight': 3
    }
}


'''
 { 'Dog': { 'name': '동동이', 'age': '5'},
   'Cat': {'name': '야옹이','weight': 3 }}
'''

 

📌 Get

Dictionary에서 원소를 가져오는 방법은 두가지 입니다.

1. [] 사용하기

2. get 메소드 이용하기

get 메소드는 get(key,x) 로 사용하실 수 있습니다. 이는 '딕셔너리에 key가 없는 경우, x를 리턴해줘라' 라는 용도입니다.

딕셔너리를 카운터하는 (집계) 경우에 get함수가 유용하게 사용됩니다.

# [] 기호 사용해 원소 가져오기

dict = {'하이': 300, '헬로': 180, 3: 5}
dict['헬로'] # 180

# get 메소드를 아용해 원소 가져오기 1
# 딕셔너리에 해당 key가 없을때 Key Error 를 내는 대신, 특정한 값을 가져온다.

dict = {'하이': 300, '헬로': 180}
dict.get('동동', 0) # 0

# get 메소드를 아용해 원소 가져오기 2
# 물론, 딕셔너리에 해당 key가 있는 경우 대응하는 value를 가져온다.

dict = {'하이': 300, '헬로': 180}
dict.get('헬로', 0) # 180

 

📌 Set

딕셔너리에 값을 집어넣거나, 값을 업데이트 할 때 [ ] 를 사용합니다.

# 값 집어넣기

dict = {'김철수': 300, 'Anna': 180}
dict['홍길동'] = 100
dict #{'Anna': 180, '김철수': 300, '홍길동': 100}

# 값 수정하기1

dict = {'김철수': 300, 'Anna': 180}
dict['김철수'] = 500
dict # {'Anna': 180, '김철수': 500}

# 값 수정하기2

dict = {'김철수': 300, 'Anna': 180}
dict['김철수'] += 500
dict # {'Anna': 180, '김철수': 800}

 

📌 Delete

딕셔너리에서 특정 key값을 지울 때에 다음과 같은 방법을 사용할 수 있습니다.

1. del dict_obj[key]

del은 키워드로써, 만약 딕셔너리에 key가 없다면 keyError가 발생합니다.

2. pop(key[,default])

pop은 메소드로써, pop메소드는 key 값에 해당하는 value를 리턴합니다. key가 없다면 두번째 파라미터인 default를 리턴합니다.

만약 default 설정하지 않았을 시엔 keyError가 발생합니다.

# del 이용하기 - 키가 있는 경우
dict = {'김철수': 300, 'Anna': 180}
del dict['김철수']

dict #{'Anna': 180}

# del 이용하기 - 키가 없는 경우 raise KeyError
my_dict = {'김철수': 300, 'Anna': 180}
del my_dict['홍길동'] 
'''
keyError 발생!
'''

# pop 이용하기 - 키가 있는 경우 대응하는 value 리턴
my_dict = {'김철수': 300, 'Anna': 180}
my_dict.pop('김철수', 180) # 300

# pop 이용하기 - 키가 없는 경우 대응하는 default 리턴
my_dict = {'김철수': 300, 'Anna': 180}
my_dict.pop('홍길동', 180) # 180

 

📌 Iterate

딕셔너리를 for문을 이용하여 조회할 때 두가지 방법이 존재합니다.

1. key로만 순회하기

2. key, value 동시 순회하기 (items() 사용)

# key로만 순회
dict = {'김철수': 300, 'Anna': 180}
for key in dict:
    print(key)
    # 이 경우 value를 찾고 싶으면 dict[key] 와 같이 접근을 따로 해주어야.

'''
김철수
Anna
'''

# key-value 동시 순회

dict = {'김철수': 300, 'Anna': 180}
for key, value in dict.items():
    print(key, value)

'''
김철수 300
Anna 180
'''

 

그 밖에 딕셔너리 유용한 팁

1. 특정 key가 딕셔너리에 있는지 없는지 조회할 때 - in 사용하기

dict = {'김철수': 300, 'Anna': 180}
print("김철수" in dict) #True
print("김철수" not in dict) # False

 

2. key 또는 value만 뽑아내는 방법

1. key 만 : keys()

# key를 extract - keys 사용


my_dict = {'김철수': 300, 'Anna': 180}
my_dict.keys() # dict_keys(['김철수', 'Anna'])

2. value만 : values()

# value를 extract - values 사용


my_dict = {'김철수': 300, 'Anna': 180}
my_dict.values() # dict_values([300, 180])

3. key - value 모두 : items()

# key, value 쌍을 extract - items 사용


my_dict = {'김철수': 300, 'Anna': 180}
my_dict.items() # dict_items([('김철수', 300), ('Anna', 180)])

 

 

오늘은 파이썬에서 해시를 구현하는 방법에 대해 정리해보았습니다. 딕셔너리 관련 내용이 더 궁금하시다면?! 아래 포스팅을 읽어주세요 : )

딕셔너리(Dictionary)

 

리스트(List) / 딕셔너리(Dictionary) 정렬

 

 

 

참고

TimeComplexity - Python Wiki