[Algorithm] 해시테이블(Hash Table) - Python

문지은·2024년 2월 13일

algorithm data structure python

Algorithm with Python

목록 보기

17/19

DAT(Direct-address Table)

Direct-address Table(직접 주소화 테이블) : key값이 $k$ 인 데이터를 index $k$ 위치에 저장하는 방식

key: 출석번호, value: 이름

(3, 문지은)
(5, 박서희)
(6, 최지수)
(7, 송아람)

직접 주소화 방법을 통해 key-value 쌍의 데이터를 저장하고자 하면 많은 문제가 발생한다.

문제점 1) 불필요한 공간 낭비

key: 학번, value: 이름

(2022390, 문지은)
(2022392, 박서희)
(2022393, 송아람)
(2022401, 최지수)

문제점 2) Key값으로 문자열이 올 수 없다.

key: ID, value: 이름

(jieun123, 문지은)
(jisoo123, 최지수)
(quokka123, 박서희)
(aram123, 송아람)

Hash table

위와 같은 이유로, 직접 주소화 방법은 (key, value) 데이터 쌍을 저장하기 위한 방법으로 잘 맞지 않다.
대안으로, Hash table을 이용할 수 있다.
Hash table은 hash function $h$ 를 활용해서 (key, value) 를 저장한다. key값을 $k$ 라고 했을 때, $h(k)$ 함숫값에 해당하는 index에 (key, value) 데이터 쌍을 저장한다.
- 따라서 흔히 “ $h(k)$ 는 키 $k$ 의 해시값이다”라고 표현한다.
모든 데이터에 key값은 무조건 존재해야 하며, 중복되는 key값이 있어서는 안 된다.
(key, value) 데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 한다.

Collision

collision이란 서로 다른 key의 해시값이 똑같을 때를 말한다.
즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데 이때 collision이 발생했다고 한다.
- 따라서 collision이 최대한 적게 나도록 hash function을 잘 설계해야 하고, 어쩔 수 없이 collision이 발생하는 경우 seperate chaining 또는 open addressing 등의 방식을 사용하여 해결한다.
- Python의 dictionary는 open addressing 방식을 채택하고 있다.

💡 Separate Chaining vs Open Addressing

Separate Chaining

데이터 삽입 시, 버킷 혹은 슬롯에 연결리스트를 할당

만약 같은 해시값에 의해 해시 충돌이 발생하면, 연결리스트를 이어서 해시 충돌을 방지하고자 하는 방식

버킷이 모두 채워진 상태여도, 연결리스트로 데이터를 연결 짓기 때문에 한 번 정해진 데이터의 주솟값은 영구적으로 유지되며, 이를 Closed Addressing이라고도 부른다.

장점

단순한 연결리스트만을 활용한다.

해시테이블이 채워지면서, 탐색에 대한 성능 저하가 선형적으로 발생한다.

Open Addressing

데이터를 삽입할 때, 버킷 혹은 슬롯에 연결리스트를 만들지 않는다. 다만, 해시 충돌이 발생한다면, 다른 비어있는 버킷에 데이터를 저장한다.

선형 탐색, 제곱 탐색, 이중 해시 등 비어있는 버킷 탐색 방식에 따라 내부 알고리즘이 다를 수 있다.

장점

해시테이블 자체만을 저장공간으로 활용하기 때문에, 추가적인 저장공간이 필요하지 않다.

삽입, 삭제 시, 발생하는 오버헤드가 적다.

상대적으로 데이터가 적을 때, 체이닝 방식보다 유리하다.

시간 복잡도와 공간 효율성

시간 복잡도는 저장, 삭제, 검색 모두 기본적으로 $O(1)$ 이다.
- 다만 collision으로 인하여 최악의 경우, $O(n)$ 이 될 수 있다.
공간 효율성 측면에서는 성능이 떨어진다.
- 데이터가 저장되기 전에 미리 저장공간(slot, bucket)을 확보해야 하기 때문이다.
- 따라서 저장공간이 부족하거나 채워지지 않은 부분이 많은 경우가 발생할 수 있다.

	Hash table	Linked list	Array
