해싱이란 데이터를 해시함수에 넣어 해시코드를 만들고 이 해시코드를 인덱스로 분류해 값을 저장하는 방식이다.

해시함수는 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

이때 인덱스와 value가 있는 테이블을 해시테이블이라고 부른다.

F(key) → Hashcode → Index → value

해싱의 최대 장점은 검색 속도가 빠르다는 것이다. 해시 함수를 통해 얻은 해시코드가 index에 바로 매칭이 되기 때문에 인덱스에 바로 접근해 값을 확인할 수 있다.

하지만 충돌할 수 있다는 문제도 있다.

크기가 더 큰 데이터를 적은 데이터로 매핑시키는 것이기 때문에 당연히 충돌이 발생할 수 밖에 없다. 따라서 해싱에서 충돌을 어떻게 처리할 것인지는 아주 중요한 문제이다.

대처방안 1. chaining

해당 인덱스에 이미 값이 들어가 있다면 링크드 리스트로 연결해 값을 찾을 수 있게 하는 방식이다.

하지만 특정 인덱스에만 계속해서 값이 채워진다면 시간 복잡도가 O(1)에서 최대 O(n)까지 갈 수 있어 비효율이 발생할 수 있다. 또 빠르게 찾으라고 테이블을 만들어 뒀더니 리스트만 찾아다닐 수도 있다.

대처방안 2. Probing

chaining 방식의 문제점을 좀 더 보완하고자 나온 방식이다. 테이블 공간이 남아 있다면 리스트로 연결하지 않고 비어있는 공간을 찾는 것이다.

대처방안 3. Resizing

하지만 테이블이 다 차서 더이상 비어있는 공간이 없다면 probing도 할 수가 없다. 이때는 사이즈를 늘려서 새롭게 재배열 하는 방법도 있다.