[Java 가지고놀기] Java Map 정리(2) - HashMap

callme.waffle·2024년 9월 18일

Java 가지고놀기

목록 보기
10/18

1. 개요

Java 문법을 복습하며 Collection 구현체들을 정리하던 중 Set의 구현체 다수에서 Map을 사용하는 것을 확인하였습니다.
Map에 대한 지식없이 Set 구현체를 이해하는 것에 어려움이 있어 관련내용을 공부하며 정리하였습니다.

#Reference

Naver D2 Helloworld의 글
테드의 기술블로그

2. Map이란?

Key-Value 쌍으로 이루어진 자료형

Map은 Key와 Value를 각각 한쌍으로 묶어 데이터를 저장하는 Java 자료형을 의미합니다.
자세한 내용은 이 글을 참고해주세요

3. HashMap 구현체

전체적인 상속관계는 다음과 같습니다

  • AbstractMap (implements Map) [Class(Abstract)]
    • HashMap (implements Clonable, java.io.Serializable) [Class]

TL;DR

읽기/쓰기작업을 자주 진행하고, 삽입순서가 고려되지 않아도 되는경우 사용

기본 동작구조

HashMap의 구현체는 다른 자료구조에 비해 구현이 복잡하여, 별도로 정리해보았습니다.

0) HashMap 동작원리

HashMap은 내부에서 Map.Entry를 extend하는 Node 객체 배열을 통해 데이터를 관리합니다. (이 배열을 앞으로 bucket이라 부르고, Node를 담는 각 칸을 slot이라 합니다)
이 배열에 최대한 많은 데이터를 담고 빠르게 접근하기 위해, HashMap은 각 slot에 최대 8개의 값을 LinkedList구조로 담고, 이후부터는 TreeMap 형식으로 변경하여 관리합니다. (성능저하 문제로 인한 Java8 이후 조치사항)

1) HashMap 생성: 저장공간 크기 설정

HashMap을 constructor로 생성하면, 인자로 받는 loadFactor를 통해 treshold를 설정합니다.
이 2개의 값은 각각 필드에 저장되어, 나중에 데이터추가 시 bucket의 크기를 재설정하는 기준이 됩니다.

2) 데이터 추가

HashMap.put()을 통해 데이터를 추가하게 되면, 내부의 HashMap.putVal() 메서드를 호출하여 아래와 같이 데이터 추가작업을 수행합니다.

  1. key값을 해싱하여 hash값 연산
  2. hash값에 해당하는 bucket의 slot에 배열 index로 접근하여 값 저장 -> 상수시간 소요
  3. 변경내용을 전역필드에 반영 & 결과 return

이중 2번 과정에서 다양한 조건별 동작방식이 달라지는데, 조건 별 동작방식은 다음과 같다:

조건1 (slot 내 Node 개수)조건2 (Node 저장방식)동작소요시간
0개LinkedListNode에 감싸 데이터 저장O(1)
1~8개LinkedListLinkedList 형태로 데이터 추가O(1)
9개~LinkedListTreeMap으로 내부데이터 저장형식 전환 후 데이터 추가O(1)
9개~TreeMap저장위치 연산 후 접근하여 데이터 추가O(n)

3) 데이터 접근

HashMap.get()를 통해 데이터 접근 시, 내부의 HashMap.getNode() 메서드를 호출하여 데이터를 가져오게 됩니다.
실제 데이터 접근시 저장형태에 따라 소요시간이 달라지는데, 저장형태 별 소요시간은 다음과 같습니다:

Node 저장방식동작소요시간
LinkedList일치하는 key값을 찾을 때 까지 do-while문으로 순회하며 탐색O(1)
TreeMapTreeMap의 getTreeNode() 메서드 호출하여 탐색O(n)

+) LinkedList방식으로 저장 시 소요시간이 O(1)인 이유는 do-while 문을 사용하더라도 저장개수 제한되어 있어 최대 8회만 동작하기 때문이다.

동작 별 소요 시간복잡도

최종적으로 동작 별 소요되는 시간복잡도는 다음과 같습니다:

동작유형시간복잡도설명
추가O(1) / O(n)TreeMap 사용 시 최대 O(n)
조회 - getO(1) / O(n)TreeMap 사용 시 최대 O(n)
조회 - containsO(n)for문으로 순회하며 데이터 존재여부 확인
삭제O(1) / O(n)TreeMap 사용 시 최대 O(n)

4. 결론

Set을 더 정확히 이해하기 위해 본 HashMap의 양이 생각보다 많았습니다.
그래도 이왕 시작한만큼 제대로 정리해서 이해할 수 있도록 노력해야겠습니다.

profile
Developer waffle = new Waffle();

0개의 댓글