[Java DeepDive] - Map(HashMap) 1. 개념, 필드, 생성자

🔗  Map(HashMap)

Java에서 가장 많이 사용하는 자료구조는 List와 Map이 아닐까 생각합니다.

어디에서든 굉장히 많이 활용하는 자료구조로 저또한 많이 사용하는데요, 이번에는 Map 인터페이스의 개념과 제공되는 API들, 구현체인 HashMap에 대해 살펴보겠습니다. 

(예제 코드는 깃허브에서 확인하실 수 있으며, 버전은 Java 11을 사용했습니다.)

 

https://www.geeksforgeeks.org/java-util-hashmap-in-java-with-examples/

Map 인터페이스는 Collection 프레임워크와는 다르게 키와 값을 하나의 쌍으로 저장하는 Key-Value 형식의 자료구조 입니다.

 

Key는 이름 그대로 값(Value)을 찾기 위한 역할을 하며 Map 인터페이스의 key, value는 다음과 같은 특징을 가지고 있습니다.

• key는 중복이 불가능하지만, value는 중복이 가능합니다.
• 각 key는 최대 하나의 value에 매핑될 수 있습니다.
• 일반적으로 요소의 순서는 유지하지 않습니다.
• Map 컬렉션에 속하는 클래스는 HashMap, LinkedHashMap, Hashtable, TreeMap 등의 구현 클래스가 있습니다.

 

개인적으로 Map 인터페이스의 구현체로 동기화가 필요한 일부 케이스는 ConcurrentHashMap을, Key의 순서가 필요할 경우 TreeMap을 그 외의 케이스는 HashMap을 사용을 했던 것 같습니다.

 

Map 인터페이스에 존재하는 추상 메서드, default 메서드 목록 입니다.

(참고로 of 메서드의 경우 Java 9에서 추가된 팩토리 생성자 메서드로 수정이 불가능한 Map을 생성합니다.)

위 테스트 처럼 Map.of() 메서드를 통해 생성한 객체를 변경(put)할 때 UnsupportedOperationException 예외가 발생합니다.

 

※ 인텔리제이 같은 똑똑한 IDE가 경고를 나타내주고 있긴하지만, 개인적인 생각으로는 코틀린의 List나 Map처럼 데이터를 추가하거나 삭제하는 put(), add(), remove() 등의 메서드를 애초에 제공하지 않도록 강제하여 컴파일 타임에서 확인이 가능했으면 어땠을까 하는 생각이 드네요.. 😯

 

ImmutableCollections 클래스는 불변 컬렉션을 위한 컨테이너 클래스입니다. 즉, Map뿐만 아니라 List, Set 등에 대해 불변 객체를 생성하는 생성자도 존재합니다.

 

 

 

🔗  HashMap 설명

Map의 구현체 중 가장 많이 사용하는 HashMap에 대해 살펴보겠습니다.

HashMap 클래스에 설명에 대한 주석문인데요, 굉장히 길기때문에 간략히 정리하면 다음과 같습니다.

• Map 인터페이스의 Hashtable 기반 구현체
• 이 구현체(HashMap)는 key와 value가 null을 허용함
• 동기화되지 않고 null을 허용한다는 점을 제외하면 Hashtable과 거의 동일함
• 순서를 유지하지 않음
• 해시 함수가 버킷 간 요소를 적절히 분산한다고 가정할 때 기본 작업(get, put)에 대해 O(1) 제공
• 반복 성능이 중요한 경우 초기 용량을 너무 높게 설정하지 않는 것이 매우 중요함
• HashMap 인스턴스는 성능에 영향을 미치는 두 가지 매개변수: 초기 용량, 부하 계수가 존재함
  • 용량은 해시 테이블의 버킷 수를 나타내며, 초기 용량은 해시 테이블을 생성할 때의 용량
  • 부하율은 용량이 자동으로 증가하기 전 해시 테이블이 얼마나 꽉 찰 수 있는지를 나타내는 척도
  • 해시 테이블의 항목 수 > 현재 용량 * 로드 팩터 일 경우, 해시 테이블은 재해시되어 해시 테이블의 버킷 수가 약 두 배 증가
• 일반적으로 기본 부하 계수(0.75)는 시간과 공간 비용 간 좋은 균형을 제공
• HashMap 인스턴스에 많은 매핑이 저장된 경우, 충분히 큰 용량으로 생성하면 테이블 확장 시 필요한 자동 재해싱을 수행하는 것보다 더 효율적으로 매핑을 저장할 수 있음
• 동기화가 되지 않기 때문에 필요할 경우 외부적으로 동기화를 해야 함
• 동기화가 필요할 경우 컬렉션을 사용하여 Collections.synchronizedMap 메서드를 통해 Map을 Wrapped 해야 함
  • Collections.synchronizedMap의 경우, synchronizedList() 처럼 내부 로직은 대부분 synchronized 블럭으로 구현이 되어 있습니다.
  • 주석에는 없지만 ConcurrentHashMap 클래스를 사용하는 방법도 있을 것 같습니다.

