자바 컬렉션 프레임워크: Set과 해시 알고리즘 이해하기

📚 학습 기록/Java 기초 & 중급

자바 컬렉션 프레임워크: Set과 해시 알고리즘 이해하기

zenjoydev 2025. 4. 16. 15:39

안녕하세요! 오늘은 자바 컬렉션 프레임워크의 중요한 부분인 Set과 해시 알고리즘에 대해 알아보겠습니다. List 컬렉션에 이어 Set 컬렉션의 특징과 내부적으로 사용되는 해시 알고리즘의 원리를 살펴보면서 효율적인 데이터 저장과 검색 방법에 대해 알아보겠습니다.

List vs Set: 근본적인 차이점

먼저 컬렉션 프레임워크의 두 가지 주요 인터페이스인 List와 Set의 차이점을 비교해보겠습니다.

List의 특징

순서 보장: 요소가 추가된 순서대로 저장됩니다.
중복 허용: 동일한 요소를 여러 번 저장할 수 있습니다.
인덱스 접근: 인덱스를 통해 특정 위치의 요소에 직접 접근할 수 있습니다.
사용 사례: 순서가 중요하거나 중복 요소가 필요한 경우 (예: 사용자 입력 기록, 명령 히스토리)

Set의 특징

유일성 보장: 중복 요소를 허용하지 않습니다.
순서 미보장: 요소의 저장 순서를 보장하지 않습니다(구현체에 따라 다를 수 있음).
빠른 검색: 요소의 존재 여부를 빠르게 확인할 수 있습니다.
사용 사례: 중복이 없는 고유한 데이터 집합이 필요한 경우 (예: 사용자 ID 목록, 방문한 URL 집합)

해시(Hash) 알고리즘이란?

해시 알고리즘은 데이터 값을 배열의 인덱스로 변환하여 저장하고 검색하는 기법입니다. 이를 통해 데이터의 검색 시간을 크게 단축할 수 있습니다.

해시 알고리즘의 기본 원리

해시 알고리즘의 기본 개념을 이해하기 위해 간단한 예제를 살펴보겠습니다:

public class HashStart1 {
    public static void main(String[] args) {
       Integer[] inputArray =  new Integer[4];
       inputArray[0] = 1;
       inputArray[1] = 2;
       inputArray[2] = 5;
       inputArray[3] = 8;

        System.out.println("inputArray = " + Arrays.toString(inputArray));
        int searchValue = 8;
        // 선형 검색: 4번의 비교 연산 필요
        for (Integer inputValue : inputArray) {
            if (inputValue == searchValue) {
                System.out.println(inputValue);
            }
        }
    }
}

위 코드에서는 배열에서 특정 값을 찾기 위해 모든 요소를 순회해야 합니다. 시간 복잡도는 O(n)으로, 배열 크기에 비례하여 검색 시간이 늘어납니다.

해시 인덱싱의 활용

이번에는 해시 개념을 활용해 값을 배열의 인덱스로 직접 사용해보겠습니다:

public class HashStart2 {
    public static void main(String[] args) {
       Integer[] inputArray =  new Integer[10];
       inputArray[1] = 1;  // 값이 1인 요소를 인덱스 1에 저장
       inputArray[2] = 2;  // 값이 2인 요소를 인덱스 2에 저장
       inputArray[5] = 5;  // 값이 5인 요소를 인덱스 5에 저장
       inputArray[8] = 8;  // 값이 8인 요소를 인덱스 8에 저장

        System.out.println("inputArray = " + Arrays.toString(inputArray));
        int searchValue = 8;
        // 값을 인덱스로 직접 사용하여 O(1) 시간에 접근
        Integer result = inputArray[searchValue];
        System.out.println("result = " + result);
    }
}

이 방식에서는 값 자체를 배열의 인덱스로 사용합니다. 따라서 검색 시 값을 바로 인덱스로 활용하여 시간 복잡도 O(1)로 데이터에 접근할 수 있습니다.

