[Java] 컬렉션 프레임워크 - Set(HashSet, TreeSet)의 이해

2026.02.22 - [Java] - [Java] 컬렉션 프레임워크 - List(ArrayList, LinkedList)의 이해

[Java] 컬렉션 프레임워크 - List(ArrayList, LinkedList)의 이해

 

Set이란?

Set은 중복을 허용하지 않는 자료구조입니다. Collection의 인터페이스를 상속받는 인터페이스이며, 같은 값을 두 번 저장하려고 하면, 자동으로 하나만 저장됩니다. 또한 순서를 보장하지 않습니다. (일부 구현체는 순서를 유지합니다)

 

주로 데이터의 중복을 방지하고 특정 값의 존재 여부만 중요할 때, 빠른 검색이 필요할 때 사용 합니다.

가장 큰 특징은 평균 검색 속도가 O(1)로 최적화 돼있다는 점입니다. 이러한 성능은 내부적으로 해시 알고리즘(Hash Algorithm)을 사용하기 때문에 가능합니다. 

 

대표적인 구현체로는 HashSet, LinkedSet, TreeSet이 있으며 HashSet을 가장 많이 사용 합니다.

 

Hashset

HashSet은 중복을 허용하지 않고, 저장 순서도 보장하지 않습니다.

또한 평균 검색 속도는 O(1)이며 내부적으로 HashMap을 사용합니다. 실제 내부 구조는 다음과 같습니다. 

public class HashSet<E> {
    private transient HashMap<E,Object> map;
}

즉, HashSet은 자체적으로 모든 로직을 새로 구현한 것이 아니라, 이미 구현되어 있는 HashMap을 내부적으로 활용합니다.

그러면 자연스럽게 이런 의문이 생깁니다.

 

배열은 인덱스를 알고 있다면 바로 해당 위치로 접근할 수 있기 때문에 O(1)의 속도를 가집니다.

예를 들어 arr[3] 이처럼 인덱스를 알고 있다면 즉시 접근할 수 있습니다. 하지만 배열에서 데이터 3(특정 값)의 "검색"은 배열의 처음부터 끝까지 하나씩 비교해야 하므로 시간 복잡도는 O(n)입니다.

arr[3] -> O(1)

그렇다면 HashSet은 순서를 보장하지 않아, 인덱스를 활용할 수도 없는데 어떻게 평균 O(1)의 속도를 가질 수 있을까요? 그 이유는 바로 해시(Hash)입니다.

 

해시(Hash)란?

해시(Hash)는 어떤 데이터를 일정한 규칙에 따라 계산한 정수 값(해시 값)을 의미합니다.

보통 메서드 hashCode()를 통해 객체를 정수 값으로 변환하며, 이 때 반환되는 값이 바로 해시값(해시 코드)입니다.

여기서 hashCode() 메서드 자체가 해시 함수(해시 알고리즘)을 이용한 것 입니다.

 

앞에서 살펴봤듯이 배열은 인덱스를 알고 있다면 O(1)로 바로 접근할 수 있지만, 특정 값의 "검색" 은 이야기가 달라집니다. 

예를 들어 "배열 안에 값 3이 있는가?"를 구하려면 배열의 모든 요소를 하나씩 비교해야 하므로 O(n)의 속도를 가집니다.

 

그렇다면 만약 아래의 코드 처럼 데이터를 찾을 때도 인덱스를 활용할 수 있다면 어떨까요?

데이터의 값을 배열의 인덱스로 그대로 사용한다면 O(n)의 속도는 O(1)로 될 것입니다.

arr[3] = 3;
arr[1000] = 1000;

하지만 문제는 우리가 저장하려는 값은 단 2개뿐인데, 인덱스 1,000의 배열을 만들어서 활용한다면 심각 메모리 낭비가 발생할 것입니다. 또한 데이터는 항상 숫자만 있는 것이 아니라, 문자열, 객체 등도 있으므로 이러한 값들은 배열의 인덱스로 직접 사용할 수 없습니다. 그래서 이러한 문제를 해결하는 것이 바로 해시 알고리즘이며, 해시 알고리즘을 통해 해시를 구할 수 있습니다.

 

