HashMap<K, V> 정리 - 사용법, 연산속도

📌 1. 해시맵(HashMap)이란?

HashMap<K, V>은 키(Key)와 값(Value)의 쌍을 저장하는 자료구조
✔ 배열(Array) 처럼 인덱스를 이용해 데이터를 찾는 것이 아니라, **키(Key)**를 이용해 값을 찾음.
✔ 내부적으로 해시 테이블(Hash Table) 구조를 사용하여 빠르게 데이터 검색이 가능.
✔ O(1)(평균적인 경우)의 시간복잡도로 데이터 추가, 삭제, 조회 가능.
✔ 중복 키 없음 (같은 키를 넣으면 마지막 값으로 덮어쓰기 됨).

 

Map<String, Object> dodoMap = new HashMap<>();

 

 

📌 2. 해시맵의 자료구조 (해시 테이블)

🔹 내부 동작 원리

• 해시 함수(Hash Function) 를 사용하여 **키(Key)**를 해시값(해시코드)로 변환 → 배열의 인덱스로 저장.
• 데이터 저장 시 put(K key, V value) 사용하면,
  1️⃣ 키를 해시 함수로 변환해 배열 인덱스를 찾고
  2️⃣ 해당 위치에 데이터를 저장함.
• 데이터 검색 시 get(K key) 호출하면,
  1️⃣ 키를 다시 해시 함수로 변환하여 배열 인덱스를 찾고
  2️⃣ 해당 위치에서 값을 빠르게 찾아 반환.

💡 즉, 배열처럼 직접 접근하므로 검색 속도가 빠름! (O(1)) - 시간복잡도에서 상수시간. 입력의 크기와 관계없이 일정한 시간 걸림.

🔹 충돌(Collision) 문제

• 다른 키가 같은 해시코드로 변환되면 충돌(Collision) 발생
• 이를 해결하기 위해 체이닝(Chaining) 기법(배열 안에 LinkedList 사용) 또는 오픈 어드레싱(Open Addressing) 기법 사용.

3. HashMap vs 다른 자료구조 비교

자료구조특징시간복잡도 (검색, 추가, 삭제)중복 허용

ArrayList	순차적인 데이터 저장, 인덱스로 접근 가능	O(1) (검색-인덱스), O(n) (검색-값)	O
LinkedList	순차적인 데이터 저장, 삽입/삭제 빠름	O(n) (검색), O(1) (삽입/삭제)	O
HashMap	키-값 저장, 빠른 검색	O(1) (검색, 추가, 삭제)	키 중복 ❌
TreeMap	정렬된 키 저장, O(log n) 성능	O(log n) (검색, 추가, 삭제)	키 중복 ❌
HashSet	중복 없는 값 저장, 순서 없음	O(1) (검색, 추가, 삭제)	값 중복 ❌

 

 

단어갯수구하기

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

public class WordCounter {
    public static void main(String[] args) {
        String text = "hello world hello java java java";
        String[] words = text.split(" ");

        Map<String, Integer> wordCount = new HashMap<>();

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

        System.out.println(wordCount);
    }
}

 

✔ 주요 로직: wordCount.getOrDefault(word, 0) + 1

• getOrDefault(word, 0) → 해당 단어가 존재하면 기존 개수 반환, 없으면 기본값 0 반환.
• +1 → 기존 개수에 1을 더해 단어 개수를 업데이트.
• put(word, new_count) → 새로운 값 저장.

 

 

 

 

📌 1. HashMap의 주요 연산과 시간 복잡도

연산평균 시간 복잡도최악의 경우 시간 복잡도

put(K key, V value) (삽입)	O(1)	O(n)
get(K key) (검색)	O(1)	O(n)
remove(K key) (삭제)	O(1)	O(n)
containsKey(K key) (키 존재 여부)	O(1)	O(n)
size() (크기 반환)	O(1)	O(1)
entrySet() (모든 키-값 조회)	O(n)	O(n)

💡 HashMap은 평균적으로 모든 연산이 O(1)!
💡 하지만 최악의 경우 O(n)도 가능함 → 충돌(Collision)이 많을 때!

 

