해시 테이블
해시 테이블 = 사람의 뇌
하나하나 확인해서 찾지 않고 O(1)로 찾을 수 있다는 점에서 사람의 뇌라고 생각하면 편하다!
시간 복잡도
저장, 삭제, 검색의 시간 복잡도가 모두 O(1)
- 리스트와 달리 in 연산자 사용하여 존재 여부를 확인할 때도 O(1)이다.
- 충돌로 인한 최악의 경우 O(n)의 시간복잡도를 가진다.
- 저장공간을 확보해야 하기 때문에 공간의 효율성은 떨어질 수 있지만 메모리를 사용해서 시간 복잡도를 줄일 수 있다.
set도 in 연산자를 사용하면 O(1)로 존재 여부를 확인할 수 있다
dictionary의 key 값을 set에 넣어서 사용한다고 생각하면 편하다!
key-value 데이터
- key-value 쌍으로 데이터를 저장한다
- 중복된 값을 key로 사용할 수 없다!
- 중복된 key 값을 사용하면 기존 value가 덮어씌여진다.
- value는 중복된 값이 들어갈 수 있다.
사용방법
dictionary에 값 저장
dict = {}
dict['python'] = 1
dict['java'] = 2
print(dict){'python': 1, 'java': 2}
key 를 사용해서 value 에 접근
print(dict['python'])print(dict.get('python'))1
key 값 중에 'python' 존재 여부 확인
if 'python' in dict :
print(True)if 'python' in dict.keys() :
print(True)True
value 값 중에 1 존재 여부 확인
if 1 in dict.values() :
print(True)True
정리
- 파이썬에서는 dictionary로 해시 테이블 사용
- key를 배열의 index처럼 생각하기
- O(1)의 시간복잡도로 검색하고 싶을 때는 dictionary나 set을 사용!
- 순서가 중요한 경우는 리스트를 사용하는 것이 better
- dictionary나 set을 사람의 뇌로 생각하고 기억하고 싶은 것이 있으면 key 값에 지정하여 dictionary에 저장하거나 set에 저장한 후in 을 사용해서 빠르게 확인하기