해시 알고리즘(Hash Algorithm)

해시 알고리즘은 임의의 데이터를 정수 형태의 해시값으로 변환하는 계산 규칙 입니다.

자바에서는 hashCode()각 이 역할을 하며, 해시 값을 구하는 흐름은 아래와 같습니다.

데이터 → hashCode() → 해시값(int)

전체적인 흐름을 정리하자면, 아래와 같습니다.

데이터 → hashCode()(해시 알고리즘) → 해시 값(int) → 배열 길이에 맞게 계산 -> 해시 인덱스 -> 배열 인덱스

아래 예시 해시 함수를 보겠습니다. 이 연산을 이용하면 항상 배열 크기 범위 안의 숫자가 나오게 됩니다.

이렇게 구한 해시 값을 그대로 배열의 인덱스로 이용합니다. 아래 이미지도 같이 보겠습니다

해시 인덱스 = 데이터 값 % 배열의 크기

 

이 때 데이터를 저장하는 배열을 해시 테이블(Hash Table)이라고 합니다. 그런데 여기서도 한 가지 의문이 생깁니다. 만약에 데이터 를 13도 추가를 한다고 하면, 서로 다른 두 데이터(3, 13)이 같은 인덱스 3에 저장될 것 입니다.

 

이처럼 서로 다른 데이터가 동일한 해시 값을 가지는 현상을 해시 충돌(Hash Collision)이라고 합니다. 해시 테이블은 빠른 검색을 가능하게 해주지만, 이 충돌 문제를 해결해야만 제대로 동작할 수 있습니다.

 

그러면 우선 해시 테이블에 대해서 먼저 알아보겠습니다.

 

해시 테이블(Hash Table)

해시 테이블은 해시 알고리즘을 이용해 데이터를 효율적으로 저장하고 검색하기 위한 자료 구조입니다.

해시 함수를 통해 계산된 해시 인덱스를 배열의 인덱스를 활용하기 때문에 평균 시간 복잡도는 O(1)입니다. 

 

또한 해시 테이블은 내부적으로 배열을 사용 하는데, 여기서 단순한 배열이 아닌 배열, 노드, 연결 구조를 사용하는 구조를 가집니다. 이러한 구조를 사용하는 이유는 바로 해시 충돌을 처리하기 위해서입니다

 

그러면 해시 테이블의 내부 구조에 대해서 먼저 알아보겠습니다.

 

해시 테이블 내부 구조

우선 해시 테이블의 크기가 10이라고 가정한다면  0 ~9번까지의 인덱스가 존재 하고 배열의 모든 값은 null 입니다.

이 배열의 각 칸을 버킷(Bucket)이라고 부릅니다. 즉 배열의 크기가 10이니 버킷도 10개이며, 서로 연결되어 있지 않은 각각 독립적인 공간입니다.

 

데이터 저장 과정

이제 첫 번째 데이터 3을 저장 한다고 가정 하겠습니다. 해시 함수를 통해 해시 값이 3이 나왔고, 따라서 3번 버킷에 저장됩니다.

현재 3번 버킷은 비어 있으므로 Node 객체 하나가 생성되어 해당 버킷에 저장 됩니다.

 

여기서 중요한 점은 아직 연결리스트는 만들어지지 않았으며, Node 하나만 저장된다는 것입니다.

즉 버킷 한 칸에 데이터 3을 담고 있는 Node 객체 하나가 들어 있는 상태입니다.

*Node는 데이터를 저장하기 위한 객체 단위로, Key, Value(더미), Next(다음 노드를 가리키는 참조)의 정보를 가집니다.

 

그렇다면 연결 리스트는 언제 사용할까요? 바로 해시 충돌이 발생하는 경우 사용 합니다.

 

해시 충돌(Hash Collision)

해시 충돌은 서로 다른 데이터가 동일한 해시 값을 가지는 현상을 의미 합니다. 

 