해시 함수와 나머지 연산

그러나 저장할 값이 배열의 크기보다 클 경우 문제가 발생합니다. 이를 해결하기 위해 나머지 연산을 사용한 해시 함수를 도입할 수 있습니다:

public class HashStart4 {
    static final int CAPACITY = 10;

    public static void main(String[] args) {
        System.out.println("hashIndex(1) = " + hashIndex(1));   // 1
        System.out.println("hashIndex(2) = " + hashIndex(2));   // 2
        System.out.println("hashIndex(5) = " + hashIndex(5));   // 5
        System.out.println("hashIndex(8) = " + hashIndex(8));   // 8
        System.out.println("hashIndex(14) = " + hashIndex(14)); // 4
        System.out.println("hashIndex(99) = " + hashIndex(99)); // 9

        Integer[] inputArray = new Integer[CAPACITY];

        add(inputArray, 1);
        add(inputArray, 2);
        add(inputArray, 5);
        add(inputArray, 8);
        add(inputArray, 14);
        add(inputArray, 99);

        System.out.println("inputArray = " + Arrays.toString(inputArray));

        int searchValue = 14;
        int hashIndex = hashIndex(searchValue);
        System.out.println("searchValue hashIndex = " + hashIndex);
        Integer result = inputArray[hashIndex];
        System.out.println(result);
    }

    private static void add(Integer[] inputArray, int value) {
        int hashIndex = hashIndex(value);
        inputArray[hashIndex] = value;
    }

    static int hashIndex(int value) {
        return value % CAPACITY;  // 나머지 연산을 통한 해시 인덱스 생성
    }
}

이 코드에서는 hashIndex 메서드를 통해 값을 배열의 인덱스 범위 내로 매핑합니다. 나머지 연산(%)을 사용하여 큰 값도 배열 크기 내의 인덱스로 변환합니다.

해시 충돌(Hash Collision)의 문제

나머지 연산을 사용한 해시 함수는 간단하지만 충돌 문제가 있습니다. 예를 들어, 14 % 10 = 4와 24 % 10 = 4처럼 서로 다른 값이 동일한 인덱스에 매핑될 수 있습니다. 이런 문제를 해시 충돌이라고 합니다.

위 예제에서는 충돌이 발생하면 이전 값이 새로운 값으로 덮어씌워지는 문제가 있습니다. 실제 HashSet 구현에서는 충돌을 해결하기 위한 다양한 기법(체이닝, 오픈 어드레싱 등)을 사용합니다.

간단한 HashSet 구현

이제 중복을 허용하지 않는 Set의 기본 개념을 담은 간단한 구현체를 살펴보겠습니다:

public class MyHashSetV0 {
    private int[] elementData = new int[10];
    private int size = 0;

    public boolean add(int value) {
        if (contains(value)) {
            return false;  // 이미 존재하는 값이면 추가하지 않음
        }
        elementData[size] = value;
        size++;
        return true;
    }

