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