우리는 현재 3번 버킷에 Node 한 개를 저장했습니다. 이제 두 번째 데이터 13을 추가해보겠습니다. 해시 함수를 적용하여 동일하게 13의 해시 값은 동일하게 3이 나왔다고 가정해보면, 데이터 13 역시 같은 3번 버킷에 저장이 됩니다. 하지만 이미 3번 버킷에는 데이터 3이 저장되어 있습니다. 

 

배열 하나의 공간에는 하나의 값만 저장할 수 있기 때문에, 배열 안에 또 다른 저장 구조가 필요합니다. 이때 사용하는 방식이 바로 연결 리스트(체이닝 방식)입니다. 연결 리스트는 새로운 Node를 생성하고, 기존 Node의 next가 새 Node를 참조하도록 연결 합니다.

*value의 PRESENT는 더미(의미 없는 값)이며, 순서가 중요하지 않고 메모리 절약을 위해 단일 연결 리스트를 이용니다.

 

즉 해시 충돌이 발생하기 전에는 단일 Node만 존재하지만, 해시 충돌이 발생하는 순간부터 연결 리스트 구조가 형성 됩니다.

따라서 각 버킷은 연결 리스트의 시작점(head)이 됩니다.

 

해시 함수는 무한한 데이터를 유한한 배열 크기로 압축하기 때문에 해시 충돌은 낮은 확률로라도 반드시 발생합니다. 따라서 해시 충돌은 완전히 피할 수 없기에, 해시 테이블은 충돌을 없애는 것이 아니라 충돌이 발생했을 때 효율적으로 처리하는 구조입니다. 

 

HashSet은 중복을 허용하지 않기 때문에, 저장하기 전 contains()를 통해 같은 값이 있는지 확인합니다. 연결리스트에서의 contains()는 모든 노드를 순회해야 하므로 O(n)입니다. 

 

하지만, 해시 충돌이 거의 없다면 사실상 O(1)이고 해시 테이블은 확률적으로 데이터를 넓게 분산시키기 때문에 평균적으로 O(1)에 가까운 매우 빠른 성능을 제공합니다.

 

HashCode()와 equals() 재정의

객체를 직접 만들어 사용하는 경우, hashCode()와 equals()는 반드시 함께 재정의 해야 합니다. String, Integer Long 등 같은 자바 기본 제공 클래스들은 이미 equals()와 hashCode()가 올바르게 재정의 돼있어, 그대로 사용하면 됩니다.

 

하지만 사용자 정의 객체를 HashSet의 요소나 HashMap의 Key로 사용한다면 반드시 재정의 해야 합니다. 

그 이유는 자바에서 모든 클래스는 기본적으로 Object의 hashVode()와 equals()를 상속 받으며, 두 메서드들의 기본 구현 방식 때문입니다.

 Object의 equals()

Object의 equals()는 두 객체의 참조값이 같은지 비교합니다. 예를 들어 두 객체는 이름은 같지만 서로 다른 참조값을 가집니다.

Person p1 = new Person("Lee");
Person p2 = new Person("Lee");

따라서 아래와 같은 결과가 나옵니다.

p1.equals(p2) → false

즉 기본 equals()는 논리적 동일성이 아닌, 물리적 동일성(같은 객체)인지만 비교 합니다. 기본형은?

 

 

 Object의 hashCode()

object의 기본 hashCode()는 객체의 메모리 주소 기반 값을 반환합니다. 즉, 서로 다른 객체라면, 데이터 값이 같아도 대부분 다른 해시값이 나옵니다.

p1.hashCode() != p2.hashCode()

 

저희는 보통 이름이 같으면 같은 사람으로 취급 합니다. 하지만 Object의 기본 구현을 그대로 사용하면 equals()는 false, hashCode()또한 다르게 나와 문제가 발생합니다. 

즉, 같은 데이터 값을 갖고 있는 서로 다른 두 객체는 서로 다른 버킷에 들어가거나 같은 버킷에 들어가더라도 equals()가 false()가 되어 다른 객체로 취급됩니다. 

 

