Hash에 관하여

해시(Hash)가 무엇인가요?

해시란 데이터를 고정된 크기의 고유한 값으로 매핑하는 것을 의미합니다. 임의의 길이를 가진 데이터를 입력하면 고정된 길이의 값을 출력하는 함수를 해시 함수라고 합니다.

해시 함수의 특징은 단방향성입니다. 입력 데이터에서 해시값으로 변환은 쉽지만, 해시값에서 원래 데이터로 역변환은 거의 불가능합니다. 이는 해시 함수가 데이터의 무결성을 보장하고 보안 용도로 활용되는 데에 주요한 특징입니다. 이러한 단방향성을 평가하는 척도 중 하나가 역상 저항성입니다. 역상 저항성이 우수하다는 것은 특정한 값을 출력하는 입력 값을 찾기 어려움을 의미합니다.

해시를 활용한 HashMap은 검색을 수행할 때 O(1)만에 동작하여 굉장히 빠릅니다.

다른 입력 값이 동일한 출력을 보이는 경우 해시 충돌이라고 합니다.

좋은 해시 함수는 어떤 함수일까요?

좋은 해시 함수는 단방향성, 고유성, 일관성, 고속성이 뛰어난 해시 함수입니다. 출력 값으로 입력 값을 역추적하기 어려워야 하고, 입력마다 최대한 고유한 출력을 보여야 하고, 동일한 입력에는 동일한 출력을 보여야 합니다. 그리고 연산 속도가 빨라야 합니다.

해시 충돌을 어떻게 해결할까요?

해시 충돌을 해결하는 방법은 크게 두 가지로 분류됩니다.

첫 번째는 개방 주소법(Open Addressing)입니다. 이 방법은 충돌이 발생했을 때 다른 해시 버킷에 데이터를 넣는 방식입니다. 단순한 방식으로는 선형 탐사 방법이 있습니다. 한 버킷이 이미 사용중인 경우 다음 인덱스의 버킷을 확인하는 방식입니다. 이 방식은 primary clustering 문제가 있습니다. 이 문제는 충돌이 한 번 발생하면 계속하여 충돌이 발생하는 것을 의미합니다. 이로 인하여 평균 검색 시간은 느려집니다. 쿼드라틱 프로빙 방식은 선형 프로빙보다 충돌이 적습니다. 이는 i^2 만큼 버킷을 건너 뛰며 탐사를 하는 방식입니다.

두 번째는 체이닝(Seperate Channing) 방법입니다. 충돌이 발생한 버킷의 연결리스트에 데이터를 저장하는 방식입니다. 이 방식은 최악의 경우 수행 시간이 O(N)이 될 수 있습니다. 이는 연결리스트 대신 트리를 두어 시간 복잡도를 O(logN)으로 개선할 수 있습니다.

배열의 크기가 작을 때는 개방 주소법이 캐시 효율이 더 높습니다. 그 이유는 충돌이 발생할 때 체이닝 방식이 별도의 공간에 데이터를 저장하는 반면, 개방 주소법은 연속된 공간에 저장하기 때문입니다. 그런데 배열의 크기가 커지는 경우 캐시 히트율이 감소하기 때문에 개방 주소법의 장점은 사라지게 됩니다.

자바의 HashMap에서는 어떤 방법으로 충돌을 해결하나요?

체이닝 방식을 사용합니다. 그 이유는 개방 주소법에서는 삭제 연산을 효율적으로 구현하기 어려운데, remove 함수는 매우 빈번하게 호출될 수 있기 때문입니다. 또한 데이터의 갯수가 일정 갯수를 넘어가면 개방 주소법은 Worst Case 발생 빈도가 높습니다. 반면 체이닝 방식은 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있는 방법이 있습니다.

HashMap은 체이닝 방식에서 트리와 연결리스트 모두 사용합니다. 데이터 삽입 후 데이터가 8개 이상이면 트리로 변환하며, 데이터 삭제 후 데이터가 6개 이하이면 연결리스트로 변환합니다.