해시 테이블

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

정의

  • 항목 모음 저장

  • 키-값 쌍

      lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

  • 대부분의 언어에 내장 해시 테이블 있음:

    • hashes, hash maps, dictionaries, associative arrays
    • Python: 딕셔너리
Python으로 배우는 자료구조와 알고리즘

구조

  • 각 위치: 슬롯/버킷

빈 해시 테이블의 개략도.

Python으로 배우는 자료구조와 알고리즘

해시 함수

빈 해시 테이블의 개략도. 다섯 번째 위치에 lasagna의 가격이 삽입되었습니다.

Python으로 배우는 자료구조와 알고리즘

해시 함수

해시 테이블 개략도. 화살표 중앙에 "Hash function"이 있고 "Lasagna"를 다섯 번째 위치의 값에 매핑합니다.

  • 해시 함수를 적용할 때마다
    • 같은 입력에 같은 값을 반환해야 함
Python으로 배우는 자료구조와 알고리즘

탐색(lookup)

값이 일부 채워진 해시 테이블의 개략도.

  • "lasagna" 찾기
    • hash("lasagna") -> 5
Python으로 배우는 자료구조와 알고리즘

탐색(lookup)

값이 일부 채워진 해시 테이블의 개략도. 다섯 번째 위치의 값이 초록색입니다.

  • "lasagna" 찾기
    • hash("lasagna") -> 5
    • 14.75 반환
  • $O(1)$
Python으로 배우는 자료구조와 알고리즘

충돌

  • 서로 다른 입력이 같은 출력을 낼 수 있음
  • hash("moussaka") -> 1

값이 일부 채워진 해시 테이블의 개략도. 첫 번째 위치의 값이 노란색입니다.

  • 삽입: moussaka -> 21.15
  • 충돌(Collision)!
    • 해결 필요
    • 여러 기법 존재
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리

  • 빈 딕셔너리
my_empty_dictionary = {}
  • 항목이 있는 딕셔너리
my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리 - get

print(my_menu['sushi'])

16.05

print(my_menu['paella'])

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'paella'

print(my_menu.get('paella'))

None
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리 - items, keys, values

  • 항목 가져오기
print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])
  • 키 가져오기
print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])
  • 값 가져오기
print(my_menu.values())

dict_values([14.75, 21.15, 16.05])
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리 - 삽입

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리 - 수정

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리 - 삭제

  • 딕셔너리 전체 삭제
del my_menu
  • 키-값 쌍 삭제
del my_menu["sushi"]
  • 딕셔너리 비우기
my_menu.clear()
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리 - 반복

for key, value in my_menu.items():
  print(f"\nkey: {key}")
  print(f"value: {value}")

key: lasagna
value: 14.75

key: moussaka
value: 21.15

key: sushi
value: 16.05
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리 - 반복

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

for prices in my_menu.values():
  print(prices)

14.75
21.15
16.05
Python으로 배우는 자료구조와 알고리즘

Python 딕셔너리 - 중첩 딕셔너리

  • 중첩 딕셔너리
my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}
Python으로 배우는 자료구조와 알고리즘

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘

Preparing Video For Download...