해시 테이블

파이썬에서는 해시테이블이 딕셔너리라는 자료구조로 구현되어 있다.

구현 방법

• Array List (파이썬에서는 Array List로 구현되어 있다.)
• Array List + Linked List

해시 테이블의 시간 복잡도

Hash Talbe은 효율적인 탐색을 위한 자료구조로써 key-Value쌍의 데이터를 입력받는다. hash function h에 key값을 입력으로 넣어 얻은 해시값을 위치로 지정하여 key - value 데이터 쌍을 저장한다. 저장, 삭제, 검색의 시간복잡도는 모두 Big O (1)을 가진다.

Direct-address Table

• 크기가 U인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식

• 중복되는 key는 없다고 가정

• 시간복잡도가 굉장히 빠름

• 검색, 삽입, 삭제가 빠르지만 실제 사용하는 공간이 낭비되는 단점

딕셔너리 (Dictionary)

• 딕셔너리 쓰는 법

score = {
  'math':97,
  'eng':49,
  'ko':89,
}
 
print(score["eng"])
score["music"]= 100
print(score)
 
print("science" in score)
 
if "music" in score:
  print("뮤직있어요")
else:
  print("뮤직 없어")