toStirng() 메서드를 오버라이드 하고나서, 추가적으로 hashCode() 메서드도 역시 오버라이드 해보라고 하셨다.
어떤 의도로 이것을 오버라이딩 해보라고 하셨을까? 라는 생각을 해보았을 때 hashCode() 메서드를 자세히 알지 못했기 때문에 질문의 의도를 제대로 파악하지 못했다.
클래스 주석을 읽어보니 이 메서드가 재정의 될 때마다 hashCode 메서드를 재정의 해야하며, 이는 동일한 객체가 동일한 해시 코드를 가져야 한다는 hashCode 메서드에 대한 규약을 유지하기 위해서 필요하다고 나와 있다.
재정의를 해줘야 하는 이유
일단 동일한 해시코드를 가지기 위해서 재정의를 해야한다고 나와 있는데, 왜 재정의를 해야하는지는 정확히 알지 못했다.
따라서 인터넷에 이유를 검색해보니 굉장히 많은 글들이 나와있었다. 되도록이면 공식 문서를 보기로 했지만, 이유에 대한 것은 클래스 주석에서 자세히 설명해주지는 않기 때문에 인터넷에 나와있는 글을 읽기로 하였다.
따라서, 좋은 블로그 글을 읽게 되었고, 해시 코드 재정의를 해줘야하는 이유를 알게 되었다. 해시 맵 같은 자료구조에서 객체를 키 값으로 사용하게 되면 동일한 객체는 동일한 해시 코드 값을 반환해야지, 그렇지 않으면 다른 값이 나와서 해시 맵에서 값을 찾을 수 없다.
그렇다면, 만약 서로 다른 Task가 같은 해시 코드 값을 가지고 있다면 과연 HashMap은 중복된 해시값을 가지는 Task를 어떻게 처리할까라는 질문을 하셨다.
당장 생각을 해보았을 때는 당연히 같은 버킷에서 선형적으로 검색을 할 것이고 만약 충돌이 많이 발생을 하게 된다면, 리스트 형태로 길게 늘어져 검색하는데 성능이 떨어질 것이다. 따라서 내부적으로 어떤 처리를 할 것이라고 생각을 할 수 있지만 어떻게 처리하는지 잘 모르고 있었다.
해시 충돌
해시 테이블의 검색 성능은 일반적으로 O(1)이지만 충돌이 많이 일어나게 되면 같은 버킷에 많은 데이터가 선형으로 길게 늘어서므로 O(n) 의 복잡도를 가지게 된다. 따라서 충돌이 많이 일어나지 않게 설계하거나, 아니면 충돌이 많이 일어났을 때 재배열을 시켜줘야한다.
해시 충돌이 일어나더라도 키-값 데이터를 잘 저장하고 조회할 수 있게 하는 방식의 종류
- Open Addressing
데이터를 삽입하려는 해시 버킷이 이미 사용중인 경우, 다른 해시 버킷에 데이터를 삽입하는 방식이다.
- Separate Chaining
링크드 리스트를 이용하는 방식이다. 만약 충돌이 발생하면 그 index가 가리키고 있는 링크드리스트에 노드를 추가하여 값을 추가한다.
해시 버킷 동적 확장
해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만, 해시 충돌로 인해서 성능상의 손실이 발생한다. 따라서 HashMap은 키-값 쌍의 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다.
모던 자바 인 액션에서 HashMap에 대한 설명이 있어서 적어보았다.
- 기존의 맵의 항목은 키로 생성한 해시 코드로 접근할 수 있는 버켓에 저장하였다.
- 해시 충돌이 일어난다면 O(n)의 시간이 걸리는 LinkedList로 버킷을 반환해야하므로 성능이 저하된다.
- 최근에는 버킷이 너무 커질 경우에는 이를 O(log(n))의 시간이 소요되는 정렬된 트리를 이용하여 동적으로 치환하여 충돌이 일어나는 요소 반환 성능을 개선한다.
보조 해시 함수
키의 해시 값을 변형하여 해시 충돌이 날 가능성을 줄여주는 목적의 함수이다.
출처
