[Python] 자료구조 : 해시(Hash) 개념 및 사용

해시란?

해시/해쉬(Hash)는 해시 테이블로 Key, Value를 매핑해서 데이터를 저장하는 자료구조이다.

파이썬에서는 기본적으로 제공되는 딕셔너리 자료형이 해시 테이블과 같은 구조이다.!

 

용어

키(Key) - 고유의 값으로 해시 함수의 Input, 다양한 길이의 값이 될 수 있다.

해시테이블(Hash Table) 또는 해시 맵(Hash Map) - Key와 Value를 매핑해서 데이터를 저장하는 자료구조

해시 함수(Hash Function) - 임의의 값을 고정된 길이의 데이터로 변환하는 함수. 다양한 길이의 키를 고정된 길이의 해시로 변환시키므로 저장소를 효율적으로 운영

해시(Hash) - 해시함수의 Output으로 해시값과 매칭되어 버킷에 저장

해시 값(Hash Value) 또는 해시 주소(Hash Address) - Key에 해시함수를 적용하여 얻는 해시 값

버킷(Bucket) - 한 개의 데이터를 저장할 수 있는 공간

 

 

다양한 길이를 갖고있는 키 값에 해시 함수를 적용시키면 00, 01, 02 등과 같이 고정된 길이의 데이터로 변환한다. 이렇게 변환된 데이터가 해시 값이고 버킷에는 키와 매핑된 원래 데이터를 저장한다. 결과적으로 변환된 키값과 버킷에 매핑되어 있는 데이터를 해시라 하고이러한 자료구조를 해시 테이블 이라 한다.

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

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

 

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)])