Hash란?
임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. —by 위키백과—
간단하게 요점만 말하자면 단방향 암호화 기법으로 해시함수(해시 알고리즘)를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 해시라고 한다.
같은 자료를 묶어서 파악할 수 있는 것이 장점이자 특징이고, 특정 입력에 대해 항상 같은 해시 값을 리턴하기 때문에 이를 이용해 인증이라든지 여러 방면에서 사용가능하다.
hash table?
hash table이란 , key와 value를 가지고 있는 자료구조로 파이썬에서는 딕셔너리를 떠올리면 이해가 빠를 것이다. 주로 효율적인 검색에 활용되고, 알맞는 키로 그 키에 색인되있는 주소를 찾아가 value를 저장 및 출력하는 구조이다. 이때 색인된 주소를 산출하는 것을 해쉬함수 라고 부른다.
그런데 이때 문제가 발생하는 경우가 생기는데, 다른 데이터값임에도 같은 키를 가지게 된다면?,
이러한 상황을 해쉬 충돌 이라고 한다.
hash collision solution?
크게 두가지의 방법이 존재한다.
1. Chaining
이미 사용중인 주소를 피하지 않고, 데이터를 연결하여 저장하는 방식이다. 각 색인된 주소별로 연결리스트(Linked list)를 할당하여, 데이터를 삽입하다가 충돌이 일어나면 연결리스트로 데이터를 연결한다.
2. Open addressing
해시 충돌이 발생하면, 그 주소에 저장하지 않고 비어있는 주소에 저장하는 방법이다.
크게 세가지 방식이 있는데,
- Linear probing : 충돌이 발생하면, 몇개의 주소를 건너뛰어 저장하는 방식
- Quadratic probing : 충돌이 발생하면, 제곱만큼 건너뛰어 저장하는 방식
- Double hashing : 충돌이 발생하면, 다른 해쉬함수를 적용시켜 그 결과값을 이용하는 방식
ㅎㅅㅎ