[자료 구조 및 기초] Hash Code에 대해 알아보자

Kotlin을 쓰다보면 아래의코드를 잘 보지 않았을 것 같습니다.

왜냐하면 data class를 구현할때, 기본적으로 재정의 되기 떄문입니다.

해쉬 코드란?

Map은 HashMap, Set은 HashSet이 있는, 접두에 Hash가 들어간 자료구조를 많이 들어보셨을껍니다.

Hash가 들어간 자료구조들은 인자(T) 타입의 hashCode() 메서드를 활용하여 해당 해쉬를 내부적으로 저장합니다.

hashCode()는 어떻게 작동할까?

hashCode()는 재정의 하지않는 이상 알아서 만들어집니다.
hashCode가 중복되면 의미가 없기때문에 , 최대한 중복되지 않게 hash알고리즘을 통해 생성이 되는데요.
*31이 붙는 이유는 홀수(오버플로우 발생시 정보잃는거 방지)이며, 소수(전통적인 관행)이기 때문에 그렇습니다.

해쉬 충돌이 발생한다면?

아무리 잘만들어도 데이터가 워낙 많다면 충돌이 발생할 수 밖에 없겠죠?
충돌이 발생하면 아래의 Chaning을 이용하여 버킷내부의 원소를 LinkedList로 저장하게 됩니다.

체이닝 Chaining

하나의 키가 아닌 링크드 리스트를 저장하는것을 말합니다.
LinkedList인 만큼 구현이 쉽고, 맨앞에 추가하기 떄문에 삽입에 O(1) 이라는 장점을 갖습니다.

하지만 값을 찾아볼땐 전부 순회하기 때문에 O(N)의 시간이 걸립니다.

참고

[Java] 해시코드(hashCode)란 무엇인가?