access	$O(1)$	$O(n)$	$O(1)$
insert	$O(1)$	$O(1)$	$O(n)$
append	$O(1)$	$O(1)$	$O(1)$
delete	$O(1)$	$O(1)$	$O(n)$

Python 해시테이블 사용법

Dictionary

Hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value 쌍을 데이터로 입력받는다.
hash function $h$ 에 key값을 입력값으로 넣어 얻은 해시값 $h(k)$ 를 위치로 지정하여 key-value 데이터 쌍을 저장한다.
Dictionary는 hash table로 구현된 python의 유일한 매핑(mapping)형이며, 해시 가능한(hashable) 데이터를 임의의 객체에 대응되도록 한다.

# {'a':1, 'b':2, 'c':3}
hash_table = {'a':1, 'b':2, 'c':3}
hash_table = dict(a=1, b=2, c=3)

Dictionary 사용법

파이썬에서 dictionary를 사용할 때, key를 index처럼 생각해서 사용하면 된다.
따라서 dictionary[key] = value 같은 형식으로 각 key-value 쌍을 입력하면 된다.

dictionary 선언 및 초기화

# 예시) (학번, 이름)을 (key, value)로 가지는 딕셔너리 만들기
# 원하는 결과 : {2022390: '문지은', 2022392: '박서희', 2022393: '송아람', 2022401: '최지수'}

student_info = {}
student_info[2022390] = "문지은"
student_info[2022392] = "박서희"
student_info[2022393] = "송아람"
student_info[2022401] = "최지수"

한 번에 초기화하는 방법도 다양하게 존재한다.

a = dict(one=1, two=2, three=3)
b = {'one': 1, 'two': 2, 'three': 3}
c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
d = dict([('two', 2), ('one', 1), ('three', 3)])
e = dict({'two':2, 'three':3}, two=2)

# a == b == c == d == e

dictionary 컴프리헨션

# list처럼 컴프리헨션도 사용할 수 있다.
f = {i:i**2 for i in range(4) if (i % 2 == 0)} 

print(f) # {0:0, 2:4}

# 사용 예시 (70점 이상의 점수를 받은 학생들에 대한 정보를 담은 dictionary 만들기)
name = ['bob', 'sam', 'maria', 'david', 'nancy']
score = [30, 50, 80, 92, 83]
result_dict = {name[i]:score[i] for i in range(len(name)) if score[i] >= 70}

print(result_dict) # {'maria': 80, 'david': 92, 'nancy': 83}

Dictionary 주요 메서드

위에 만들었던 예시를 이용해서 주요 메서드의 사용 방법을 알아보자.

student_info = {}
student_info[2022390] = "문지은"
student_info[2022392] = "박서희"
student_info[2022393] = "송아람"
student_info[2022401] = "최지수"

print(student_info)
# {2022390: '문지은', 2022392: '박서희', 2022393: '송아람', 2022401: '최지수'}

dictionary.items()

key 와 value 모두 접근할 때 사용

print(student_info.items())

# dict_items([(2022390, '문지은'), (2022392, '박서희'), (2022393, '송아람'), (2022401, '최지수')])

for student_id, name in student_info.items():
    print(student_id, name)

'''
2022390 문지은
2022392 박서희
2022393 송아람
2022401 최지수
'''

dictionary.keys()

dictionary의 key들을 접근할 때 사용

print(student_info.keys())

# dict_keys([2022390, 2022392, 2022393, 2022401])

for student_id in student_info.keys():
    print(student_id)

'''
2022390
2022392
2022393
2022401
'''

dictionary.values()

dictionary의 value들을 접근할 때 사용

print(student_info.values())

# dict_values(['문지은', '박서희', '송아람', '최지수'])

for name in student_info.values():
    print(name)

'''
문지은
박서희
송아람
최지수
'''

dictionary.get()

key에 해당하는 value을 가져올 때 사용

print(student_info.get(2022390))  # 문지은

만약 존재하지 않는 값을 가져오면 None 반환

