[JAVA] _ hash 해시함수

백준 15829 Hashing 문제를 풀려다가 해시 함수에 대한 기본적인 정보가 부족한 것 같아 위키백과 등을 보며 정리해보았다.

 

---

해시 란?

 

"해시 함수에 의해 얻어지는 값"

 

 

해시 함수 (Hash Function) or 해시 알고리즘 (Hash Algorithm) 란?

 

임의의 길이를 갖는 임이의 데이터를 고정된 길이의 데이터(해시 값)으로 매핑하는 함수

 

---

 

해시 함수의 충돌 

 

해시 함수는 입력값의 범위보다 출력값의 범위가 좁은 경우가 많다고 한다.

 

so, 입력값이 달라져도 드물게 동일한 출력값이 나오는 경우가 있는데,

이를 '충돌'이라고 한다.

 

예시 : 비둘기집의 원리, 생일 문제

 

비둘기집의 원리(pigeonhole principle)란 

 

간단하게 말해서 n + 1개의 물건을 n개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리.

 

공이 3개가 있는데, 2개의 상자에 나누어 넣어야한다. 어떤 방법으로 나누어 넣더라고 공을 쪼개지 않는 이상 반드시 둘 중 하나의 상자에는 공이 2개 이상 들어있다.

 

생일 문제(birthday paradox)란

 

비둘기 집의 원리의 확률 버전이라 볼 수 있는 개념으로, 366명(윤년인 경우 367명)이 모여있는 경우 반드시 생일이 같은 쌍이 나오거나 실제로는 그보다 훨씬 적은 수로도 생일이 같은 쌍이 나와 발생하는 문제, 혹은 이런 '문제'가 발생할 가능성 자체를 구하는 문제를 말한다. 인간의 직감은 수학적 사실이 일치하지 않아 모순으로 인식되기도 하기에 '생일 역설'이라고 한다.

 

 

---

해시 알고리즘에서 생일 문제는 중요한 문제로 작용한다.출력이 n비트인 해시 함수는 그 경우의 수가 2의 n 제곱이 되는데, 실제로는 그보다 훨씬 적은 O(2의 n/2제곱) 선에서 충분히 해시 충돌을 찾을 수 있다. 이를 생일 공격이라고 한다.