[알고리즘] 18. 해시맵(HashMap)

[알고리즘] 18. 해시맵(HashMap)

지난 글에서는 덱(Deque)에 대해 정리했습니다. 이번 글에서는 알고리즘 문제에서 정말 자주 사용하는 자료구조인 해시맵(HashMap)에 대해 알아보겠습니다.

HashMap은 데이터를 key와 value 형태로 저장하는 자료구조입니다. 값을 빠르게 찾거나, 등장 횟수를 세거나, 특정 데이터에 연결된 정보를 저장할 때 자주 사용됩니다.

HashMap은 key를 이용해 value를 빠르게 저장하고 찾는 자료구조입니다.

---

1. HashMap이란?

HashMap은 데이터를 쌍으로 저장합니다. 하나의 데이터는 key와 value로 이루어져 있습니다.

구분	의미	예시
key	값을 찾기 위한 기준	이름, 번호, 단어
value	key에 연결된 값	점수, 개수, 정보

예를 들어 학생 이름과 점수를 저장한다고 생각해보겠습니다.

Kim → 90
Lee → 85
Park → 95

여기서 Kim, Lee, Park은 key이고, 90, 85, 95는 value입니다.

HashMap은 key를 넣으면 그 key에 연결된 value를 빠르게 찾을 수 있습니다.

---

2. HashMap이 필요한 상황

알고리즘 문제에서는 단순 배열만으로 처리하기 어려운 상황이 자주 나옵니다. 이때 HashMap을 사용하면 훨씬 쉽게 해결할 수 있습니다.

• 특정 값이 존재하는지 빠르게 확인해야 할 때
• 값의 등장 횟수를 세어야 할 때
• 문자열이나 단어를 기준으로 값을 저장해야 할 때
• 번호와 이름처럼 서로 연결된 정보를 저장해야 할 때
• 값의 범위가 너무 커서 카운팅 배열을 쓰기 어려울 때
• 중복 여부나 빈도수를 빠르게 확인해야 할 때

특히 값의 범위가 크거나, 문자열을 key로 사용해야 하는 문제에서는 HashMap이 매우 유용합니다.

---

3. Java에서 HashMap 사용하기

Java에서 HashMap을 사용하려면 먼저 import가 필요합니다.

import java.util.HashMap;

기본 사용 형태는 다음과 같습니다.

HashMap<String, Integer> map = new HashMap<>();

위 코드는 key는 String, value는 Integer인 HashMap을 만든 것입니다.

코드	의미
String	key의 타입
Integer	value의 타입

즉 문자열 key에 정수 value를 연결해서 저장할 수 있습니다.

---

4. put()으로 값 저장하기

HashMap에 값을 저장할 때는 put()을 사용합니다.

import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>();

map.put("Kim", 90);
map.put("Lee", 85);
map.put("Park", 95);

System.out.println(map);

출력 결과는 순서가 다를 수 있지만, 내용은 다음과 비슷합니다.

{Lee=85, Kim=90, Park=95}

HashMap은 입력한 순서를 보장하지 않습니다. 따라서 출력 순서가 달라도 key와 value가 제대로 저장되어 있으면 정상입니다.

HashMap은 저장 순서보다 key로 빠르게 찾는 것이 중요한 자료구조입니다.

---

5. get()으로 값 가져오기

HashMap에서 특정 key에 연결된 value를 가져올 때는 get()을 사용합니다.

HashMap<String, Integer> map = new HashMap<>();

map.put("Kim", 90);
map.put("Lee", 85);
map.put("Park", 95);

System.out.println(map.get("Kim"));
System.out.println(map.get("Park"));

출력 결과는 다음과 같습니다.

90
95

"Kim"이라는 key를 넣으면 90이라는 value를 가져오고, "Park"이라는 key를 넣으면 95라는 value를 가져옵니다.

---

6. 없는 key를 get()하면 어떻게 될까요?

HashMap에서 존재하지 않는 key를 get()하면 null이 반환됩니다.

HashMap<String, Integer> map = new HashMap<>();

map.put("Kim", 90);

System.out.println(map.get("Lee"));

출력 결과는 다음과 같습니다.

null

없는 key를 바로 사용하려고 하면 오류가 날 수 있으므로 주의해야 합니다.

Integer score = map.get("Lee");

if (score != null) {
    System.out.println(score);
} else {
    System.out.println("점수가 없습니다.");
}

HashMap에서 없는 key를 조회하면 null이 나올 수 있습니다.

---

7. containsKey()로 key 존재 여부 확인하기

특정 key가 HashMap에 존재하는지 확인할 때는 containsKey()를 사용합니다.

HashMap<String, Integer> map = new HashMap<>();

map.put("Kim", 90);
map.put("Lee", 85);

