숨숨 베이스

지식이 숨어있는 공간

   개발지식  HashMap

HashMap

Last updated on November 30, 2025

1. 정의

<KEY, VALUE> 형태의 데이터 쌍으로 이루어진 자료 구조이다.

2. 특징

  1. 삽입, 삭제, 조회에 O(1) 의 시간 복잡도가 든다. (해시 기반 버킷 테이블 활용)
  1. 키 정렬이 안된다.
  1. Key 값은 중복될 수 없다. (중복된 저장은 갱신으로 간주)
  1. Key, Value에는 Null 값이 허용된다. (Key는 중복되면 안되므로 하나 허용, Value에는 여러 개 허용)

3. 내부 구조

hash_map_내부구조.png
  • Hash 함수
    : bucket index = hashcode(key)% bucket_table_size
    key 객체 내부의 hashcode() 계산 결과를 가져와서 위의 연산을 하여 해당 <Key, Value> 객체가 저장될 bucket table 속 위치를 특정한다.
  • Hash Bucket Table
    : <Key, Value> 쌍이 저장되는 공간으로 배열로 구현되어 있다.

4. 작동원리

HashMap의 작동원리는 삽입을 예로 들어 알아보겠다. 조회와 삭제는 끝처리를 제외하고는 동일하다.
put작동원리1.png
다음과 같이 HashMap이 있을 떄, <kA, vA>, <kB, vB> 값을 집어넣는다고 해보자.

A. HashCode() 연산으로 정수 해시값 찾기

put작동원리2.png
Key 객체 내부 함수인 hashcode()를 활용해, 해당 Key 고유의 정수 Hash값을 찾는다.
 
ℹ️ hashcode() 함수란?
Object 클래스에 존재하는 기본적인 함수로 해당 객체의 해시값을 반환한다.
Object는 모든 클래스의 부모이므로, 어느 클래스든 hashcode() 함수를 가지고 있다.

다만 커스텀 클래스의 경우와 같이 hashcode()가 클래스에 맞게 재정의되지 않았다면, Object의 기본 hashcode가 호출되기 때문에 엉뚱한 해시값이 나올 수 있으므로 커스텀 클래스 구현 시 재정의가 권장된다.

B. Hash 함수를 활용하여 객체가 저장될 Hash Bucket Index 특정 후 저장

put작동원리3.png
Hash 함수의 공식인hash index = hashcode(key) % bucket_table_size 를 활용해 해당 객체가 저장될 Hash Bucket 속 위치를 찾아 value로 저장된다. 현재는 <kA, vA>와 <kB, vB>가 각기 다른 해시값을 가지고 있어 다른 위치에 저장되었다. 하지만 둘의 해시값이 같은 경우도 있을 수 있고, 이러한 경우를 해시 충돌이라 부른다.

C. Hash 충돌 발생 시 대처

해시 충돌이 8번 이하로 일어난 경우
put작동원리5.png
원래 Bucket Table은 단순 배열 형태이지만, 만약 해시 충돌이 하나라도 발생하면 '발생한 버킷만 링크드 리스트 형태로 바뀐다.'
이렇게 되면 해당 버킷의 탐색, 삽입, 삭제 시간 복잡도는 O(N) 수준으로 높아질 것이다. 이것을 막고자, 해시 충돌이 8번을 초과한 경우, 다음과 같이 Balanced Tree 형태로 내부 구조가 다시 변경된다.
해시 충돌이 8번을 초과한 경우
image.png
8번의 충돌을 초과한 해당 버킷만 체인 형태가 BBST(Balanced Binary Search Tree) 형태로 바뀐다. 이로써 충돌이 자주 일어난 버킷에서 특정 값을 조회, 삽입, 삭제할 때도 시간복잡도가 O(logN)으로 줄어든다.

5. 내장 함수

A. Map.compute()

map.compute (K key, BiFunction<K,V,V> fun ( K key, V old-value)

// 작성 예시
map.compute (K key, (k,ov) -> (ov+1))
구조
  • 첫 번째 인자
    : 조작하려는 Key 특정
  • 두 번째 인자
    : 함수형 인터페이스의 구현체가 들어가는 곳으로, 첫 번째 인자인 Key에 대한 연산식이 삽입
    첫 번째 인자를 Key로 가지는 Entry 쌍이 인수로 자동 삽입되며, 해당 람다식의 결과가 Key의 새로운 value 값이 된다.
주의점?
  • 두 번쨰 인자의 계산 결과가 NULL 인 경우
    : 해당 Key의 Entry가 HashMap에서 삭제
  • 첫 번째 인자인 Key가 HashMap에 존재하지 않는 값일 경우
    : 해당 Key값과 두번째 인자 계산 결과를 HashMap에 신규로 삽입
  • 두 번째 인자는 함수형 인터페이스임으로 람다식으로 대체 가능하다.
 

B. map.putIfAbsent(K key, V value)

용도
첫 번째 인자인 Key 값이 map에 없을 경우에, map에 인수로 들어온 Key, Value Entry를 추가 삽입하는 함수이다.
주의점
  • 첫 번째 인자인 Key가 이미 Map에 존재하면 아무런 일도 일어나지 않는다.
  • 첫 번째 인자인 Key가 Map에 없거나, 있더라도 그것의 value가 null 이라면, Key와 Value 쌍이 삽입된다.
 
➡️ 다음 글
☁️
TreeMap