알고있던 내용도 있고 처음 보는 내용도 많이 존재하는데요 아래에서 조금 더 자세히 살펴보겠습니다.

 

 

 

🔗  HashMap 필드 1. 상수

HashMap 클래스에는 위 사진처럼 여러 필드들이 존재하는데요, 각 필드에 대한 설명은 다음과 같습니다.

• DEFAULT_INITIAL_CAPACITY: Map의 기본 초기 용량(=버킷 수)으로 디폴트 값은 16
• MAXIMUM_CAPACITY: 최대 용량으로 해당 값을 초과할 수 없습니다. 값은 2^30으로 1,073,741,824
• DEFAULT_LOAD_FACTOR: Map의 용량을 늘려야 하는 시기를 결정하는 지표로 기본 값은 0.75(75%)
  • 예를 들어 HashMap의 사이즈가 16이고 Load Factor은 0.75일 경우 전체 사이즈 16에서 75%에 해당하는 12 크기의 저장소가 이미 사용중이라면, 저장소의 크기를 resizing할 시기라고 판단합니다.
  • 추후 설명드리겠지만, resizing 시 저장소 크기는 2배로 증가합니다.
• ~_THRESHOLD:  THRESHOLD는 임곗값을 나타내는 용어로 트리를 사용하거나/사용하지 않거나 하기 위한 임계값을 나타낸다고 주석에 설명이 되어 있습니다. 버킷의 갯수가 일정 수준을 넘어가면 버킷 관리를 Tree 형식으로, 그렇지 않다면 LinkedList(Node) 형태로 관리하는것에 따라 값을 의미하는 것 같습니다. (정확하게는 이해하지 못해 틀릴 수 있습니다..😦)

 

지난 List의 ArrayList처럼 HashMap도 초기 용량을 적절히 설정하여 객체를 생성하는 것이 효율적입니다.

(List의 경우 Arrays.copyOf() 메서드를 사용하여 새로운 배열을 생성하는 작업을 진행하기 때문입니다.)

• Map의 경우 각 요소를 bucket이라고 하는 공간에 저장을 하는데 초기 용량을 설정하지 않아 16인 경우 부하율(Load Factor) 대비 공간이 가득 차면 resizing하는 작업이 수행되며 이 때 모든 요소들에 대해 해시값을 통해 어떠한 bucket에 저장할지 계산을 하는 과정(rehasing)이 있기때문에 객체를 생성할 때 적절한 용량을 설정하는 것이 좋습니다.
• 반대로 초기 용량을 너무 크게 설정한다면 사용되지 않는 불필요한 공간을 낭비하기에 적절한 값 설정이 중요할 것 같습니다.

 

 

 

🔗  HashMap 필드 2. 변수

HashMap의 key-value 요소는 위 사진처럼 Node<K,V>[] table 변수에서 관리가 됩니다.

threshold의 경우 Map의 크기 조정이 필요할 때 다음 크기 값(용량 * 부하율)을 의미합니다.

 

 

 

🔗  HashMap 생성자

HashMap의 생성자는 위 사진처럼 총 4개가 존재합니다.

 

int 타입의 인자는 HashMap의 초기 용량을 의미하며, float 타입 인자는 위에서 살펴보았던 Load Factor의 부하율을 의미합니다.

마지막 Map 타입 인자는 동일한 매핑을 하고 있는 Map을 받아서 생성합니다.

 

생성자에는 유효성 검증을 통해 초기 용량, loadFactor 값을 설정하는데요 위에서 tableSizeFor() 메서드에 대해서만 살펴보겠습니다.

 

초기 용량(initialCapacity)를 10으로 설정했을 때 tableSizeFor 메서드가 리턴하는 값은 16입니다.

따라서, threshold 값은 16이 됩니다.

(아래 주석처럼 리턴하는 값은 항상 2의 제곱수 입니다... 2-4-8-16-32-64 ...)

 

numberOfLeadingZeros() 메서드의 로직은 아래와 같으며 해당 코드에 대한 설명은 stackoverflow를 참고해주세요:

 

이상으로 HashMap의 개념 및 각 필드 생성자에 대해 살펴보았습니다.

내용이 너무 길어지기에 2편으로 나누어 다음 시간엔 HashMap의 다양한 메서드와 리사이징, 해시 등에 대해 살펴보겠습니다.

 

 

 

📄  참고자료

• https://www.baeldung.com/java-hashmap-load-factor
• http://egloos.zum.com/iilii/v/4457500