HashCode 알아보기
안녕하세요.
카카오헤어샵 백엔드 개발자 paige입니다.
최근에 개발을 하다 Java hashCode() 메서드가 사용된 코드가 의도대로 동작하지 않는 것을 발견하였습니다.
그래서 오늘은 해시 함수와 hashCode() 메서드에 대해서 정리해 보고자 합니다.
해시 함수란?
우선 해시 함수에 대해서 알아볼까요?
해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말합니다.
이 함수를 통해 얻어지는 값을 해시 코드라고 합니다.
해시 코드는 원하는 데이터를 빠르게 찾기 위해서 사용합니다.
출처: https://ko.wikipedia.org/wiki/해시_함수
위의 그림과 같은 구조로 어떤 값이 있을 때 해시 코드를 기반으로 저장/검색을 하면 빠른 검색이 가능하게 됩니다. 하지만 그림처럼 같은 해시 코드 값이 나타나는 경우도 있습니다.
이것을 해시 충돌이라고 합니다. 이 해시 충돌은 어떻게 해결해야 할까요?
해시 충돌 해결 방법
Chaining
출처: https://en.wikipedia.org/wiki/Hash_table#Separate_chaining먼저 Chaining 방식이 있습니다. 같은 해시 코드를 갖는 원소를 하나의 연결 리스트로 관리하는 방식입니다.
검색 시에는 해당 연결 리스트를 차례로 지나가며 탐색합니다.
삽입의 경우에는 해시 코드 값을 가지고 연결 리스트에 저장만 하면 되기 때문에 O(1)의 시간 복잡도가 걸리지만 탐색의 경우에는 연결 리스트를 모두 탐색해야 하므로 연결 리스트의 길이가 길어질수록 효율적이지 못하게 됩니다.
Open Addressing
다른 하나는 Open Addressing입니다.
Chaining과 달리 주어진 테이블 공간에서 해결하며 따라서 해시 값과 일치하지 않는 주소에 저장될 수 있습니다. Open Addressing에는 선형 조사, 이차원 조사, 더블 해싱 세 가지 방법이 있습니다.
선형 조사는 충돌이 일어난 공간의 바로 다음 영역에 데이터를 삽입하는 방식입니다. 때문에 특정 영역에 원소가 몰리는 상황이 발생할 수 있고 이때 탐색이 매우 느려집니다.
이차원 조사는 1^2, 2^2, 3^2..으로 다음 영역 대신 차수가 2인 수의 값만큼 떨어진 영역에 데이터를 삽입하는 방식입니다. 선형 조사에 비해 넓은 범위를 가지기 때문에 검색에 효율적일 수 있지만 초기 해시 값이 같은 경우 이후 찾는 주소 역시 계속 충돌이 발생할 수 있습니다.
더블 해싱은 이러한 Secondary Clustering을 해결하기 위해 사용하는 방법으로 두 개의 해시 함수를 사용하는 것입니다. 충돌이 발생했을 때 해시 함수를 사용해 저장할 공간의 폭을 구하면서 초기 값이 같은 경우의 문제를 해결할 수 있습니다.
지금까지 해시 함수에 대해서 알아봤습니다.
그렇다면 Java에서는 해시 함수를 어떻게 사용하고 있을까요?
Java의 hashCode()
Java에서는 HashMap이나 HashTable 등을 통해서 자료를 저장할 때 활용하고 있습니다.
그리고 Object 클래스의 hashCode() 메서드는 Java 객체의 동일성을 비교하기 위해 사용합니다.
Object의 hashCode() 메서드는 위와 같이 native 메서드로 객체의 주소를 기반으로 한 해시 코드 값을 반환합니다.
String 클래스의 hashCode() 메서드도 동일할까요?
String 클래스는 hashCode() 메서드를 재정의 하였습니다.
문자열을 기반으로 해시 코드 값을 구하므로 같은 문자열은 같은 해시 코드를 가지게 됩니다.
그렇담 Enum 클래스의 hashCode()는 어떨까요?
Enum Class는 기본 Object와 같이 객체의 주소 값을 기반으로 정수 값을 반환합니다. 따라서 같은 문자의 Enum 값이라도 다른 해시 코드 값을 가지게 됩니다.
정리하며
해시 함수와 해시 충돌 그리고 자바에 구현되어있는 hashCode() 메서드에 대해서 살펴봤습니다.
다음에 다른 주제로 다시 찾아오겠습니다.
감사합니다.