자바에서 모든 클래스는 기본적으로 Object의 hashCode()와 equals()를 상속 받습니다. 따라서 우리가 재정의 하지 않으면, Object의 hashCode()와 euqlas()를 그대로 사용하게 됩니다.

 

equals()는 논리적으로 같은 객체인지 판별하기 위한 메서드이고, hashCode()는 같은 버킷인지를 판별하기 위한 메서드입니다.

문제는 여기서 발생합니다.

 

hashCode()와 equals() 정리

HashMap과 HashSet은 객체를 비교할 때 두 단계를 거칩니다.

1. hashCode()로 같은 버킷인지 확인
2. 같은 버킷 안에서 equals()로 실제 동일 객체인지 비교

 

즉 hashCode()는 빠르게 범위를 좁히는 역할, equals()는 정말 같은 객체인지 확인하는 역할을 합니다.

해시 기반 컬렉션이 빠른 이유는, 모든 객체를 비교하지 않고 해시값으로 후보를 줄이기 때문입니다.

 

그리고 자바에서는 다음 규칙이 반드시 성립해야 합니다.

equals()가 true라면 hashCode()도 반드시 같아야 한다. 
하지만 hashCode()가 같다고 해서 equals()가 true()일 필요는 없다.

 이 규칙이 깨지면 HashSet과 HashMap은 정상적으로 동작하지 않습니다.

 

HashMap

HashMap은 Key-Value 형태로 데이터를 저장하는 자료구조입니다. 여기서 각 Key는 고유해야 하며, 동일한 Key는 한 번만 존재할 수 있습니다.

 

위에서 HashSet은 값을 하나만 저장하는 구조라고 했습니다. 그렇다면 왜 내부적으로는 Key와 Value를 함께 저장하는 HashMap을 사용할까요? 그 이유는 바로 Map의 핵심 특성 때문입니다.

 

Set에 저장 되는 값을 Map의 Key로 할용하면 Map이 제공하는 Key 중복 금지 특성을 그대로 사용할 수 있습니다.

즉, 굳이 중복 검사 로직을 새로 만들 필요 없이 HashMap의 구조를 그대로 활용하면 됩니다.

 

그래서 HashSet은 내부적으로 다음과 같이 동작 합니다.

set.add("apple");
↓ 내부 동작
map.put("apple", PRESENT);

여기서 PRESENT는 의미 없는 더미로 HashSet에서는 Value가 중요하지 않기 때문에 단순히 자리 채우는 용도로만 사용 됩니다.

 

HashMap은 우리가 앞에서 설명한 해시 테이블 구조를 그대로 사용하는 자바의 구현체입니다.

그렇다면 HashMap과 HashTable의 차이는 뭘까요?

HashMap vs Hash Table

둘 다 해시 테이블 기반의 Key-Value, 자료 구조이지만, 설계 목적과 사용 환경에서 차이가 있습니다.

 

먼저 HashTable은 모든 주요 메서드에 synchronized가 적용되어 있어, 멀티스레드 환경에 안전하지만 이 동기화 과정때문에 한 번에 하나의 스레드만 접근할 수 있어 성능은 상대적으로 느립니다. 또한 null key/value를 허용하지 않습니다.

 

반면 HashMap은 동기화를 지원하지 않아 단일 스레드 환경에 적합하고, 그 만큼 더 빠른 성능을 제공합니다. 또한 1개의 null key를 허용합니다. 1개만 허용하는 이유는 Map은 key의 중복을 허용하지 않는데, null 또한 하나의 key로 취급되기 때문입니다.

 

 

---

LinkedHashSet

LinkedHashSet은 HashSet과 마찬가지로 중복을 허용하지 않지만, 입력 순서를 유지한다는 차이가 있습니다. 내부적으로는

HashMap을 사용함으로써 데이터의 유일성을 보장하고, 평균 O(1)의 성능을 가지며 이중 연결 리스트 구조로 삽입된 순서(order)를 기억합니다.

 

