2.3 해시테이블 (Hash Table)

DTA(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: 이름

(nossi8128, 노정호)
(js9876, 배준석)
(zebra001, 정재헌)
(nam1234, 남영욱)

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 방식을 채택하고 있습니다.

시간 복잡도와 공간 효율성

시간 복잡도는 저장, 삭제, 검색 모두 기본적으로 $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 사용법

hash table은 앞서 key-value의 쌍으로 이루어졌다고 했습니다. 파이썬에서 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)}

• 결과
• 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}

• 결과
• result_dict == {'maria': 80, 'david': 92, 'nancy': 83}

Dictionary 주요 메서드

위에 만들었던 예시를 이용해서 주요 메서드의 사용 예시를 보겠습니다.

student_info = {}
student_info[2022390] = "노정호"
student_info[2022392] = "배준석"
student_info[2022393] = "정재헌"
student_info[2022401] = "남영욱"

# 결과
# {2022390: '노정호', 2022392: '배준석', 2022393: '정재헌', 2022401: '남영욱'}

1. 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 남영욱

2. 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

3. dictionary.values()

dictionary의 value들을 접근할 때 사용합니다.

print(student_info.values())

• 결과
• dict_values(['노정호', '배준석', '정재헌', '남영욱'])

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

• 결과
• 노정호 배준석 정재헌 남영욱

4. dictionary.get()

key에 해당하는 value을 가져올 때 사용됩니다.

print(student_info.get(2022390))

• 결과
• 노정호

만약 다음처럼 존재하지 않는 값을 가져오면 어떻게 될까요?

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

• 결과
• Yes No

반복문에서의 in 연산자

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

• 결과
• Popped element : 9 Popped element : 8 Popped element : 7 Popped element : 6 Popped element : 5 Popped element : 4 # q == [0, 1, 2, 3]

위의 예시처럼 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⁽²⁾도 지원합니다.

Set 사용법

set 선언 및 초기화

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

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

print(a)

• 결과
• a == {5, 2, 4} # 중복 데이터는 존재하지 않습니다

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

<aside> 🚧 올바른 set 선언하기

흔히 set이 {}으로 묶이기 때문에 초기화할 때, a = {}처럼 사용하는 경우가 많습니다. 하지만 이것은 공식적으로 비어있는 dictionary 선언에 해당하는 문법이기 때문에, 위의 예시와 같이 set() 을 사용하는 것이 맞습니다. 하지만 그렇다고 a = {} 형식으로 쓴다고 에러가 나는 것은 아니기 때문에 사용 가능합니다. 분명하게 자료구조에 대한 표현을 해주기 위해 set()을 사용하는 것을 권장합니다.

</aside>

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

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

• 결과
• a == {0, 1, 4, 9, 16}

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

• 결과
• a == {'s', 'b', 'e', 'd', 'c', 'a', 'f'} b == {1, 2, 3, 5, 7, 8} c == {2, 4, 5, 7}

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

• 결과
• Counter({'b':4, 'a':2, 'c':1, 'd':1})

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

• 결과
• Counter({'apple': 2, 'banana': 1, 'kiwi': 1})

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

• 결과
• 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의 반환되는 객체는 위의 예시와 같습니다. 앞서 설명했듯이 defaultdict는 선언할 당시 value의 자료형을 설정합니다. (위 예시에서는 list로 설정되어 있습니다) 또한 a라는 defaultdict는 1이라는 key값이 설정되어 있지 않은 상태입니다. 만약 일반 dictionary는 a[1] 에 접근할 때 key error를 발생시키지만, defaultdict는 value의 자료형(list)의 기본값인 빈 배열을 반환해 주어 append 연산이 수행 가능합니다. 즉, 기본적으로 일반 dictionary와 동일하게 사용 가능하지만, 새로운 key-value 쌍이 입력될 때, 지정된 value의 자료형에 대한 초기화를 해주고, 자료형에 맞는 연산을 할 수 있게 해줍니다. 다음은 set을 이용한 예시입니다.

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)
# 결과 : a == defaultdict(<class 'set'>, {})

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

• 결과
• defaultdict(<class 'set'>, {'b': {4}, 'a': {1, 2}, 'c': {1, 3}})

defaultdict는 데이터 개수를 세려고 할 때, 가장 사용하기 좋습니다. 다음 코드로 활용 예시를 보여드리겠습니다.

