[Java] 해시맵(HashMap)? 그게 뭔데 사용법 & 개념 정리

hansung's·2024년 3월 13일

Java 자료구조

🤔 Hash는 뭐고 Map은 뭔가요?

해시맵은 말 그대로 해싱된 맵을 의미합니다. 그럼 해싱은 뭐고 맵은 뭘까요??

Hash

해시(Hash)는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말하는데, 참고로 다른 말로는 해시 값, 해시코드, 체크섬 이라고도 불립니다.

Map

맵은, Key-Value pair들을 저장하는 추상 자료형으로(ADT, Abastract Data type)
같은 Key를 가지는 pair는 오직 하나만 존재할 수 있다.

이를 조금 더 쉽게 설명하자면, Map은 Key-Value로 이뤄지고, Key는 중복된 값을 가질 수 없다는 얘기입니다. 다만 Value는 중복이 되어도 상관 없습니다.

Map은 다른말로 Associative array, dictionary라고도 불린다.

그렇다면, 이러한 Map은 언제 사용할까요?
여러 경우가 있겠지만, 포괄적으로 얘기한다면 Key 값에 대응하는 Value를 찾거나 매핑하고 싶을 때 사용할 수 있습니다.
하나의 예시를 생각한다면, 영화 인기순위와 같은 경우를 생각할 수 있습니다.

~~조잡한 그림이다~~ 영화 제목을 key값으로 평점을 Value값으로 지정해, 해당 영화의 평점을 Map을 통해 구할 수 있다.

자 그럼, HashMap에 대한 Hash와 Map에 대해서 간략히 설명했으니,
정확히 HashMap이 무엇인지 알아보자,

👀 HashMap이란?

HashMap은 Map 인터페이스를 구현한 컬랙션 클래스로
삽입 / 삭제 / 조회 연산의 시간 복잡도가 O(1)인 자료구조이다.
아까 위에서 설명했듯이 중복을 허용하지 않으며, 정렬 또한 불가하다.
그리고, 데이터의 순서 역시 보장하지 않는다.

Map 인터페이스에는 HashMap, TreeMap, HashTable 등이 존재하는데,
여기서 HashMap과 HashTable은 사용법이 유사하지만, 다른 점이 존재한다.

바로 Thread-Safe의 유무인데, HashTable은 동기화(동시접근에 안전)가 걸려 있어, Thread-safe하다고 볼 수 있지만, HashMap은 비동기화라 unsafe하다고 볼 수 있습니다.
그래서 사업조건에 맞게 안정성: HashTable
빠른 처리: HashMap 을 사용할 수 있습니다.

간략하게 설명드린 이유는, HashMap과 HashTable 둘 다 거의 비슷하기 때문에
알아놓으면 나중에 더 좋을 것 같아 설명해봤습니다.

서론이 길었습니다. 대충 적은바를 정리하자면,

HashMap

Map 인터페이스를 구현한 컬랙션 클래스

삽입 / 삭제 / 조회 연산의 시간 복잡도가 O(1)인 빠른 자료구조

하지만, 모든 index에서 충돌이 발생할 경우 O(N)의 시간 복잡도를 가짐

중복을 허용하지 않음

정렬이 불가하다

입력 데이터의 순서를 보장하지 않는다.

동기화를 지원하지 않아 Thread-unsafe(즉, 동시에 쓰레드로 접근하여 데이터 변경시 ConcurrentModificationException 예외 발생)

놓친 부분이 존재하는데, null값이 올 수 있다.

😒 HashMap의 동작원리는?

자 이제 어느정도 HashMap의 특징을 알아 볼 수 있었는데요. 그럼 동작원리는 어떻게 될까요?

HashMap은 해시함수(Hash Function)을 사용하여 임의의 크기를 가지는 type의 입력 데이터를 받으면, 고정된 크기를 가지는 type의 데이터로 변환하는데,
이렇게 변환된 해시값을 통해 우리는 입력데이터를 조회하고 수정하고 삭제할 수 있는겁니다.

동작원리를 간단히 그림으로 그린다면,