이는 해시 충돌과 무관하게, 오로지 삽입 순서를 유지하기 위함이며, HashSet과 다르게 이중 연결 리스트 구조를 사용하는 이유는 입력 순서 유지를 위해서는 앞/뒤 노드 정보를 알아야 하기 때문입니다.

 

즉 LinkedHashSet은 HashSet의 기능을 그대로 활용하면서 순서를 유지하기 위해 연결 리스트만 추가한 형태입니다. 연결 리스트가 추가 되기에 HashSet보다는 조금 더 무겁습니다.

---

TreeSet

TreeSet은 중복을 허용하지 않으면서, 데이터를 자동으로 정렬해주는 Set입니다. 앞의 HashSet과 LinkedHashSet이 해시 기반이었다면, TreeSet은 트리(Tree) 기반으로 동작합니다.

 

내부적으로는 Red-Black Tree(균형 이진 탐색 트리)구조를 사용하며, 데이터가 저장될 때마다 오름차순을 기준으로 정렬 상태를 유지합니다. 주요 연산들은 평균 O(log n)입니다.

 

Tree 내부 구조

TreeSet이 사용하는 트리 구조는 이진 탐색 트리(Binary Search Tree)기반입니다. 이 구조의 핵심 규칙은 현재 노드보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다는 것입니다. 이 규칙이 모든 노드에 대해 재귀적으로 적용되면서 트리가 구성됩니다.

 

여기서 핵심은 입력 순서가 아닌, 데이터의 값을 기준으로 정렬해서 보관한다는 점이며 따라서 정렬된 순서로 데이터를 차례대로 조회할 수 있습니다.

 

예를 들어 다음 숫자를 순서대로 삽입한다고 가정 하겠습니다.

50 → 30 → 70 → 20 → 40 → 60 → 80

 

그렇다면 트리는 이렇게 구성 됩니다. 여기서, 가장 높은 조상을 루트(root)라고 하며, 부모 노드와 자식 노드로 이루어집니다.

그렇다면 왜 이렇게 저장할까요? 이 구조의 목적은 검색 속도를 빠르게 하기 위함입니다.

예를 들어 60을 찾는 과정을 알아보겠습니다.

1. 50과 비교, 60이 더 큼 => 오른쪽으로 이동
2. 70과 비교, 60이 더 작음 => 왼쪽으로 이동
3. 60 발견

이 과정에서 모든 노드를 탐색하지 않고, 비교할 때마다 탐색 범위가 절반씩 줄어듭니다. 이러한 원리로 탐색할 때마다 선택지가 절반으로 줄어들기 때문에 평균적으로 O(log n)의 시간 복잡도를 가져, 항상 정렬된 상태를 유지하면서도 비교적 효율적인 성능을 제공합니다.

 

그런데 만약 데이터를 다음과 같이 삽입하면 어떻게 될까요?

10 → 20 → 30 → 40 → 50

 

그러면 트리는 아래와 같이 구성될 것입니다. 

이 경우 검색 성능은 O(log n)이 아닌 O(n)이 될것입니다. 즉 이진 탐색 트리는 데이터 입력 순서에 따라 한쪽으로 치우치는(skewed) 문제가 발생할 수 있습니다.

 

Red-Black Tree(자가 균형 이진 탐색 트리)

Red-Black Tree란 이진 탐색 트리의 성질을 유지하면서, 트리의 균형을 자동으로 맞추는 자료 구조입니다.

즉, 트리의 높이를 항상 O(log n) 수준으로 유지하여 주요 연산을 O(log n)으로 보장하는 것이 목적입니다.

 

핵심 특징으로는 각 노드는 빨강 또는 검정색을 가지며 특정 규칙을 만족하도록 삽입 / 삭제 시 자동으로 재정렬 한다는 점입니다.

이러한 규칙 덕분에 트리는 항상 일정한 균형을 유지하게 됩니다.

 

예시 이미지를 보겠습니다.