print(student_info.get(1111))  # None

존재하지 않는 값을 가져올 경우, default를 지정할 수도 있다.

print(student_info.get(1111, "서지현"))  # 서지현

조금 더 응용하면, 매우 편리하게 사용할 수 있다.

if 3 not in a:
	a[3] = 1
else:
	a[3] += 1

위와 같은 코드를 단 1줄만으로 작성할 수 있게 된다.

a[3] = 1 + a.get(3, 0)

in 연산자

for ... in ...문에서 사용하는 경우를 제외하고, in 연산자는 포함 검사에 사용된다.
(value) + in + (container)를 하면 해당 컨테이너(container)에서 특정 값(value)이 존재하는지에 대한 여부를 판단해서 True 혹은 False로 알려주는 연산자이다.
다음 조건문과 반복문에서 in 연산자가 사용된 예시를 보여주고 있습니다.

조건문에서의 in 연산자

n = [i for i in range(100)]

if 25 in n:
	print("Yes")
else:
	print("No")

s = "I like an apple"
if 'z' in s:
	print("Yes")
else:
	print("No")

반복문에서의 in 연산자

q = [i for i in range(10)]
while 4 in q:
	print("Popped element :", q.pop())

위의 예시처럼 iterable 객체를 대표하는 리스트(list), 문자열, 튜플(tuple)은 전체를 탐색하기 때문에 원소 n개가 있을 때 value를 찾는 데에 $O(n)$ 의 시간복잡도가 발생한다.
하지만 딕셔너리(dictionary)와 집합(set)은 해시 함수를 활용하기 때문에 value의 포함 여부를 판단하는 데에 걸리는 시간복잡도는 $O(1)$ 이 된다.

Dictionary와 in 연산자

dictionary에서 in 연산자는 key가 존재하는지 확인 해준다.
다른 iterable 객체들과 마찬가지로, 만약 key 가 존재하면 True를 반환하고 존재하지 않으면 False를 반환한다.

if 2022390 in student_info:
		print("학생이 존재합니다")
else:
		print("학생이 존재하지 않습니다")

다른 iterable 객체들과 다르게 dictionary 자료형에 in 연산자를 사용하면 $O(1)$ 의 시간복잡도를 가지기 때문에 매우 효율적이다.
이러한 이유로 탐색의 시간복잡도를 감소시키기 위해 dictionary 자료형에 in 연산자를 사용하는 경우가 많다.

li = [6, 9, 1000, 28, 4, 27, 45, 51, 16]
li_d = {i:True for i in li}
# li_d = {6:True, 9:True, 1000:True, 28:True, 4:True, 27:True, 45:True, 51:True, 16:True}

if 4 in li:   # list와 in 연산자의 시간복잡도 : O(n)
if 4 in li_d: # dictionary와 in 연산자의 시간복잡도 : O(1)

Set

Set은 말 그대로 집합을 의미하는 자료구조이다.
순서가 존재하지 않는다는 점에서 dictionary와 동일하지만, 중복되는 데이터를 제거하여, 유일한 데이터만을 담을 수 있도록 설계되었다.
Mutable 객체이므로 데이터 삽입과 제거가 가능하며, 추가로 집합 연산 메서드도 사용할 수 있다.
Python에서는 set과 비슷한 frozenset도 지원한다.

💡 frozenset()

set과 같이 집합을 나타내는 내장 클래스로, 인자로 iterable 객체를 넘기면 set 객체를 반환

하지만, set과 다르게 frozenset은 immutable 하기 때문에, 데이터 삽입 및 삭제 같은 변형이 불가능하다.
items = ["apple", "banana", "orange", "melon"]
fruit_set = frozenset(items)
fruit_set.add("New fruit")
결과
AttributeError: 'frozenset' object has no attribute 'add'
frozenset에는 집합 연산 메서드가 없기 때문에 위와 같이 에러를 발생시킨다.

