[Java] HashMap이 키와 값을 빠르게 찾을 수 있는 이유는 무엇일까요?

[rogarithm]

[Java] HashMap이 키와 값을 빠르게 찾을 수 있는 이유는 무엇일까요?

키워드

bucket, 모듈로 계산, linked list, tree

---

HashMap에서 키를 가지고 값을 찾는 과정이 빠른 이유는, HashMap 안 모든 요소를 체크해가면서 키와 그 키에 맞는 값을 찾는 것이 아니라 키를 기준으로 값이 있는 위치를 찾기 때문입니다.

자세하게 살펴보기 위해 키를 기준으로 HashMap의 값을 찾는 메서드인 get이 어떻게 동작하는지 살펴보면:

1. 키를 입력합니다.
2. 키에 hash 메서드를 적용해(hash(키)) 해시값을 얻습니다.
3. 이 해시값을 기준으로 모듈로 계산을 해서 원하는 키-값 entry가 있는 bucket 위치를 찾습니다.

• HashMap 안 (키-값을 갖는) 객체는 키로부터 얻은 해시값을 기준으로 그 위치가 정해집니다. 이것을 bucket이라고 합니다.
• bucket 안에 키-값 단위로 담기는 요소를 entry라고 합니다.
• 모듈로 계산은 원하는 entry가 있는 bucket이 무엇인지 찾기 위한 계산입니다. (*1)
• 해시값이 매우 크더라도 해시값 자체가 아닌 해시값의 모듈로 계산 결과로 키-값의 위치를 찾기 때문에 속도가 빠릅니다.

• [*1]. 모듈로 계산
  • 모듈로 계산의 한 예를 들면, x mod y는 x를 y로 나눈 나머지입니다.
  • 만약 키의 해시값이 30이고, bucket 갯수가 3개라고 할 때, 30 mod 3은 0입니다. 따라서 이 상황에서 get으로 찾으려는 entry는 bucket 0에 있다는 것을 알 수 있습니다.
• [*2]. 만약 서로 다른 키의 해시값이 같아서 같은 bucket에 서로 다른 값이 들어가게 되는 경우, 그 bucket은 linked list 또는 tree 구조를 이루게 됩니다.
  • 기본적으로 linked list 구조를 가지며, bucket 안 요소의 갯수가 일정 threshold를 넘어가면 tree 구조로 변경됩니다.
  • 이럴 경우 tree 안에서 equal 메서드를 이용해 어떤 키-값이 원하는 요소인지 확인해야 합니다. 이로 인해 찾는 시간이 더 길어질 수 있습니다.
  • equal 메서드가 해당 HashMap 타입에 맞게 정의되어 있지 않다면 값을 제대로 찾지 못할 수도 있습니다.