<aside>
</aside>
대한민국 사람들의 정보를 저장하는 자료구조를 만든다고 하자. 모든 데이터를 그대로 저장한다면 5000만명 전국민의 데이터를 하나씩 찾아봐야 할테다. 효율적이고 빠르게 저장된 데이터를 찾고싶다. 사람들마다 고유한 식별자를 갖고 있으면 바로 찾기 수월할 것이다. 사람들은 서로다른 주민등록번호를 갖고있다. 그럼 주민등록번호를 키값으로 갖는 자료구조를 만들면 베스트이지 않을까?
이상적이지만 비현실적이다. 10^13개의 주민번호를 키 값으로 가지는 자료구조로 구성돼야 하기 때문에 엄청난 메모리를 차지하기도 하며 나의 주민등록번호를 찾기위해 000000 ~ 999999까지 모든 값을 찾아야한다.
10^13개의 키값을 갖는 테이블을 N개로 만들 방안이 필요하다. 이때 나오는 개념이 해싱이다. 원본 데이터를 정해진 N개로 매핑하여 작게 만드는 것이다.
// 해싱
981015 -> 98 % 50 -> 48
// 테이블에 저장
[47 -> ...]
[48 -> (나의 데이터)]
[49 -> ...]
대표적인 방법으로는 자릿수를 자른 후 나머지 연산이 있다. 주민등록번호에서 앞/뒤 N자리를 잘라 상수 K로 나머지 연산 후 키값으로 지정하는 것이다. 나의 주민등록번호는 981015-1******이다. 여기서 앞 2자리를 50으로 나눈 48이 나의 키값이다. (해싱 함수와 방법은 정말 많고 예시를 이용해 설명했을 뿐이다.)
(나의 데이터), (98년생 익명의 데이터1), (98년생 익명의 데이터2), .. -> 98 % 50 -> 48
결과적으로 어떠한 주민번호도 해싱함수만 적용해 접근하는 O(1)의 시간복잡도로 데이터를 접근할 수 있으며 10^13개의 상자를 50개로 줄일 수 있게된 것이다. 여기서 의문이 생길 수 있다. 98년생의 모든 데이터들이 같은 키를 가지게 되어 중복이 발생하는 것이다. 이것을 해시충돌이라고 하는데, 충돌 대처를 위한 체이닝/오픈어드레싱 방법과 Java의 대처법을 뒤에 설명하겠다.