이렇게 해시함수를 통해 변환된 값에 capacity(용량 8)을 나눈 나머지 값을
버킷 또는 slot에 저장하게 됩니다.

버킷에는 Key, Value 그리고 **해시값** 총 3개의 값이 저장돕니다.

그렇다면 조회 메서드인 get("파묘")을 하면 어떨까요?
이미 우리는 파묘의 해시값이 404인 것을 알고 있습니다.
이것을 다시 해시함수에 넣으면 4라는 값을 찾을 수 있고, 4를 버킷에서 찾으면
8.22의 값을 구할 수 있을 것입니다.

💢 Hash Collision(해시 충돌)

하지만 해시 자료형태는 근본적인 문제가 있습니다. 바로, 여러 키가 저장되면서 발생하는 주소(인덱스)가 동일해지는 경우 이렇게 해시 충돌이 일어나는데,

해시 충돌에는 두 가지 경우가 존재합니다.
1. Key는 다른데, Hash가 같은 경우

위의 경우를 예로 들면, "파묘" - > hash(404) / "윙카" -> hash(404)를 갖는 경우
해당 부분은 피할 수 없는 충돌로, 해시함수를 사용하는 것은 방대한 입력 데이터를 줄어든 범위로 축약 시키기위해 쓰는건데,
- 이러한 이유로 같은 Hash값이 존재해 충돌이 발생할 수 있는 것이다.
- 해시 함수의 중요한 것이, output(ex. 파묘 -> 404)이 균등하게 나와 균등하게 주소(인덱스)를 가질 수 있도록 하는 것이다.

Key값도 Hash값도 다른데, 주소(인덱스)값이 같다면?

파묘는 현재, 4의 주소값을 가진다고 가정하자,
- 여기서 만약 "듄"의 해시값이 4를 가진다면?
- 키값도 hash값도 다른데, 같은 주소값을 가지게 된다.

위의 예시처럼 결국 해시충돌은 피할 수 없다.

그렇다면 이를 해결할 수 있는 방법에 대해 알아보자

🚑 해시 충돌 해결하기

두 가지 방법이 존재한다. 바로 Open addressing과 separate chaining이 존재하는데

먼저, separate chaining에 대해서 알아보자

Separate Chaining 기법은 해시 테이블 저장공간 외 다른 공간을 활용하는 방법으로
자바의 HashMap 클래스가 해당 기법을 채택하여 사용한다.

위와 같은 버킷 하나하나에 linkedList로 관리하여, 다음 노드를 가리키는 레퍼런스를 저장하고, 파묘 다음에 저장될 수 있도록 하는 방식이 separate chaining 방식입니다.

짧게 그림으로 나타내면, 이런식으로 저장된다는 얘기입니다.

이렇게 되면, 해시 충돌이 일어났을 때, 리스트 형태로 여러개의 키-값쌍을 연결하여 충돌을 해결할 수 있습니다.

Open addressing 기법 중 가장 간단한 linear probing방식으로 설명하면
※ 해당 방법은 Python의 dictionary가 해당 기법을 채택한다고 한다.

4자리에 파묘가 존재한다고 보자, 근데 만약 "듄"의 주솟값도 4로 나오게 되면,
"파묘"가 -> "듄"으로 변경되는 충돌이 일어날 수 있다.

그래서 이를 피하고자 "듄이" 인덱스 4에서 가장 가까운 곳인 5에 저장됩니다.
즉, 충돌이 발생하면 해당 인덱스를 넘어 다음 인덱스부터 맨 처음 인덱스까지 순회하며 빈 공간을 찾는 방식입니다.

이러한 방법으로 해시 충돌을 해결하는게 Open addressing 중 linear probing 방식입니다.

✨ resizing

위에서 이야기한 Open addressing 방법은 공간 활용도를 높이는 방법인데,
만약 데이터가 용량을 넘긴다면? 그러면 어떻게 되는 것인가

그럴 경우에는 버킷 사이즈를 늘려주는 resizing을 해주는 과정이 발생하는데,
자바의 HashMap같은 경우 용량(capacity)가 3/4 정도 차면 자동으로 2배로 크기를 늘려준다.

