[알고리즘 공부] 해시를 이용한 집합

1. 해시함수란?

해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
특정한 배열의 인덱스를 입력하고자하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.
해시함수는 암호화만 가능하고 복호화는 불가능한 단방향 암호화 기법으로 해시를 만든다.
해시함수는 매우 빠른 처리속도가 특징이다.

2. 용어

키 : 매핑 전의 데이터 값
해싱 : 매핑하는 과정
해시값 : 매핑 후의 데이터 값
해시 테이블 : 해시 값에 의해 직접 접극이 가능한 데이터 구조
슬롯 : 한개의 데이터를 저장할 수 있는 공간

3. 해시 함수의 장점

1. 접근, 탐색 속도가 빠르다.
2. 키에 대한 데이터의 중복확인이 쉽다.

3. 시간 복잡도

파이썬에서는 dictionary로 구현한다.

딕셔너리의 시간 복잡도는 O(1)로 원소가 많아질수록 삽입, 삭제, 탐색속도가 빠르다.

4. 해시 함수의 단점

1. 처리속도가 빨라 무차별 대입 공격을 받을 수 있다.
2. 여러 키에 해당하는 주소가 동일할 경우 충돌이 일어난다. -> SHA-1 대신 해시 값의 크기가 256이어서 더 안전한 SHA-256를 사용해 보완한다.

5. 해시 함수 충돌 방지 알고리즘

• 여러 알고리즘이 있다.

1. Simple Uniform hash

• 충돌이 적은 좋은 해쉬 함수를 만드는 방법
  - 계산된 해시 값들은 0부터 배열의 크기 -1 사이의 범위를 동일한 확률로 골고루 나타낼 것.
  - 각각의 해쉬 값들은 서로 연관성을 가지지 않고 독립적으로 생성될 것.

1. Chaining 기법
2. Linear Probing 기법
3. Quadratic Probing 기법
4. Double hashing 기법

+ 관련된 알고리즘 문제 풀이

백준 1764번

https://www.acmicpc.net/problem/1764

n, m = map(int, input().split())
hear = {}
see = {}
hear_see = []
for i in range(n):
    hear[input()] = i
for i in range(m):
    see[input()] = i
for i in see:
    if i in hear:
        hear_see.append(i)
print(len(hear_see))
hear_see = sorted(hear_see)
for i in hear_see:
    print(i)