System.out.println(map.containsKey("Kim"));
System.out.println(map.containsKey("Park"));

출력 결과는 다음과 같습니다.

true
false

"Kim"은 존재하므로 true, "Park"은 존재하지 않으므로 false가 출력됩니다.

알고리즘 문제에서는 이미 등장한 값인지 확인할 때 containsKey()를 자주 사용합니다.

---

8. getOrDefault() 사용하기

HashMap으로 빈도수를 계산할 때 가장 자주 사용하는 메서드가 getOrDefault()입니다.

map.getOrDefault(key, 기본값)

key가 존재하면 기존 value를 가져오고, key가 없으면 지정한 기본값을 사용합니다.

HashMap<String, Integer> map = new HashMap<>();

System.out.println(map.getOrDefault("apple", 0));

출력 결과는 다음과 같습니다.

0

아직 "apple"이라는 key가 없기 때문에 기본값 0이 반환됩니다.

getOrDefault()는 없는 key를 안전하게 처리할 때 유용합니다.

---

9. HashMap으로 빈도수 계산하기

HashMap은 값이 몇 번 등장했는지 세는 빈도수 계산에서 매우 자주 사용됩니다.

다음 배열에서 각 숫자가 몇 번 등장했는지 세어보겠습니다.

import java.util.HashMap;

int[] numbers = {10, 20, 10, 30, 20, 10};

HashMap<Integer, Integer> map = new HashMap<>();

for (int num : numbers) {
    map.put(num, map.getOrDefault(num, 0) + 1);
}

System.out.println(map);

출력 결과는 순서가 다를 수 있지만, 내용은 다음과 같습니다.

{20=2, 10=3, 30=1}

10은 3번, 20은 2번, 30은 1번 등장했습니다.

여기서 핵심 코드는 아래 한 줄입니다.

map.put(num, map.getOrDefault(num, 0) + 1);

기존 횟수가 있으면 가져와서 1을 더하고, 처음 등장한 값이면 0에서 시작해 1로 저장합니다.

---

10. 단어 빈도수 계산하기

HashMap은 문자열을 key로 사용할 수 있기 때문에 단어 빈도수 계산에도 잘 어울립니다.

import java.util.HashMap;

String sentence = "java spring java sql spring java";

String[] words = sentence.split(" ");

HashMap<String, Integer> map = new HashMap<>();

for (String word : words) {
    map.put(word, map.getOrDefault(word, 0) + 1);
}

System.out.println(map);

출력 결과는 다음과 비슷합니다.

{spring=2, java=3, sql=1}

java는 3번, spring은 2번, sql은 1번 등장했습니다.

문자열을 기준으로 횟수를 세어야 한다면 HashMap을 먼저 떠올리면 좋습니다.

---

11. entrySet()으로 전체 순회하기

HashMap에 저장된 모든 key와 value를 확인하려면 entrySet()을 사용할 수 있습니다.

import java.util.HashMap;
import java.util.Map;

HashMap<String, Integer> map = new HashMap<>();

map.put("Kim", 90);
map.put("Lee", 85);
map.put("Park", 95);

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String name = entry.getKey();
    int score = entry.getValue();

    System.out.println(name + ": " + score);
}

출력 순서는 달라질 수 있지만, 저장된 key와 value를 모두 확인할 수 있습니다.

Lee: 85
Kim: 90
Park: 95

HashMap 전체를 돌면서 최댓값, 최빈값, 조건에 맞는 값을 찾을 때 entrySet()을 자주 사용합니다.

---

12. 가장 많이 등장한 값 찾기

빈도수를 계산한 뒤 가장 많이 등장한 값을 찾아보겠습니다.

import java.util.HashMap;
import java.util.Map;

int[] numbers = {10, 20, 10, 30, 20, 10};

HashMap<Integer, Integer> map = new HashMap<>();

for (int num : numbers) {
    map.put(num, map.getOrDefault(num, 0) + 1);
}

int maxNumber = 0;
int maxCount = 0;

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    int number = entry.getKey();
    int count = entry.getValue();

    if (count > maxCount) {
        maxCount = count;
        maxNumber = number;
    }
}

System.out.println("가장 많이 나온 숫자: " + maxNumber);
System.out.println("등장 횟수: " + maxCount);

출력 결과는 다음과 같습니다.

가장 많이 나온 숫자: 10
등장 횟수: 3

HashMap에서는 key가 실제 값이고, value가 등장 횟수입니다. 이 둘을 헷갈리지 않는 것이 중요합니다.

---

13. remove()로 값 삭제하기

HashMap에서 특정 key를 삭제할 때는 remove()를 사용합니다.

HashMap<String, Integer> map = new HashMap<>();

map.put("Kim", 90);
map.put("Lee", 85);