즉, 현재 용량이 8인데, 16만큼 사이즈가 커지며
해시 함수에서 모듈러 연산(%)를 하여 인덱스를 구했던 것을 기억하는가? 거기에 값 역시 사이즈 만큼 커져서 계산하게 된다.

python의 dictionary와 자바의 HashMap은 유사하게 동작하지만, 
dictionary는 linear probing 방식을
HashMap은 Separate Chaining을 채택하여 사용한다고 한다. 
또한 모듈러 연산(%) 하는 값 역시, 파이썬은 8부터 자바는 16부터라고 하니 참고하는 것이 좋을듯 하다.

이렇게 해서 HashMap에 대해서 간략히 알아봤으며 이제, 사용법에 대해 설명해보겠다.

💦 HashMap 사용법

사실 많은 사람들이 이거 보려고 들어오는건데, 얘기가 잠시 길었다.
HashMap 주요 메서드를 짧게 알아보면

미리 알아두면 좋은 것,
K - 맵에 의해 유지되는 키의 타입
V - 키에 의해 매핑될 Value 값

1. V get(Object key):

해당 맵에서 전달된 키에 대응하는 값을 반환함.만약 해당 맵이 전달된 키를 포함한 매핑을 
포함하고 있지 않으면 null을 반환함.

2. V getOrDefault(Object key, V defaultValue):

지정한 키가 매핑되는 값을 반환하거나, 이 맵에 키에 대한 매핑이 없는 경우 defaultValue를 반환함

3. V put(K key, V value)

해당 맵에 전달된 키에 대응하는 값으로 특정 값을 매핑함.

4. V remove(Object key)

해당 맵에서 전달된 키에 대응하는 매핑을 제거함.

5. void clear()

해당 맵(map)의 모든 매핑(mapping)을 제거함.

6. boolean containsKey(Object key)

해당 맵이 전달된 키를 포함하고 있는지를 확인함. 
시간복잡도 O(1)을 가진다.

7. boolean containsValue(Object value)

해당 맵이 전달된 값에 해당하는 하나 이상의 키를 포함하고 있는지를 확인함.
전체 값을 조회해야 하기 때문에 O(N)의 시간복잡도를 가진다.

8. boolean isEmpty()

해당 맵이 비어있는지를 확인함.

9. Set keySet()

해당 맵에 포함되어 있는 모든 키로 만들어진 Set 객체를 반환함.

10. V replace(K key, V value)

해당 맵에서 전달된 키에 대응하는 값을 특정 값으로 대체함.

아마 이렇게 대표적으로 사용할 수 있을 것 같다.
~~벨로그 단점이.. table이 별로다 이게 필자에겐 최선인 점..~~

1. HashMap 객체 선언

import java.util.HashMap; // 반드시 import 해줘야 사용할 수 있다.

HashMap<String, String> hashMap = new HashMap<>();	
// <>제너릭 타입에는 카와 값이 받을 데이터 타입으로 명시해줘야 한다. 
// 또한 primitive type이 아닌 Wrapper 타입으로 명시해줘야 한다.

이렇게 선언하면 이제부터 hashMap 변수를 사용할 수 있는 것이다.

2. HashMap에 특정 데이터 삽입 및 조회

hashMap.put("파묘", "8.22") // 이렇게 키와 값으로 입력 데이터를 삽입할 수 있다.

hashMap.get("파묘") // 출력: "8.22" -> 이렇게 키값을 통해 Value값을 조회할 수 있다.
  
hashMap.getOrDefault("어벤져스", "0"); // 출력: 0 -> 
//어벤져스 키는 없기 때문에 디폴트인 0을 출력한다.

3. HashMap 전체 키 불러오기(키값은 Set형태로 가져온다)

for(String key : hashMap.keySet()) {
	hashMap.get(key); // 이렇게 전체 키값을 이용해, Value값을 가져올 수 있다. 
}

4. HashMap 안에 Key와 Value의 존재 유무 파악

hashMap.containsKey("파묘") 		// true
hashMap.containsKey("어벤져스") 	// false

hashMap.containsValue("8.22") 	// true
hashMap.containsValue("10") 	// false