Hash
- 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
- 해시 함수에 의해 얻어지는 값은 "해시값, 해시코드, 해시체크섬, 해시"라고 함
- 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용됨
Hash 충돌이란?
- 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미
- 해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시 충돌이 자주 발생하지 않도록 구성되어야 함
- 해시 충돌을 일으키는 임의의 두 값을 찾는 과정을 '충돌 공격(collision attack)'이라고 함
- 또한 주어진 값에 대해 그 값과 해시 충돌을 일으키는 값을 찾는 것은 역상 공격이라고 함
- 암호 공격라는 측면에서 보면 역상 공격은 충돌 공격 보다 더 심각한 공격이 될 것임
- 충돌 저항성:
* 약한 충돌 저항성: 주어진 x에 대해서 H(x) = H(y)인 x,y를 찾는 것이 어려울 때- 강한 충돌 저항성: H(x) = H(y)와 같이 같은 해시값을 갖는 x와 y를 찾는 것이 함수의 출력 값 범위 내에서 무시가능할 때
Hash 충돌 해결책은 어떠한 것들이 있나요?
- 해쉬 함수를 잘 짠다. 하지만 아무리 잘 짜도 비둘기집 원리에 의해 충돌은 불가피하다. 따라서 3의 처리가 필요하다.
- 해쉬 충돌이 일어났을 때 어떻게 처리되는가? open, close 어드레싱의 방법이 있다. 충돌이 일어났을 때 특별한 연산을 통해 비어있는 다른 인덱스를 찾는 방법과, 배열 안에 배열 혹은 연결 리스트로 계속 붙여나가는 방법 등이 있다.
(1) 체이닝
: 같은 주소로 해쉬되는 원소를 모두 하나의 연결 리스트에 매달아 관리
(2) 개방주소 방법(Open Addressing)
: 개방주소 방법은 체이닝과 같은 추가 공간을 허용하지 않고 주어진 해쉬 테이블 공간 내에서 해결한다.
먼저 해쉬 함수를 계산하여 계산된 주소를 차지하고 있는 다른 원소가 없으면 그 자리에 넣고, 이미 그 자리를 차지한 원소가 있으면 정해진 규칙에 따라 다음 자리를 찾게된다.
처음 계산한 해쉬 함수를 0번째 해쉬함수, 충돌이 일어나서 다음 주소를 계산하는 것을 1번째 해쉬함수 ... 이런식으로 표현한다
(3) 선형 조사(Linear Probing)
: 선형 조사는 가장 간단한 충돌 해결 방법으로,
충돌이 일어난 바로 뒷자리를 보는 것이다.
이렇게 하면 i번째 해쉬 함수는 h(x)로 부터 i만큼 떨어진 자리가 된다.
테이블의 경계를 넘어갈 경우에는 맨 앞으로 돌아간다.
(4) 이차원 조사(Quadratic Probing)
: 이차원 조사는 바로 뒷자리를 보는 선형 조사와 달리
보폭을 이차함수에 의해 넓혀가면서 본다.
예를 들면, i번째 해쉬 함수를 h(x)로 부터 i^2만큼 떨어진 자리로 삼을 수 있다.
즉, h(x), h(x)+1, h(x)+4, h(x)+9, h(x)+16.... 과 같이 볼 수 있다.
(5) 더블 해슁(Double Hashing)
: 더블 해슁은 두 개의 함수를 사용한다.
더블 해슁에서 i번째 해쉬 함수는 다음과 같다
여기서 h(x)와 f(x)는 서로 다른 해쉬 함수이다.
충돌이 생겨 다음에 볼 주소를 계산할 때
두 번째 해쉬 함수값 만큼씩 점프를 한다
(https://images.velog.io/images/muchogusto/post/bbcfbd14-ddf1-48cc-9c74-facfeb7eca62/image.png)
Reference
- 위키백과 해시 함수 (https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98)
- 위키백과 해시 충돌 (https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%EC%B6%A9%EB%8F%8C)
- 해쉬 충돌이 무엇이고, 해결책을 알고 있나요? (https://stdin2stdout.tistory.com/entry/Q-%ED%95%B4%EC%89%AC-%EC%B6%A9%EB%8F%8C%EC%9D%B4-%EB%AC%B4%EC%97%87%EC%9D%B4%EA%B3%A0-%ED%95%B4%EA%B2%B0%EC%B1%85%EC%9D%84-%EC%95%8C%EA%B3%A0-%EC%9E%88%EB%82%98%EC%9A%94)
- 해슁에서 충돌해결(https://itstory.tk/entry/%ED%95%B4%EC%8A%81%EC%97%90%EC%84%9C%EC%9D%98-%EC%B6%A9%EB%8F%99%ED%95%B4%EA%B2%B0Collision-Resolution)