frozenset을 사용하는 이유는 해시 가능한(hashable) 특성 때문인데, 고유한 값을 가지기 때문에 dictionary에 key로 사용할 수 있다.
snack_set = frozenset(["cookie", "chips", "icecream", "cereal"])
my_bag = {fruit_set:"Buy only these fruits", snack_set:"Snacks for Tom"}
print(my_bag)
# {frozenset({'melon', 'apple', 'orange', 'banana'}): 'Buy only these fruits', frozenset({'chips', 'cereal', 'icecream', 'cookie'}): 'Snacks for Tom'}

Set 사용법

set 선언 및 초기화

# 비어있는 집합 선언
a = set()

a.add(5)  # 데이터 삽입
a.add(2)
a.add(4)
a.add(5)  # 중복 데이터 삽입 시도

print(a)

{5, 2, 4}  # 중복 데이터는 존재x

# set 선언과 동시에 초기화하기
a = {2, 4, 6, 5, 7}
b = {2, 4, 4, 6, 7, 5, 5}
# -> 결과 : a == b

🚧 올바른 set 선언하기

흔히 set이 {}으로 묶이기 때문에 초기화할 때, a = {}처럼 사용하는 경우가 많다.

이것은 공식적으로 비어있는 dictionary 선언에 해당하는 문법이기 때문에, 위의 예시와 같이 set() 을 사용하는 것이 맞다.

하지만 a = {} 형식으로 쓴다고 에러가 나는 것은 아니기 때문에 사용은 가능하다.

분명하게 자료구조에 대한 표현을 해주기 위해 set()을 사용하는 것을 권장

그 외에도 컴프리헨션이 가능하고, iterable 객체를 인자로 받아서 set을 구성할 수도 있다.

# 컴프리헨션
a = {i**2 for i in range(5)}

# iterable 객체 사용
a = set("abadcfesdf")                # 문자열
b = set([1, 7, 5, 3, 2, 2, 8, 1])    # 리스트
c = set((2, 7, 4, 7, 5, 2))          # 튜플

Dictionary 주요 메서드 (집합 연산 포함)

a = set()
b = set()

a.add(4)          # 삽입
a.pop()           # 가장 앞에 배치된 데이터 반환 및 제거
a.remove()        # 원하는 데이터 제거 (없는 데이터 제거 시도할 경우, 에러 발생)
a.discard()       # 원하는 데이터 제거 (없는 데이터 제거 시도해도 에러 발생하지 않음)

# 집합 연산
c = a.intersection(b) == a & b   # a와 b의 교집합
c = a.union(b) == a | b          # a와 b의 합집합
c = a - b                        # a의 b에 대한 차집합
c = a.isdisjoint(b)              # a와 b의 서로소 집합 관계 확인하기

Counter

Counter는 해시 가능한(hashable) 객체의 개수를 세어주는 클래스
인자로 iterable 혹은 매핑(mapping)형 객체를 받는다.
내부적으로, 해시 테이블 구조로 되어있는데, 각 요소와 개수를 key-value 쌍으로 가진다.
Counter를 사용하기 위해서는 collections 패키지로부터 불러와야 한다.

from collections import Counter
# 선언
c = Counter()

# 문자열
c = Counter("abcbdbab")

print(c) # Counter({'b':4, 'a':2, 'c':1, 'd':1})

# 리스트
c = Counter(['banana', 'apple', 'apple', 'kiwi'])

print(c)  # Counter({'apple': 2, 'banana': 1, 'kiwi': 1})

# 딕셔너리
c = Counter({'dogs':4, 'cats':2})

print(c)  # Counter({'dogs':4, 'cats':2})

DefaultDict

DefaultDict는 dict 클래스의 서브 클래스로, 딕셔너리 같은(dictionary-like) 객체를 반환
defaultdict의 가장 큰 특징은 설정되지 않은 key값에 대해 접근을 시도할 때 defaultdict를 선언할 당시 설정한 자료형의 기본값을 반환해 준다는 특징이 있다.

defaultdict 예시 (value 자료형 : list)

from collections import defaultdict

a = defaultdict(list)
# 결과 : a == defaultdict(<class 'list'>, {})

