해시 테이블

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

Miriam Antona

Software engineer

정의

  • 항목의 컬렉션 저장

  • 키-값 쌍

      lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

  • 거의 모든 프로그래밍 언어에 해시 테이블이 내장됨:

    • 해시, 해시 맵, 딕셔너리, 연관 배열
    • Python: 딕셔너리
Python으로 배우는 자료구조와 알고리즘

구조

  • 각 위치: 슬롯/버킷

빈 해시 테이블의 개략적 표현.

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

해시 함수

빈 해시 테이블의 개략적 표현. 라자냐 가격이 다섯 번째 위치에 삽입됨.

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

해시 함수

"해시 함수"라는 글자가 "Lasagna"를 다섯 번째 위치의 값으로 매핑하는 화살표 중간에 표시된 해시 테이블의 개략적 표현.

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

조회

일부 값이 있는 해시 테이블의 개략적 표현.

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

조회

일부 값이 있는 해시 테이블의 개략적 표현. 다섯 번째 위치의 값이 초록색으로 표시됨.

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

충돌

  • 해시 함수는 서로 다른 입력에 동일한 출력을 반환할 수 있음
  • hash("moussaka") -> 1

일부 값이 있는 해시 테이블의 개략적 표현. 첫 번째 위치의 값이 노란색으로 표시됨.

  • 삽입: moussaka -> 21,15
  • 충돌!
    • 해결 필요
    • 다양한 기법 존재
Python으로 배우는 자료구조와 알고리즘

파이썬 딕셔너리

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

파이썬 딕셔너리 - 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으로 배우는 자료구조와 알고리즘

파이썬 딕셔너리 - 삽입

my_menu['samosas'] = 13

print(my_menu.items())

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

파이썬 딕셔너리 - 수정

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

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

파이썬 딕셔너리 - 삭제

  • 딕셔너리 완전 삭제
del my_menu
  • 키-값 쌍 제거
del my_menu["sushi"]
  • 딕셔너리 비우기
my_menu.clear()
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으로 배우는 자료구조와 알고리즘

파이썬 딕셔너리 - 반복

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으로 배우는 자료구조와 알고리즘

파이썬 딕셔너리 - 중첩 딕셔너리

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

연습해 봅시다!

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

Preparing Video For Download...