    public boolean contains(int value) {
        for (int i = 0; i < size; i++) {
            if (elementData[i] == value) {
                return true;
            }
        }
        return false;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSetV0{" +
                "elementData=" + Arrays.toString(elementData) +
                ", size=" + size +
                '}';
    }
}

이 구현은 해시 알고리즘을 사용하지 않고 선형 검색을 통해 중복 검사를 수행합니다. 따라서 contains 메서드의 시간 복잡도는 O(n)입니다.

public class MyHashSetV0Main {
    public static void main(String[] args) {
        MyHashSetV0 set = new MyHashSetV0();

        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        System.out.println("set = " + set);

        boolean result = set.add(4);  // 중복 값 추가 시도
        System.out.println("중복 데이터 저장 결과 = " + result);  // false 반환
        System.out.println("set = " + set);

        System.out.println("set.contains(3) = " + set.contains(3));    // true
        System.out.println("set.contains(99) = " + set.contains(99));  // false
    }
}

실행 결과:

set = MyHashSetV0{elementData=[1, 2, 3, 4, 0, 0, 0, 0, 0, 0], size=4}
중복 데이터 저장 결과 = false
set = MyHashSetV0{elementData=[1, 2, 3, 4, 0, 0, 0, 0, 0, 0], size=4}
set.contains(3) = true
set.contains(99) = false

해시 알고리즘의 주요 특징 정리

빠른 검색: 해시 함수를 통해 O(1) 시간 복잡도로 데이터 접근 가능
메모리 효율성: 값의 범위에 따라 추가 메모리가 필요할 수 있음
충돌 처리: 서로 다른 값이 동일한 인덱스에 매핑될 때 해결 방법 필요
해시 함수: 값을 인덱스로 변환하는 함수로, 고른 분포를 갖는 것이 이상적

자바 컬렉션에서의 활용

자바 컬렉션 프레임워크의 HashSet, HashMap, HashTable 등은 내부적으로 해시 알고리즘을 사용하여 효율적인 데이터 관리를 제공합니다. 특히 HashSet은 중복을 허용하지 않는 컬렉션으로, 요소의 존재 여부를 빠르게 확인할 수 있습니다.

import java.util.HashSet;

public class JavaHashSetExample {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple");  // 중복 값은 추가되지 않음
        
        System.out.println("Set size: " + set.size());  // 3
        System.out.println("Set contains Apple: " + set.contains("Apple"));  // true
        System.out.println("Set elements: " + set);  // [Apple, Cherry, Banana] (순서 보장 안됨)
    }
}

결론

해시 알고리즘은 대규모 데이터를 효율적으로 저장하고 검색하는 데 필수적인 기술입니다. 자바 컬렉션 프레임워크의 Set 구현체들은 이 알고리즘을 활용하여 빠른 검색과 중복 제거 기능을 제공합니다.

리스트가 순서와 인덱스가 중요한 상황에서 유용하다면, 세트는 요소의 유일성과 존재 여부 확인이 중요한 상황에서 효과적입니다. 각 자료구조의 특성을 이해하고 상황에 맞게 활용하는 것이 효율적인 프로그래밍의 핵심입니다.

다음 시간에는 자바의 hashCode() 메서드와 더 발전된 해시 알고리즘 구현에 대해 알아보겠습니다.

혹시 해시 알고리즘이나 자바 컬렉션에 대해 궁금한 점이 있으시거나, 함께 공부하고 싶으신 주제가 있으시면 언제든지 댓글로 남겨주세요. 여러분들의 의견과 질문이 더 좋은 콘텐츠를 만드는 데 큰 도움이 됩니다! 함께 성장하는 개발 여정을 이어가요. 😊

'📚 학습 기록 > Java 기초 & 중급' 카테고리의 다른 글

자바 HashSet 완벽 가이드: equals()와 hashCode()의 중요성과 제네릭 활용법 (1)	2025.04.22
자바 HashSet 완전 정복: 해시 알고리즘과 충돌 해결 전략 구현하기 (1)	2025.04.21
자바 컬렉션 프레임워크 완전 정복: ArrayList vs LinkedList 실전 비교 (1)	2025.04.15
ArrayList vs LinkedList: 성능 비교와 의존관계 이해하기 (1)	2025.04.14
자바 LinkedList 완전 정복: 개념과 직접 구현하기 (2)	2025.04.09

현재글자바 컬렉션 프레임워크: Set과 해시 알고리즘 이해하기

ZenJoyDev

"Zen: 기본에 충실하게, Joy: 즐겁게, Dev: 개발하기"

백엔드, 코딩공부, 수학의답, 프로그래밍, 모바일개발, Flutter, 수학, 성능최적화, 예외처리, 앱개발, dart, 개발자, 코딩, 자바, 자바중급, Java, 컬렉션프레임워크, 자료구조, 중등수학, 모바일앱개발,

Today :
Yesterday :

ZenJoyDev