a[1].append(2)        
# 결과 : defaultdict(<class 'list'>, {1:[2]})

a[2].append(3)        
# 결과 : defaultdict(<class 'list'>, {1:[2], 2:[3]})

a['a'].append(4)      
# 결과 : defaultdict(<class 'list'>, {1:[2], 2:[3], 'a':[4]})

a[1].append(5)        
# 결과 : defaultdict(<class 'list'>, {1:[2, 5], 2:[3], 'a':[4]})

defaultdict 예시 (value 자료형 : set)

from collections import defaultdict

i = [('b', 4), ('a', 1), ('b', 4), ('c', 1), ('a', 2), ('a', 1), ('c', 3)]
result = defaultdict(set)
print(result) # defaultdict(<class 'set'>, {})

for name, point in i:
	result[name].add(point)

print(result)  # defaultdict(<class 'set'>, {'b': {4}, 'a': {1, 2}, 'c': {1, 3}})

defaultdict는 데이터 개수를 세려고 할 때, 가장 사용하기 좋다.
- 아래와 같이 무수히 많고, 무질서하게 나열된 데이터들을 정리하고 싶을 때, defaultdict(int)를 활용할 수 있다.

from collections import defaultdict

s = "alkbjlkdnlsknldkmvlksndlk"
d = defaultdict(int)
for i in s:
	d[i] += 1

print(d)  # defaultdict(<class 'int'>, {'a': 1, 'l': 6, 'k': 6, 'b': 1, 'j': 1, 'd': 3, 'n': 3, 's': 2, 'm': 1, 'v': 1})

🚧 주의점 1 : 인자로 아무것도 넘겨주지 않은 상태로 defaultdict 선언하기

defaultdict의 인자는 value의 자료형을 지정한다.
만약 인자 없는 상태로 defaultdict를 선언하면, value에 대한 자료형은 None이 된다.
이 경우, 일반 dictionary와 다를 바 없는 객체가 반환되지만, 오버헤드가 존재하기 때문에, 아무 이유 없이 defaultdict를 사용하는 것은 무의미한 자원 낭비가 될 수 있다.

🚧 주의점 2 : defaultdict의 활용법을 제대로 알고 사용할 것

defaultdict의 강점은 지정된 자료형으로 value를 자동 초기화시켜 key-value 쌍의 형태로 데이터를 편리하게 분류하고 저장하는 것이다.
지정한 value의 자료형을 무시하고 사용한다면, 기존 defaultdict의 본래 목적을 잃어버리게 된다.
아래와 같이 a[0] = "abc"를 실행시키면, 더 이상 list형의 value가 아니기 때문에 append, pop 등의 list의 메서드를 사용할 수 없다.

from collections import defaultdict

a = defaultdict(list)            # value 자료형이 list인 defaultdict 선언

for i in range(5):
	a[i].append(i+1)
# 결과 : defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3], 3: [4], 4: [5]})

a[0] = "abc"
# 결과 : defaultdict(<class 'list'>, {0: 'abc', 1: [2], 2: [3], 3: [4], 4: [5]})

a[0].pop()
# 결과 : AttributeError: 'str' object has no attribute 'pop'

OrderedDict

Python 3.7 버전 이후부터 OrderedDict는 순서 재배치에 특화된 메서드가 있는 dict 클래스의 서브 클래스 인스턴스를 반환한다.
- 본래 OrderedDict의 가장 큰 특징은 삽입 순서를 기억하는 dictionary라는 것이었다.
- 하지만 python 3.7 이후 버전부터는 dictionary도 입력 순서를 기억하는 특징이 부여되면서, OrderedDict의 중요도가 감소하였다.
인자로 iterable 혹은 dictionary형 객체를 받을 수 있는데, 방식이 다르다.

iterable 객체 - fromkeys 메서드

fromkeys 메서드의 인자를 통해서만 iterable 객체를 이용해서 OrderedDict 객체를 얻을 수 있다.
반환 객체는 (데이터, None) 형태의 튜플이 열거된 형태로 저장된다.