from collections import defaultdict

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

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

만약 위와 같이 무수히 많고, 무질서하게 나열된 데이터들을 정리하고 싶을 때, defaultdict(int)를 활용하면 매우 좋습니다.

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

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

</aside>

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

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

</aside>

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 클래스의 서브 클래스 인스턴스를 반환합니다. 인자로 iterable 혹은 dictionary형 객체를 받을 수 있는데, 방식이 다릅니다.

iterable 객체 - fromkeys 메서드

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

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

dictionary 객체

from collections import OrderedDict

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

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

주요 OrderedDict 메서드

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

from collections import OrderedDict

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

1. popitem()

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

od.popitem()  # last=True
print(od)

• 결과
• (5, None) OrderedDict([(1, None), (2, None), (3, None), (4, None)])

od.popitem(last=False)
print(od)

• 결과
• (1, None) OrderedDict([(2, None), (3, None), (4, None), (5, None)])

1. 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 뷰 객체에 대해서는 정렬을 수행할 수 있습니다.

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

</aside>

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)이 발생할 수 있습니다. 이를 방지하기 위해 일정 비율로 여유 공간을 항상 남겨둡니다. 혹은 내부 구현에 따라 다르지만, 역해시⁽⁴⁾가 불가능한 경우, 해시와 데이터를 같이 저장하게 되어 더 많은 메모리 공간이 필요할 수도 있습니다.

---

1. Separate Chaining vs Open Addressing

• Separate Chaining
  • 데이터 삽입 시, 버킷 혹은 슬롯에 연결리스트를 할당합니다. 만약 같은 해시값에 의해 해시 충돌이 발생하면, 연결리스트를 이어서 해시 충돌을 방지하고자 하는 방식입니다.
  • 버킷이 모두 채워진 상태여도, 연결리스트로 데이터를 연결 짓기 때문에 한 번 정해진 데이터의 주솟값은 영구적으로 유지됩니다. 이를 Closed Addressing이라고도 부릅니다.
  • 장점
    • 단순한 연결리스트만을 활용했습니다.
    • 해시테이블이 채워지면서, 탐색에 대한 성능 저하가 선형적으로 발생합니다.
• Open Addressing
  • 데이터를 삽입할 때, 버킷 혹은 슬롯에 연결리스트를 만들지 않습니다. 다만, 해시 충돌이 발생한다면, 다른 비어있는 버킷에 데이터를 저장합니다.
  • 선형 탐색, 제곱 탐색, 이중 해시 등 비어있는 버킷 탐색 방식에 따라 내부 알고리즘이 다를 수 있습니다.
  • 장점
    • 해시테이블 자체만을 저장공간으로 활용하기 때문에, 추가적인 저장공간이 필요하지 않습니다.
    • 삽입, 삭제 시, 발생하는 오버헤드가 적습니다.
    • 상대적으로 데이터가 적을 때, 체이닝 방식보다 유리합니다.

2. frozenset()

frozenset도 set과 같이 집합을 나타내는 내장 클래스입니다. 인자로 iterable 객체를 넘기면 set 객체를 반환합니다. 하지만, set과 다르게 frozenset은 immutable 하기 때문에, 데이터 삽입 및 삭제 같은 변형이 불가능합니다. 다음 frozenset에 대한 예제 코드입니다.

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({'orange', 'melon', 'apple', 'banana'}): 'Buy only these fruits', frozenset({'chips', 'cereal', 'cookie', 'icecream'}): 'Snacks for Tom'}

3. Python 3.7 이전 버전의 OrderedDict

본래 OrderedDict의 가장 큰 특징은 삽입 순서를 기억하는 dictionary라는 것이었습니다. 하지만 python 3.7 이후 버전부터는 dictionary도 입력 순서를 기억하는 특징이 부여되면서, OrderedDict의 중요도가 감소하였습니다.

4. 역해시

해시테이블에서 키값을 해시함수에 넣어서 인덱스를 얻게 되고, 이것이 데이터를 저장하는 공간의 주소입니다. 역해시가 가능하다는 것은 인덱스에서 역방향으로 키값을 계산하는 것으로, 해시 함수에 따라 가능 여부가 달라집니다. 따라서 데이터뿐만 아니라 키값도 같이 저장하기도 합니다. 그렇게 되면, 저장 공간을 늘릴 수밖에 없기 때문에 메모리 사용량이 증가하게 됩니다.