Hash란?

특정 데이터를 단방향 암호화 기법으로 해시함수를 통해 mapping한 값을 의미한다.

해시 테이블은 해시 함수를 사용하여 index(key) 값을 통해 배열로 계산한다.

해쉬테이블을 사용하여 데이터를 저장했는데, Collision이 발생할 경우가 있다. 특정한 해시 함수를 이용하여 암호화를 진행하는데, 이때 우연히 발생하거나, 해시 함수를 간단하게 사용하면 암호화된 key 값이 동일하여 mapping이 잘못될 경우가 발생한다! 이를 Collision Resolution(해시 충돌) 이라 한다.

이를 해결하기 위한 방법은 크게 두가지로 나눌 수 있다.

1. Open Addressing

해시함수를 통해 mapping을 진행할 때, 해당되는 위치에 이미 데이터가 있을 경우 그 다음 칸으로 데이터를 집어 넣는 것을 말한다.

하지만 이는 내가 원하지 않는 mapping이 일어날 수도 있다.
(똑같은 Hash가 계속 들어온다면...? 그 다음 다음 다음....이 될 수 있다!)

2. Separate Chaining

링크드 리스트 방식으로 해시 함수를 통해 동일한 값이 들어온다면 그 다음에 저장하는 방식이다.

할당된 해쉬테이블의 크기보다 더 많은 메모리를 차지할 수 있다.