1️⃣ 이론
해시 자료구조에서는 insert, erase, find, update 등 모든 연산이 전부 O(1)이다
해시 함수란, 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수로
예를 들면 카드 번호의 경우 뒷 4자리만 인덱스로 사용하는 것이 효율적이다
충돌
서로 다른 키가, 같은 해시 값을 가지게 될 경우
ex) 카드 번호 뒷 4자리는 같지만, 나머지 자리가 다른 카드들
충돌 회피 방법 Chaining
각 인덱스마다 연결 리스트를 하나씩 두고, 삽입이 발생하면 해당하는 인덱스의 연결 리스트에 값을 추가함
- 만약 운이 안좋아서 해시 값이 다 같았을 경우, 연결 리스트 1개에서 insert, erase, find, update를 다 하는 상황이 됨 -> O(N)
- 해시 자료구조는 이상적인 상황에서는 O(1)이지만, 충돌이 빈번할수록 성능이 저하되고, 모든 키의 해시값이 같은 최악의 상황에서는 O(N)이 됨
- 때문에 해시에서는 각 키의 해시값이 최대한 균등하게 퍼져야 성능이 좋아지고, 그러기 위해서는 주어진 데이터에 대한 좋은 해시 함수를 정해야 함
충돌 회피 방법 Open Addressing
각 인덱스에 바로 (키, 값) 쌍을 씀
- 3333이 비어있지 않으므로 그 다음 칸에 내용을 삽입함
- find를 할 땐 오른쪽으로 이동하며 해당 값을 찾음 -> 비어있는 칸에 도달하면 찾고 싶은 값이 저장이 안되어 있다는 것을 확인할 수 있음
- 대신 erase를 할 때 그냥 값을 날려서 빈 칸을 만드는 게 아니라, 해당 칸에 쓰레기 값을 두든지 해서 해당 칸이 빈 칸이 아니라 원래 값이 있었지만 제거된 상태임을 명시해 줄 필요가 있음
1. Linear Probing
Cluster가 커지면 커질수록 인덱스가 이 군집에 걸렸을 때 빈 칸을 찾을 때까지 이동해야 하는 횟수가 늘어나서 성능을 저하시키게 됨
2. Quadratic Probing
- 현 위치 기준으로는 1,3,5,... 칸 이동하지만, 처음 위치 기준으로는 1,4,9,...칸 이동하는 것(1의 제곱, 2의 제곱, 3의 제곱)
- Linear Probing에 비해서는 개선이 됐지만, 해시값이 동일하다면 계속 똑같은 경로를 따라가기 때문에 여전히 Clustering이 발생함
3. Double Hashing
- 해시 함수를 하나 더 둬서 충돌이 발생했을 때, 몇 칸 점프할지를 이 새로운 해시 함수의 값으로 계산하는 방식
-> 점프할 칸의 수는 앞 4자리로 정함(1234 2222 5555는 1234칸 씩 뜀)
2️⃣ 코드
삭제
dic = {'김정빈': 75, '박한지': 56, '임호정': 23}
del dic['박한지']
출력
a = {'banana': 1500, 'watermelon': 9000}
a.get('banana') -> 1500
a.get('strawberry', 0) -> 0
print(list(a.values())) # 딕셔너리의 값만 모아 리스트로 출력
# 반복문으로 키-값 쌍 모두 출력하기
for key, value in x.items():
print(key, value)
정렬
- 키 기준으로 정렬하기 -> dic = sorted(dic.items())
- 값 기준으로 정렬하기 -> dic = sorted(dic.items(), key=lambda x:x[1])
비교
최댓값/최솟값 찾기
# key들 중에 최대/최소 값을 찾아서 리턴
max(dict.keys())
# value들 중에 최대/최소 값을 찾아서 리턴
max(dict.values())- dic1 == dic2 -> 키의 순서가 달라도 상관없음
딕셔너리 ↔️ 리스트
arr = list(zip(dic.keys(), dic.values())) # [(1, 2), (3, 4)] 형태
arr = list(sum(arr, ()) # [1, 2, 3, 4] 형태 -> 완성!defaultdict
키가 존재하지 않으면, 해당 키를 만들고 값을 디폴트값으로 넣음
from collections import defaultdict
dic = defaultdict(int) # 디폴트값이 int(0)인 딕셔너리
dic = defaultdict(list) # 디폴트값이 리스트([])인 딕셔너리
🐥👩💻💰