Hashing

해싱이란 임의의 길이의 데이터를 받아 해시함수를 사용해 정해진 사이즈의 데이터로 변환하는것을 의미합니다.
입력값이 얼마나 길거나 짧은지에 상관없이 해시 함수를 사용해 변환된 데이터는 일정한 길이를 가져야 합니다.
해싱에서 입력값을 input, 해싱에 사용되는 함수를 hash function, 그리고 결과값을 hash value이라고 합니다.

해싱에 사용되는 알고리즘의 종류는 매우 다양합니다. 하지만 의미 있는 hash function이기 위해서는 어느정도 이상의 퀄리티가 있어야 합니다.
hash value는 유일해야합니다. 쉽게 말하면 서로다른 입력값을 입력했을때 같은 값이 나와서는 안됩니다. 만약 1234를 입력한 값과 12345를 입력한 값과 같으면 안됩니다. 동일한 입력값을 입력했을때 항상 똑같은 hash value를 가져야 합니다. 만약 서로다른 값을 입력했지만 동일한 입력값을 가지게 되는경우를 해시 충돌이라고 합니다. 무한한 입력값을 가지고, 유한한 수의 출력값을 가질경우 비둘기집 원리에 의해 해시 충돌은 무조건 발생하게 됩니다. 이러한 충돌은 해시 함수를 이용한 자료구조나 알고리즘을 떨어뜨리기 때문에 자주 발생하지 않도록 구성해야 해시 함수의 퀄리티가 올라가게 됩니다. hash function은 빨라야합니다. 입력값을 hash function에 전달했을때 빠르게 hash value를 받을 수 있어야 합니다. 또한 hash functon은 안전해야 합니다. 별로 다르지 않은 입력값을 입력하더라도 hash value의 값은 매우 달라야 합니다.

해싱은 주로 비밀번호인증, 자료구조, 데이터의 오류 검출, 그래픽과 같은곳에 사용됩니다.