map.remove("Kim");

System.out.println(map);

출력 결과는 다음과 같습니다.

{Lee=85}

"Kim"이라는 key와 그에 연결된 value가 함께 삭제됩니다.

---

14. size()와 isEmpty()

HashMap에 몇 개의 key가 저장되어 있는지 확인할 때는 size()를 사용합니다. 비어 있는지 확인할 때는 isEmpty()를 사용합니다.

HashMap<String, Integer> map = new HashMap<>();

System.out.println(map.isEmpty());

map.put("Kim", 90);
map.put("Lee", 85);

System.out.println(map.size());
System.out.println(map.isEmpty());

출력 결과는 다음과 같습니다.

true
2
false

처음에는 비어 있으므로 true, 두 값을 넣은 뒤에는 크기가 2이고 비어 있지 않으므로 false가 출력됩니다.

---

15. HashMap과 카운팅 배열 비교

빈도수 계산에서는 HashMap과 카운팅 배열 중 어떤 것을 사용할지 고민할 때가 많습니다.

구분	카운팅 배열	HashMap
사용 조건	값의 범위가 작고 명확함	값의 범위가 크거나 다양함
key 역할	배열 인덱스	직접 저장한 key
문자열 key	사용 어려움	사용 가능
예시	1~100 점수 개수	단어별 등장 횟수

값의 범위가 작으면 카운팅 배열이 단순하고 빠릅니다. 하지만 값의 범위가 크거나 문자열을 다룬다면 HashMap이 더 적합합니다.

범위가 작으면 카운팅 배열, 범위가 크거나 key가 다양하면 HashMap을 고려합니다.

---

16. HashMap의 시간복잡도

HashMap은 key를 이용해 값을 빠르게 찾을 수 있습니다. 일반적으로 주요 연산은 평균적으로 O(1)에 가깝게 동작한다고 생각할 수 있습니다.

연산	평균 시간복잡도
put()	O(1)
get()	O(1)
containsKey()	O(1)
remove()	O(1)

물론 내부 충돌 상황 등에 따라 항상 완벽히 O(1)이라고만 볼 수는 없지만, 알고리즘 문제에서는 보통 평균 O(1) 자료구조로 사용합니다.

입력 N개를 한 번 순회하며 HashMap에 저장한다면 전체 시간복잡도는 보통 O(N)입니다.

---

17. HashMap에서 자주 하는 실수

HashMap을 사용할 때는 아래 실수를 조심해야 합니다.

• 없는 key를 get()한 뒤 null 처리를 하지 않는 경우
• key와 value의 의미를 반대로 생각하는 경우
• getOrDefault()의 기본값을 잘못 설정하는 경우
• HashMap 출력 순서가 입력 순서와 같다고 생각하는 경우
• 중복 key에 put()하면 기존 value가 덮어써진다는 점을 잊는 경우
• entrySet()에서 getKey()와 getValue()를 헷갈리는 경우

특히 같은 key에 다시 put()을 하면 기존 값이 새 값으로 바뀝니다.

HashMap<String, Integer> map = new HashMap<>();

map.put("Kim", 90);
map.put("Kim", 100);

System.out.println(map.get("Kim"));

출력 결과는 다음과 같습니다.

100

"Kim"이라는 key가 이미 있었기 때문에 90이 100으로 덮어써졌습니다.

HashMap에서 key는 중복될 수 없고, 같은 key에 put()하면 value가 갱신됩니다.

---

18. 정리

이번 글에서는 HashMap에 대해 정리했습니다.

• HashMap은 key와 value 형태로 데이터를 저장한다.
• put()으로 값을 저장하고, get()으로 값을 가져온다.
• containsKey()로 key 존재 여부를 확인할 수 있다.
• getOrDefault()는 빈도수 계산에서 자주 사용된다.
• HashMap은 문자열, 숫자 등 다양한 값을 key로 사용할 수 있다.
• entrySet()을 사용하면 key와 value를 함께 순회할 수 있다.
• 같은 key에 put()하면 기존 value가 덮어써진다.
• HashMap은 평균적으로 빠른 검색과 저장이 가능하다.

HashMap은 알고리즘 문제에서 정말 많이 사용되는 자료구조입니다. 특히 “빠르게 찾기”, “몇 번 나왔는지 세기”, “값과 정보를 연결하기” 같은 상황에서 매우 강력합니다.

HashMap의 핵심은 key를 기준으로 value를 빠르게 저장하고 찾는 것입니다.

---

다음 글 예고

다음 글에서는 해시셋(HashSet)에 대해 알아보겠습니다.

중복 없는 값 저장, contains를 이용한 빠른 존재 확인, HashMap과 HashSet의 차이까지 예제로 정리해보겠습니

다.