해시 알고리즘(hash algorithm)
해시 함수, 해시 알고리즘
임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 여러가지 해시 알고리즘이 있는데 대표적으로 SHA 시리즈와 MD5가 있다.
해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 해시라고 한다. 해시의 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다.
해시 테이블
해시함수를 사용하여 키를 해시 값으로 변환하고, 이 해시 값을 색인(index)으로 삼아 키와 데이터(value)를 저장하는 자료구조를 말한다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.
해시 충돌(Hash Collision)
해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 해시값을 내는 상황을 의미한다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.
해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시 충돌이 자주 발생하지 않도록 구성되어야 한다.
해시 충돌을 해결하기 위해 사용하는 방법은 보통 두 가지가 있다.
1. 개별 체이닝(Separate Chaining): 중복된 해시 값이 있는 경우, 연결 리스트로 만들어 저장한다. 그러나 이 방법은 연결 리스트로 인해 선형 검색을 해야 하기 때문에 최악의 경우 수행 시간이 O(n)이 된다.
2. 개방 주소법: 개별 체이닝은 연결 리스트로 데이터를 이어놓을 뿐, 데이터의 주소값(인덱스)은 바뀌지 않는 Closed Addressing 기법이다. 반면 개방 주소법은 해시 충돌이 일어나게 되면 비어있는 다른 인덱스를 찾아 데이터를 삽입하는 방식을 택한다. 이 때 다른 인덱스를 선택하는 로직으로는 대표적으로 3가지 로직 중 하나를 따른다.
- 선형 탐색 (Linear Probing): 해시 충돌시 다음 인덱스, 혹은 몇 칸 뒤 인덱스에 데이터 삽입
- 제곱 탐색 (Quadratic Probing): 해시 충돌시 제곱만큼 건너 뛰어 인덱스에 데이터 삽입
- 이중 해시 (Double Hasing): 해시 충돌시 다른 해시 함수를 한 번 더 적용한 해시코드 이용