해시 테이블이란 키를 해시 함수를 이용해 연산함으로써 고정된 길이의 결과값을 얻을 수 있고 이 결과값을 이용하여 키와 값을 매핑할 수 있는 형태의 자료구조이다.
이처럼 해시 함수를 이용해 키와 값을 매핑하는 것을 해싱이라 하며 해싱은 정보를 빠르게 저장하고 검색하기 위해 사용되는 중요한 기법이다.
충돌
서로 다른 값의 키를 계산했을 때 같은 결과의 해시값이 나오는 경우를 충돌했다고 표현한다.
그렇다면 충돌이 발생할 확률은 얼마나될까?
충돌에 대해 설명할 때 자주 사용하는 예로 생일 문제를 들 수 있다.
생일 문제
1년은 365일로 사람이 가질 수 있는 생일은 365가지나 된다.
그렇다면 같은 생일을 가진 사람이 존재하려면 몇 명의 사람이 필요할까? 100명? 200명?
보통 못해도 100명 이상은 되어야 같은 생일을 가진 사람이 존재할 것이라고 생각한다.
하지만 23명만 모이더라도 같은 생일을 가진 사람이 존재할 확률이 50%를 넘는다고 한다.
또한, 57명이 넘는 경우 99%를 넘어선다.
이것을 해시에 대입해보면 해시를 통해 나올 수 있는 결과값이 365개가 존재한다면 23개의 데이터를 넣었을 경우 충돌이 발생할 확률이 50%이상이고 57개의 데이터를 입력한다면 거의 100%의 확률로 충돌이 발생한다고 볼 수 있다.
충돌이 날 경우
그렇다면 충돌이 발생할 경우 어떻게 어떻게 대처할 것인가?
해시 테이블에서 충돌의 해결법은 크게 2가지로 볼 수 있다.
chaining과 open addressing 방식이다.
백준 1920번 수찾기 문제를 통해 해시 테이블이란 무엇인지 알아보자
1920번 문제는 4번째 줄에 입력으로 들어오는 값들이 2번째 줄에 입력으로 받은 값들 사이에 포함되어 있는지 확인하고 포함되어 있다면 1을 없다면 0을 출력하는 프로그램이다.
초기 제출코드
다음 코드를 백준에 제출하면 문제없이 동작한다.
하지만 걸린 시간이 4000ms를 넘어갈 정도로 오래 걸리는 것을 확인할 수 있다.
# 정수 A의 개수 n 입력
n = int(input())
# 정수 A 입력
a = list(map(int,input().split(" ")))
# A안에 존재하는지 확인할 정수의 개수
m = int(input())
# 확인할 정수 입력
values = list(map(int, input().split(" ")))
# list의 정수를 하나씩 a에 존재하는지 확인
# 존재한다면 1 존재하지 않는다면 0을 출력
for v in values:
if v in a:
print('1')
else:
print('0')
# 정수 A의 개수 n 입력
n = int(input())
# 정수 A 입력
a = set(map(int,input().split(" ")))
# A안에 존재하는지 확인할 정수의 개수
m = int(input())
# 확인할 정수 입력
values = list(map(int, input().split(" ")))
# list의 정수를 하나씩 a에 존재하는지 확인
# 존재한다면 1 존재하지 않는다면 0을 출력
for v in values:
if v in a:
print('1')
else:
print('0')