[Java] HashMap과 HashSet

1. HashMap

📚 개념

HashMap은 Map 인터페이스의 구현체로 키(key)-값(value) 쌍으로 구성된 Entry 객체를 저장한다. 내부적으로 해시 함수를 통해 데이터를 저장할 위치(버킷)를 결정한다.

import java.util.HashMap;

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

// 다형성 적용
Map<Integer, String> map = new HashMap<>(); 

⭐️ 특징

• 하나의 키는 하나의 값만 가질 수 있다.
• 키는 중복될 수 없고, 값은 중복이 가능하다.
• 키에 null 값을 허용한다.
• 저장 순서를 보장하지 않는다.

⚙️ 내부 동작 원리

1️⃣ 데이터 추가시 ( put(key, value) )

1. 키의 hashCode()로 해시값을 계산한다.

2. 해시값을 기반으로 해당 키가 저장될 해시 버킷을 결정한다.

3. 해당 버킷에 이미 값이 있는 경우, 저장된 키와 equals()로 완전히 같은 객체인지 비교한다.

   • true 값이 반환되면, 중복된 요소라 판단하고 기존 값을 덮어쓴다.
   • false 값이 반환되면, 해시 충돌이 발생한다.

   

   이미지 출처 : https://en.wikipedia.org/wiki/Hash_collision

2️⃣ 해시 충돌(Collision)이 발생한 경우

• 기존 방식 (Java 7 이하) : 동일 버킷에 여러 개의 데이터를 연결리스트 형태로 저장하여 최악의 경우 성능이 O(n)까지 떨어진다.
• Java 8 이후 : 동일 버킷에 저장된 값이 8개 이상이고, 전체 해시 테이블의 크기가 64 이상일 때, 해당 버킷의 구조가 Red-Black Tree 구조로 전환되어 최악의 경우 성능이 O(log n)까지 개선된다.

❗️ HashMap이 키 중복을 제거하지 못하는 경우

• 추가하려는 키 객체(ex. 사용자 정의 객체)에 hashCode(), equals() 메서드를 오버라이딩 하지 않은 경우 완전히 같은 객체여도, 서로 다른 객체로 판단되어 중복이 허용될 수 있다.

➕ 주요 메서드

메서드	설명
put(K key, V value)	키-값 쌍 추가
get(Object key)	키에 해당하는 값 반환
remove(Object key)	키-값 쌍 제거
clear()	모든 키-값 쌍 제거
containsKey(Object key)	특정 키 존재 여부 확인
containsValue(Object value)	특정 값 존재 여부 확인
keySet()	키를 Set 형태로 반환
entrySet()	모든 키-값 쌍을 Set 형태로 반환
values()	값을 Collection 형태로 반환

---

2. HashSet

📚 개념

• HashSet은 Set 인터페이스의 구현 클래스로 Hash 함수를 이용하여 요소를 저장하며 중복을 허용하지 않는 집합(Set) 자료구조이다.

import java.util.HashSet;

HashSet<타입> hashSet = new HashSet<>(); 

// 다형성 적용
Set<타입> set = new HashSet<>(); 

⭐️ 특징

• 중복된 값을 허용하지 않는다.
• 데이터의 순서를 보장하지 않는다.
• null 값을 허용한다. (HashMap의 key에 null을 허용하기 때문)

⚙️ 내부 동작 방식

private transient HashMap<E,Object> map;	// 백업용 HashMap

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();	// 더미 객체

public HashSet() {
    map = new HashMap<>();
}
    

• Java에서의 HashSet 클래스는 내부적으로 HashMap을 기반으로 동작한다.
• HashSet의 내부 저장소로 백업용 HashMap을 사용한다.
• 요소는 map의 key로 저장되며, value는 모두 같은 더미 객체(PRESENT)를 사용한다.

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

• 즉, HashSet.add(x)는 내부적으로 map.put(x, PRESENT)와 동일하게 동작한다.

HashSet은 HashMap과 동일하게 hashCode(), equals() 메서드로 값의 중복을 판단한다.

➕ 주요 메서드

메서드	설명
add(E e)	요소를 추가. 이미 존재하면 추가 안 함, false 반환
remove(Object o)	요소를 제거. 존재했으면 true, 아니면 false 반환
contains(Object o)	요소가 포함되어 있는지 여부 확인
size()	현재 요소 개수 반환
clear()	모든 요소 제거
isEmpty()	비어 있는지 여부 확인
iterator()	요소 순회용 반복자 반환. fail-fast 동작
clone()	얕은 복사본 반환 (요소 자체는 복사하지 않음)
spliterator()	병렬 처리를 위한 분할 반복자 제공 (Java 8부터 지원)

---

정리

• HashMap은 키-값 구조의 데이터 저장이 필요할 때 사용한다.
• HashSet은 값의 중복을 제거한 집합이 필요할 때 사용한다.
• 두 자료구조 모두 해시 함수를 기반으로 하여, 평균적으로 O(1)의 성능을 보장한다.
• 해시 충돌 발생시 최악의 경우 성능이 O(n), Java 8 이후에는 O(log n)으로 떨어진다.

---

📃 참고 문서

• HashMap (Java Platform SE 8)
• HashSet (Java Platform SE 8)
• [JAVA] HashMap/ HashSet 에서 중복 없애기
• 해시셋과 해시맵의 이해: 자바 컬렉션 프레임워크의 핵심