[알고리즘, 자료구조] Hash Table (해쉬 테이블) - dictionary

1. Hash Table

- 효율적인 탐색을 위한 알고리즘

• key - value
• 저장, 삭제, 검색의 시간 복잡도 O(1)
• Hash Table -> hash function h를 활용 (key, value)
• "h(k)는 키 k의 해시값이다"
• key는 무조건 존재, 중복되는 key값이 있어서는 안됨

	Hash Table
access	O(1)
insert	O(1)
append
delete	O(1)

 

- 파이썬 dictionary = Hash Table

• 파이썬에서는 key를 리스트의 index로 생각하자!

# dictionary -> 해쉬테이블

ST_Info = {}
ST_Info[1] = "가"
ST_Info[2] = "나"
ST_Info[3] = "다"
ST_Info[4] = "라"

# in 연산자
if 2 in ST_Info:
    print("학생 존재")
else:
    print("학생 존재하지 않음")

# dictionary.items() -> key와 value 접근
for student_id, name in ST_Info.items():
    print(student_id, name)

# dictionary.keys() -> key에 접근
for student_id in ST_Info.keys():
    print(student_id)

# dictionary.values() -> value에 접근
for name in ST_Info.values():
    print(name)

# dictionary.get() -> key에 해당하는 value를 가져옴
print(ST_Info.get(1)) # 해당하는 값이 있을 경우

print(ST_Info.get(13, "사")) # 해당하는 값이 없을 경우