Hash

해시(hash)란 단방향 암호화 기법으로 해시함수(해시 알고리즘)를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미합니다.
출처

중요한것은 단방향 변환이다.

Hash Function

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
출처

즉 변환의 축이 되는 함수를 Hash function이라고 한다.

특징

• 입력값이 일부만 변경되어도 전혀 다른 해시값을 출력한다.
• 입력값 상관없이 고정된 길이의 해시값을 출력한다.
• 같은 입력값에 대해서는 같은 출력값을 보장
• 대표적인 Hash function으로 SHA, MD5등이 있다.

레인보우 테이블
특정 hash function이 만들어 낼 수있는 값을 저장해놓은 표를 의미한다.
이 때문에 어느정도 복호화가 가능하다.

Collision

hash function이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.
출처

임의의 길이의 데이터를 고정된 길이로 바꾸다보면 당연히 중복이 생긴다. ->비둘기집 원리
그렇다보니 다른 데이터일지라고 hash table에 같은 곳을 볼 수가 있는데 이를 hash collision이라고 한다.

해결법

Chaining

출처

충돌될 경우, 해당 값을 기존에 값의 다음으로 연결리스트를 통해 연결짓는(Chain) 하는 방법이다.

특징

• 연결리스트가 쌓이면 탐색에 O(n)이 소요된다.
• 특별한 경우 연결리스트가 아닌 자가균형 이진 트리로 구현이 가능하다.

Open Addressing

대표적으로 3가지 방식이 있다.
1. 선형 탐색(Linear Probing) - 해시충돌 시 다음 버킷 또는 비어 있지 않다면 몇 개 건너뛰어 데이터를 삽입한다.
2. 제곱 탐색(Quadratic Probing - 해시충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입한다.
3. 이중 해시(Double Hashing) - 해시충돌 시 해시를 한번 더 적용해서 나온 버킷에 데이터를 삽입한다.

특징

• 2차 충돌이 생길 수 있다. (다른 버킷에 데이터를 저장하기 때문)
• 다른 자료구조(Linked List)나 포인터가 필요 없다.
• 최악의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 돌아올 수도 있다.
• 데이터가 적을 때 유리하다.