from collections import OrderedDict

od1 = OrderedDict.fromkeys("abmdk")
# 결과 : OrderedDict([('a', None), ('b', None), ('m', None), ('d', None), ('k', None)])

od2 = OrderedDict.fromkeys([1, 2, 3, 4, 5])
# 결과 : OrderedDict([(1, None), (2, None), (3, None), (4, None), (5, None)])

dictionary 객체

iterable 객체와 다르게 dictionary 객체는 OrderedDict의 인자로 바로 받을 수 있다.
이때, (key, value) 형태의 튜플로 반환 객체가 구성된다.

from collections import OrderedDict

od = OrderedDict({2:4, 4:5})
# 결과 : OrderedDict([(2, 4), (4, 5)])

주요 OrderedDict 메서드

다음 예시를 통해, 주요 메서드 사용 방법을 알아보자.

from collections import OrderedDict

od = OrderedDict.fromkeys([1, 2, 3, 4, 5])
# 결과 : OrderedDict([(1, None), (2, None), (3, None), (4, None), (5, None)])

popitem()

list의 pop() 메서드와 동일한 기능을 한다.
마지막 위치에 있는 튜플을 반환하고, OrderedDict에서 제거한다.
기본적으로, last=True로 지정되어 있어, LIFO 형태로 마지막 요소가 반환 및 제거가 이루어지지만, last=False로 지정하면, FIFO 방식으로 첫번째 요소를 반환 또는 제거한다.

od.popitem()  # last=True -> (5, None)
print(od)  # OrderedDict([(1, None), (2, None), (3, None), (4, None)])

od.popitem(last=False)  # -> (1, None)
print(od)  # OrderedDict([(2, None), (3, None), (4, None), (5, None)])

move_to_end()

특징 key값에 해당하는 튜플을 last=True 로 지정해서 마지막 요소로 옮기거나, last=False로 명시해서 첫 번째 요소로 옮길 수 있다.
popitem() 메서드와 동일하게 기본적으로 last=True

od.move_to_end(3)
print(od)  # OrderedDict([(1, None), (2, None), (4, None), (5, None), (3, None)])

od.move_to_end(3, last=False)
print(od)  # OrderedDict([(3, None), (1, None), (2, None), (4, None), (5, None)])

move_to_end() 메서드는 마지막 위치에 있는 튜플과 swap하는 것이 아니다.
지정 튜플을 제외한 모든 데이터의 순서를 유지한 상태로 key로 지정한 튜플만 마지막 위치로 옮겨주는 것임을 알아야 한다.

Python의 Hash Table 사용 시 주의사항

그럼 Dictionary가 만능일까?

dictionary가 list의 완벽한 상위호환 같지만, list만의 장점이 있다.
- 순서가 있다는 것!
dictionary의 큰 특징 중 하나는 삽입 순서대로 저장해둔다는 것이다.
하지만 실제 key 간의 순서가 정해진 것은 없기 때문에, 정렬할 수는 없지만, list는 정렬할 수 있다.

li = [4, 5, 2, 3, 1]
li.sort()             # li = [1, 2, 3, 4, 5]

d = {1:2, 5:3, 2:4, 4:9}
d.sort()              # dictionary 자체로는 sort 불가

Dictionary 자체에 대한 정렬은 불가능하지만, dictionary 뷰 객체에 대해서는 정렬을 수행할 수 있다.

💡 dictionary.items(), dictionary.keys(), dictionary.values() : 딕셔너리 뷰 객체 → 집합(set)형의 연산을 그대로 수행할 수 있다. 예시) 반복, 합집합/교집합 연산, 데이터 제거, …

d = {1:2, 5:3, 2:4, 4:9}

d.items()          # dict_items([(1, 2), (5, 3), (2, 4), (4, 9)])
d.keys()           # dict_keys([1, 5, 2, 4])
d.values()         # dict_values([2, 3, 4, 9])

sorted(d.items())  # [(1, 2), (2, 4), (4, 9), (5, 3)]
sorted(d.keys())   # [1, 2, 4, 5]
sorted(d.values()) # [2, 3, 4, 9]