for문 돌릴때 entrySet을 많이 사용하고있다....

 

 // ✅ for-each 문을 사용하여 리스트 안의 맵 탐색
        for (Map<String, String> map : list) {
            for (Map.Entry<String, String> entry : map.entrySet()) {
                System.out.println(entry.getKey() + " : " + entry.getValue());
            }

 

 

📌 2. HashMap 내부 동작과 시간 복잡도 분석

✔ 1) put(K key, V value) – 값 삽입

 

Map<String, Integer> map = new HashMap<>(); map.put("Alice", 90);

✔ 평균적으로 O(1)
✔ 해시 함수(Hash Function) 를 사용해 배열의 특정 위치(인덱스) 에 저장.
✔ 충돌이 없으면 즉시 저장 가능 → O(1)
✔ 하지만 충돌이 많으면 O(n) 까지 갈 수도 있음.

---

✔ 2) get(K key) – 값 검색

 

int score = map.get("Alice");

✔ 평균적으로 O(1)
✔ 해시 함수를 사용하여 바로 해당 위치의 값을 찾음
✔ 충돌이 많아 체이닝(Chaining)이 발생하면 O(n) 까지 가능.

---

✔ 3) remove(K key) – 값 삭제

map.remove("Alice");

✔ 평균적으로 O(1)
✔ 해시 함수로 해당 위치 찾고 즉시 삭제
✔ 하지만 충돌이 많으면 리스트에서 순차 탐색해야 하므로 O(n)

---

✔ 4) containsKey(K key) – 키 존재 여부 확인

 

map.containsKey("Alice");

✔ 평균적으로 O(1)
✔ get(K key)과 동일한 방식으로 동작
✔ 키를 찾기 위해 해시 함수를 사용 → O(1)
✔ 충돌이 많으면 리스트 탐색해야 하므로 최악의 경우 O(n)

---

✔ 5) entrySet() – 모든 키-값 조회

 

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

✔ 모든 데이터를 순회해야 하므로 O(n)
✔ 전체 데이터를 다 탐색해야 하므로 입력 크기 n에 비례
✔ 최악의 경우에도 O(n) (모든 원소를 한 번씩 확인해야 하니까)

---

📌 3. HashMap 충돌(Collision)이 발생하면?

💡 충돌(Collision) = 서로 다른 키가 같은 해시값을 가질 때
💡 해시 충돌이 발생하면 체이닝(Chaining) 기법을 사용해 LinkedList로 연결함.
💡 충돌이 많아지면 최악의 경우 O(n)이 될 수도 있음!

✔ 충돌이 없을 때 (이상적인 경우)

• put(), get(), remove() → O(1)

✔ 충돌이 많을 때 (최악의 경우)

• 여러 개의 키가 같은 해시값을 가지면 리스트를 순차 탐색해야 함 → O(n)

💡 하지만 보통 해시 충돌이 잘 관리되면 O(1)의 성능을 유지함.

---

📌 4. HashMap vs 다른 자료구조 비교

자료구조put()get()remove()특징

HashMap	O(1)	O(1)	O(1)	해시 기반, 빠른 검색
TreeMap	O(log n)	O(log n)	O(log n)	정렬된 맵 (이진 탐색 트리)
LinkedList	O(n)	O(n)	O(n)	순차 탐색 필요
ArrayList	O(1) (끝에 추가 시)	O(n)	O(n)	순차 접근
HashSet	O(1)	O(1)	O(1)	중복 없는 해시 기반 저장

💡 결론: 검색이 빠른 자료구조 필요하면 HashMap이 최고!

---

📌 5. HashMap을 사용할 때 주의할 점

1️⃣ 너무 많은 충돌 발생 시 성능 저하 → O(n)이 될 수도 있음!
2️⃣ 순서를 유지하지 않음 → LinkedHashMap 사용하면 해결 가능!
3️⃣ 멀티스레드 환경에서는 동기화 문제 발생 → ConcurrentHashMap 사용 필요!

---