Hash code
해시 코드는 어떤 데이터를 대표하는 숫자값이다.
자바에서는 모든 객체가 hashCode() 메소드를 통해 해시 코드를 제공하며 해시 코드는 자료 구조인 해시 테이블에서 사용된다.
해시 코드의 목적은 크게 두 가지로, 데이터의 빠른 저장 및 검색을 가능하게 하고, 또한 데이터의 동일성을 판별하는 데에도 사용된다.
Object 클래스의 hashCode() 메소드는 기본적으로 객체의 메모리 주소를 반영한다.
그러나 메모리 주소를 직접적으로 표현하는 것은 아니고, 메모리 주소를 기반으로 만들어진 값을 해시코드로 사용한다.
또한 해시값이 항상 고유하지는 않아 서로 다른 객체라도 해시충돌이 발생할 수 있다.
주소값은 64bit로 저장되는 반면 (64bit사양) 해시코드는 32비트의 정수인 int로 저장되는데, 메모리를 표현하는 값 보다 해시코드를 표현할 수 있는 값이 더 적기 때문에 다른 주소값을 가지고 있다고 하더라도 해시충돌이 일어날 수 있는 것이다.
hashCode() 메소드는 오버라이드하여 필요에 맞게 해시 코드 생성 규칙을 정의할 수 있다.
HashMap
해시맵은 해시코드를 이용해 자료를 저장하거나 읽는다.
해시맵은 여러 버킷으로 구성되어있는데(기본 16개),
키 값의 해시값을 버킷의 수로 나눈 나머지값 번째의 버킷에 키-밸류를 저장한다.
예로, 키값의 해시값이 42이고 버킷의 수가 16인 경우
( 42 % 16 => 10 ) -> 10 번째 버킷에 키와 밸류 값을 저장한다.
만약 다른 키-값 쌍이 이미 같은 버킷에 저장되어 있다면, 해시맵은 이러한 상황을 처리하기 위해 "체이닝"이라는 방법을 사용한다. 체이닝은 같은 버킷에 속하는 모든 키-값 쌍을 연결 리스트로 관리하는 방법이다.
따라서 해시맵은 키 값의 해시코드를 이용해 항상 같은 단계의 알고리즘으로 자료를 찾아내므로 O(1)의 시간복잡도로 value를 찾지만, 같은 버킷에 키밸류가 리스트로 저장되어 있는 경우 리스트를 한 번 더 순회해야 하므로 O(N)의 시간복잡도가 추가된다.
저장하는 자료가 많아질 수록 버킷이 충돌하는 일이 많아져 자료를 탐색하는 시간복잡도가 증가하므로
HashMap은 75% 이상의 버킷이 사용되는 경우 그 수를 두 배로 늘린다.