다음과 같이 정렬한다 하더라도, 결국에는 sorted()에 의해 list로 반환된다.
- 따라서 데이터의 순서가 중요할 때는 list를 사용하는 것이 바람직하다.

Key의 조건 - Hashable

위에서도 언급했듯이, key 값은 해시 가능(hashable) 해야 한다.
해시 가능하다는 것은 불변성, 즉 생성된 이후 삭제되기 전까지 절대 변하지 않는 특성을 지니고 있는 것을 의미한다.
- 예를 들어, int(정수형), float(부동소수점), tuple(튜플) 등이 있다.
반대로 해시가능하지 않은 객체는 수정할 수 있는 형태를 가진 객체들이다.
- 대표적으로 list(리스트), dictionary(딕셔너리) 등이 있다.

# Hashable
hashtable = {1:[value], 'a':[value], (1, 2):[value]}   # 올바른 사용

# Unhashable
hashtable = {[1, 2]:[value], {1:2, 3:4}:3}             # 올바르지 못한 사용

코딩 테스트에 활용하기

key-value 쌍의 의미가 강한 경우

파이썬의 딕셔너리는 해시 가능한(hashable) 자료형과 데이터의 순서쌍이 담긴 자료구조이다.
만약 데이터 간의 관계성을 갖게 되는 문제 상황을 맞닥뜨린다면, 딕셔너리를 통해 표현할 수 있다.
가령, (이름, 나이)와 같이 두 가지 이상의 정보를 한꺼번에 저장해야 한다면, 각 데이터에 대한 리스트를 사용하는 것보다 딕셔너리로 한 번에 데이터를 묶어서 다룰 수 있게 된다.

get & set 시간복잡도 줄이기

get은 데이터를 가져오는 것, 그리고 set은 데이터를 저장하는 것을 의미한다.
리스트는 특정 위치에 있는 데이터를 찾기 위해서 기본적으로 $O(n)$ 의 시간복잡도가 발생하지만, 딕셔너리와 in 연산자를 사용하면, $O(1)$ 로 줄일 수 있다.
따라서 많은 개수의 데이터를 담은 자료형에서 반복문을 통해 원하는 데이터를 찾아야 한다면, 딕셔너리와 in 연산자를 사용하는 것이 매우 좋다.

# 상황 : 리스트 a와 딕셔너리 b에서 n 찾기
# 리스트 시간복잡도 : O(n)
for i in a:
		if i == n:
				return 1

# 딕셔너리 시간복잡도 : O(1)
if n in b:
		return 1

메모리 제한에 걸리지 않는 경우

딕셔너리는 시간복잡도를 줄이기에 용이하지만, 그만큼 메모리 사용량이 증가한다.
딕셔너리도 해시테이블이기 때문에 데이터를 저장할 때, 충돌(collision)이 발생할 수 있다.
- 이를 방지하기 위해 일정 비율로 여유 공간을 항상 남겨둔다.
- 혹은 내부 구현에 따라 다르지만, 역해시가 불가능한 경우, 해시와 데이터를 같이 저장하게 되어 더 많은 메모리 공간이 필요할 수도 있다.

💡 역해시란?

해시테이블에서 키값을 해시함수에 넣어서 인덱스를 얻게 되고, 이것이 데이터를 저장하는 공간의 주소

역해시가 가능하다는 것은 인덱스에서 역방향으로 키값을 계산하는 것으로, 해시 함수에 따라 가능 여부가 달라진다.

따라서 데이터뿐만 아니라 키값도 같이 저장하기도 한다.

그렇게 되면, 저장 공간을 늘릴 수밖에 없기 때문에 메모리 사용량이 증가하게 된다.

References

코딩테스트 ALL IN ONE

문지은

코드로 꿈을 펼치는 개발자의 이야기, 노력과 열정이 가득한 곳 🌈

이전 포스트

[Python] 2차원 배열 회전 알고리즘 ( 프로그래머스 : 자물쇠와 열쇠 )

다음 포스트