자바 HashMap 의 동작

1. HashTable

• 원소의 검색과 저장을 O(N) 에 해결한다.
• 해쉬 함수(r mod M)로 해쉬 값을 구하고 해쉬 값을 주소로 하는 위치에 저장한다.

2. 해쉬 충돌

해쉬 값이 겹치는 경우 두 가지 방법으로 해결한다.

• 체이닝 방법 : 같은 주소에 해당하는 원소를 링크드 리스트로 관리한다.
• Open Addressing 방법
  • 주어진 테이블 공간 안에서 해결한다.
  • 선형조사 : 해쉬 값으로 하는 주소에 데이터가 있으면 다음 주소에 넣는다.
    다음 주소에도 있으면 비어있는 주소가 나올 때 까지 다음 주소를 확인한다.
    마지막 까지 도달하면 해쉬 버켓의 처음으로 돌아간다.
    특정 영역에 원소가 몰려있으면 성능이 저하된다.
  • 이차원 조사 : 다음 주소를 찾는 보폭을 2차원 함수 값으로 늘려가며 찾는다.
    특정 영역에 원소들이 몰려있으면 그 영역을 빨리 벗어날 수 있다.
    최초 해쉬 값이 같으면 앞선 값들이 충돌한 구간을 모두 다시 지나가야하는 단점이 있다.
  • 더블 해싱 : 해쉬 함수를 두 개 사용한다. 하나는 최초 해쉬 값을 구할 때,
    다음은충돌이 발생 했을때 다음 해쉬 값을 구한다.

3. Java HashMap 의 해쉬 충돌 해결 방법

• 자바의 HashMap 은 키 충돌 문제를 체이닝 방법으로 해결한다.
• HashMap 의 데이터가 일정 수 이상이 되면 키 충돌이 갑자기 많이 늘어나지만,
  체이닝은 선형적으로 증가하기 때문이다.
• load factor(3/4) * 해쉬 버켓의 수(초기 값 16) 보다 데이터가 많이자면 해쉬 버켓 수를 두 배로 늘린다.
  • 이 경우 index = x.hashCode() % 2^a 가 되어 x.hashCode() 결과의 하위 a 비트만 사용해
    키 충돌이 쉽게 일어날 수 있다.
  • 2^a 대신 소수를 사용하는 것이 가장 충돌을 적게 만든다.
  • 자바는 키 충돌을 줄이기 위해 보조 해쉬 함수를 사용한다.
• 자바8 부터 데이터가 일정 수를 넘어가면 체이닝의 링크드 리스트를 트리 형태로 바꾼다.
  • 하나의 해쉬 버켓에 8개의 노드가 생기면 트리로 바꾼다.
  • 이 방법으로 성능의 이점을 보고 있어 자바8의 보조 해쉬 함수는 간단한 형식으로 구현되어 있다.