❗️ 계속해서 업데이트 될 예정...
잘못된 부분이 있다면 알려주세요 🙏
해시 테이블
해시 테이블이란
대부분의 연산이 시간 복잡도가 O(1)이다.
해시 함수
임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용하는 함수.
좋은 해시 함수의 특징
- 해시 함수 값 충돌 최소화
- 쉽고 빠른 연산
- 해시 테이블에 해시 값이 균일하게 분포
생일 문제
해시 함수의 충돌에 대한 대표적인 예. 여러 사람이 모였을 때 생일이 같은 사람이 2명 존재할 확률은 얼핏 봤을 때 366명이 모여야 가능할 거 같지만 23명만 모여도 50%가 넘고 57명이 넘으면 그때부터 99%를 넘어선다.
이렇듯 일반적인 상식과는 달리 충돌은 쉽게 일어나, 이를 최소화하는 것이 중요하다.
로드 팩터
해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것. 즉, 로드 팩터가 커질 수록 해시 테이블의 성능이 감소하게 되며, 자바의 경우 0.75가 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당한다. 파이썬의 경우 로드 팩터는 0.66이다.
해싱
해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것. 여러가지 해싱 알고리즘이 존재.
- md5
- SHA 시리즈
- Tiger
- CRC
충돌 해결 방법
-
개별 체이닝
충돌이 일어난 데이터를 연결 리스트로 연결하는 방식. 흔히 해시 테이블이라고 하면 이 방식을 사용. 잘 구현한 경우 탐색은O(1), 최악의 경우 모두 충돌이 일어났을 때 연결 리스트가 하나의 큰 배열이 되므로O(n)이다. -
오픈 어드레싱
충돌이 일어났을 때 빈 공간을 찾는(선형 탐사) 방식. 무한정 저장할 수 있는 개별 체이닝 방식과 달리, 전체 슬롯의 개수 이상은 저장을 못함. 그래서 반드시 자신의 해시값과 일치하는 주소에 저장된다는 것을 보장 못함. 위 사진에서 보면윤아와서현이 충돌되어서현은 자신의 해시가2이지만3에 저장됨.선형 탐사
충돌이 일어난 위치부터 순차적으로 탐사를 하나씩 진행한다. 충돌이 일어난 위치에서 바로 다음 위치를 확인하는 식.
파이썬에서의 해시 테이블
파이썬에서 해시 테이블은 딕셔너리 자료형으로 구현된다. 또한 파이썬에서 충돌이 일어났을 경우 오픈 어드레싱 방식으로 해결한다. 개별 체이닝 방식을 사용하지 않는 이유는 연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요하고 이 경우 속도가 느려지기 때문에 채택하지 않았다.
해시 구현
def search(X):
if X >= 0:
return has[X][0] == 1
X = abs(X)
return has[X][1] == 1
def insert(a, n):
for i in range(0, n):
if a[i] >= 0:
has[a[i]][0] = 1
else:
has[abs(a[i])][1] = 1슬라이딩 윈도우
해시 테이블 문제 풀이
문제 10816
✏️ 내가 작성한 코드
hash = {}
N = int(input())
s:list = list(map(int, input().split()))
M = int(input())
j:list = list(map(int, input().split()))
for char in s:
if char in hash:
hash[char] += 1
else:
hash[char] = 1
for char in j:
if char in hash:
print(hash[char], end=' ')
else:
print(0, end=' ')전형적인 해시 테이블을 이용한 풀이.
import collections
hash = collections.defaultdict(int)
N = int(input())
s:list = list(map(int, input().split()))
M = int(input())
j:list = list(map(int, input().split()))
for char in s:
hash[char] += 1
for char in j:
print(hash[char], end=' ')
defaultdict을 사용하면if문으로 값이 존재 여부를 확인하지 않아도 되기때문에 코드가 줄어든다.defaultdict는 딕셔너리 안에 존재 하지 않은 키에 대해 값을0으로 해서 리턴해주기 때문이다.
import collections
N = int(input())
hash = collections.Counter(list(map(int, input().split())))
M = int(input())
j:list = list(map(int, input().split()))
for char in j:
print(hash[char], end=' ')
Counter를 사용하면 키의 종류별 개수를 자동으로 구해주기 때문에 코드가 더 간결해진다. 또한 존재하지 않는 키의 경우KeyError를 발생하지 않고 자동으로0을 반환한다.
문제 1620
✏️ 내가 작성한 코드
import sys
import collections
N, M = map(int, sys.stdin.readline().split())
d_1 = collections.defaultdict(str)
d_2 = collections.defaultdict(str)
for i in range(1, N+1):
x = sys.stdin.readline().strip()
d_1[x] = i
d_2[i] = x
for _ in range(M):
x = sys.stdin.readline().strip()
if x.isdecimal():
print(d_2[int(x)])
else:
print(d_1[x])좀 더 간결한 코드로 풀고 싶었으나 딕셔너리를 2개 사용하지 않으면 시간초과가 뜬다.
