[Java] HashMap이란

개요

String, ArrayList에 이어서 참조 자료형에 대해 계속 정리해야지. 이번에는 자바에 HashMap에 대해 정리해보겠다.

 

1. HashMap이란?

HashMap은 키(Key)와 값(Value)를 하나의 쌍으로 관리하는 Map 인터페이스의 대표적인 구현체이다.

해시 테이블 기반의 데이터 구조로, 키를 해싱해 인덱스를 계산하고 해당 버킷에 키-값 쌍을 저장한다.

 

1-1. 특징

1) Key-Value Mapping

-> 하나의 키에 하나의 값이 매핑되고, 키의 중복은 허용하지 않는다.

-> 동일한 키로 다시 put할 경우 기존 값이 덮어쓰여진다.

 

2) 해시테이블 기반

-> 키의 해시코드(hashCode())를 활용해 빠른 데이터 접근으로 평균 O(1) 시간복잡도를 제공한다.

 

3) 정렬X

-> 삽입 순서나 키의 크기 순으로 정렬되지 않는다.

-> 순서가 중요하다면 LinkedHashMap이나 TreeMap을 고려해야 한다

 

4) null 허용

-> 키와 값 모두 null을 허용한다.

-> 하지만 null 키는 앞서 말한 것처럼 하나만 존재할 수 있다.

 

2. 내부 구조

HashMap은 내부적으로 배열 + 연결리스트 + 트리 구조를 혼합해 구현되어 있다.

 

HashMap은 내부적으로 배열 형태의 해시 테이블을 기반으로 동작한다. 이때 각각의 배열 요소를 "버킷"이라고 부른다.

즉, HashMap은 해시 함수를 통해 키의 해시 값을 구하고, 이 해시값을 바탕으로 키-값 쌍이 어느 버킷에 저장될지 결정한다.

 

서로 다른 키가 같은 해시 인덱스를 가질 수 있는데 이를 해시 충돌이라고한다.

자바 8 이전에는 해시 충돌이 발생할 때, 해당 버킷에 연결 리스트로 Entry들을 관리해 최악의 경우 O(n)의 조회시간을 가질 수도 있었다.

하지만, 자바 8 이후부터 해시 충돌이 심해질 경우 연결 리스트를 레드-블랙 트리로 변환해 최악의 경우에도 O(log n)의 조회시간을 보장하도록 개선되었다.

 

1) 배열(table)

-> Node<K,V>[] table 형태의 노드 배열을 기반으로 한다.

-> 해시코드(hashCode())를 활용해 인덱스를 계산하고 해당 인덱스에 노드를 삽입한다.

 

2) Node(Entry)

-> 각 엔트리는 Node라는 내부 클래스로 구현되고, key, value, hash, next(다음 노드에 대한 참조)로 구성된다.

 

3) 해시 충돌 처리

-> 동일한 인덱스에 다른 키를 가진 노드들이 충돌하는 경우, 해당 위치에 연결 리스트가 형성된다.

-> 자바 8부터는 버킷 내 노드 수가 일정 임계치를 넘어가면 레드-블랙  트리로 변환되어 조회, 삽입, 삭제 성능을 개선한다.

 

4) hashCode(), equals()

-> HashMap은 키의 hashCode()를 활용해 버킷 인덱스를 계산하고, 동일한 버킷 내에서 같은 키를 찾기 위해 equals() 메서드를 사용한다.

 

5) 초기 용량, 로드 팩터, 리사이즈

초기 용량

-> 기본 초기 용량은 16이다.

 

로드 팩터

-> 해시 테이블이 얼마나 차면 리사이즈할 것인지를 결정하는 값으로, 기본값은 0.75이다.

-> 예를 들면, 로드 팩터 0.75의 의미는 해시 테이블의 크기 *0.75 만큼 엔트리가 찼을 때 테이블 크기를 두 배로 늘린다는 의미이다.

 

리사이즈

-> 해시 충돌을 최소화하기 위해 테이블의 크기를 늘린다. 리사이즈의 비용은 크기 때문에 초기 용량과 로드 팩터를 적절하게 지정하는 것이 중요하다.

 

3. HashMap의 활용

HashMap 선언

HashMap<String,String> mapOne = new HashMap<String,String>(); //기본 생성
HashMap<String,String> mapTwo = new HashMap<12, 0.75f>(); // 초기 용량 및 로드팩터 지정
HashMap<String,String> mapThree = new HashMap<String,String>(){{
	put("apple", "사과")
}}; //초기 값 지정

 

HashMap 메소드

메소드	설명	예제
put(K key, V value)	키-값 쌍을 맵에 삽입하거나, 이미 있는 키면 값을 갱신한다.	scores.put("yoshi", 90);
get(Object key)	키에 해당하는 값을 반환한다. 키가 없다면 null을 반환	scores.get("yoshi");
containsKey(Object key)	키가 맵에 존재하는지의 여부를 확인한다.	scores.containsKey("yoshi");
containsValue(Object value)	값이 맵에 존재하는지 여부를 확인한다.	scores.containsValue(90);
remove(Object key)	키에 대응되는 엔트리를 제거하고 제거된 값을 반환한다.	scores.remove("yoshi");
size()	맵에 포함된 엔트리의 개수를 반환한다.	scores.size();
isEmpty()	맵이 비어있는지 여부를 확인한다.	scores.isEmpty();
clear()	맵에 있는 모든 엔트리를 제거한다.	scores.clear();
keySet()	맵에 담긴 모든 키를 Set 형태로 반환한다.	scores.keySet();
values()	맵에 담긴 모든 값을 Collection 형태로 변환한다.	scores.values();
entrySet()	맵에 담긴 모든 엔트리를 Set<Map.Entry<K,V>>로 반환한다.	scores.entrySet();

 

entrySet()에 대한 코드를 다음과 같이 쓸 수 있다.

Set<Map.Entry<String, Integer>> entries = scores.entrySet();

for (Map.Entry<String, Integer> entry : entries){
    System.out.println("key: " + entry.getKey() + " value: " + entry.getValue());
}