[Java] HashSet이란?

📘 Set란?

Set은 JCF(Java Collection Framework)의 인터페이스 중 하나로 중복을 허용하지 않고 저장 순서를 보장하지 않는 경우가 많은 비선형 구조 인터페이스이고, 대표적인 구현체로 TreeSet, HashSet, LinkedHashSet이 있습니다.

---

📘 HashSet?

출처: https://www.tpointtech.com/hash-table

HashSet이란 해시 테이블을 이용하여 데이터를 저장하는 구현체로 Set의 특징을 가지고 있어 중복 값을 허용하지 않는 특징이 있습니다.

---

⚙️ HashSet 동작 원리

IntelliJ IDEA에서 HashSet 구조를 확인해보면 다음과 같이 내부적으로 HashMap을 이용하여 동작하는 것을 알 수 있습니다. 즉, HashSet은 데이터를 HashMap의 키(Key)로 저장하며, 값(Value)는 모두 같은 더미 객체를 사용하여 중복된 키(Key)를 허용하지 않는 Map의 특성을 이용하여 중복을 제거합니다.

❓ 그럼 HashSet은 어떤 원리로 중복을 제거할까?

---

hashCode(), equals()

자바에는 객체를 식별할 수 있는 hashCode가 있습니다. 다음과 같은 코드가 실행되면

set.add("apple");

내부적으로는 HashMap을 이용하여 아래와 같이 실행됩니다.

map.put("apple", PRESENT);

이 때, HashMap은 apple 객체의 hashCode()를 호출하고 해당 해시값에 기반하여 버킷 위치를 결정하고 해당 위치에 동일한 객체(equals()가 true인)가 없다면 추가합니다.

‼️ hashCode()와 equals()를 제대로 구현하지 않으면 중복이 제대로 처리되지 않아 HashSet의 중복 방지 기능이 무의미해질 수 있습니다.

이처럼 HashSet이 효율적으로 중복 처리를 할 수 있는 이유는 hashCode()를 이용하여 해시 기반 검색을 하여 탐색 범위를 좁히고 동일한 해시값을 가지는 객체가 있는 경우equals()로 정확한 중복 여부를 파악하기 때문입니다.