자바 HashSet 완전 정복: 해시 알고리즘과 충돌 해결 전략 구현하기

안녕하세요! 오늘은 자바 컬렉션 프레임워크의 중요한 구성 요소인 HashSet에 대해 심층적으로 알아보겠습니다. 특히 해시 알고리즘의 원리와 해시 충돌이 발생했을 때 이를 어떻게 해결하는지, 그리고 직접 간단한 HashSet을 구현해보는 과정을 통해 내부 동작 원리를 이해해보겠습니다.

해시(Hash)란 무엇인가?

해시는 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 기술입니다. 이 과정에서 사용되는 함수를 해시 함수라고 하며, 해시 함수를 통해 얻어낸 값을 해시 코드 또는 해시 값이라고 합니다.

해시의 가장 큰 장점은 데이터 검색 속도가 매우 빠르다는 것입니다. 이상적인 경우, 해시 검색은 O(1)의 시간 복잡도를 가집니다. 이는 데이터의 양에 관계없이 일정한 시간 내에 검색이 가능하다는 의미입니다.

해시 충돌(Hash Collision)과 해결 방법

해시 함수는 서로 다른 입력값에 대해 동일한 해시값을 출력할 수 있습니다. 이러한 현상을 해시 충돌이라고 합니다. 예를 들어, 숫자를 10으로 나눈 나머지를 해시값으로 사용한다면 11과 21은 모두 1이라는 동일한 해시값을 갖게 됩니다.

해시 충돌은 피할 수 없는 현상이지만, 이를 효과적으로 관리하는 방법이 있습니다. 그 중 가장 일반적인 방법이 체이닝(Chaining) 입니다.

체이닝(Chaining) 방식

체이닝은 해시 충돌이 발생했을 때, 동일한 해시 인덱스에 여러 데이터를 연결 리스트 형태로 저장하는 방식입니다. 아래 코드를 통해 구현 방법을 살펴보겠습니다:

static final int CAPACITY = 10;

public static void main(String[] args) {
    LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
    for (int i = 0; i < CAPACITY ; i++) {
        buckets[i] = new LinkedList<>();
    }
    
    // 데이터 추가
    add(buckets, 1);
    add(buckets, 2);
    add(buckets, 5);
    add(buckets, 8);
    add(buckets, 14);  // 해시 충돌: 14 % 10 = 4
    add(buckets, 99);  // 해시 충돌: 99 % 10 = 9
    add(buckets, 9);   // 해시 충돌: 9 % 10 = 9
    
    System.out.println("buckets = " + Arrays.toString(buckets));
    
    // 데이터 검색
    int searchValue = 9;
    boolean contains = contains(buckets, searchValue);
    System.out.println("buckets.contains(" + searchValue + ") = " + contains);
}

private static void add(LinkedList<Integer>[] buckets, int value) {
    int hashIndex = hashIndex(value);
    LinkedList<Integer> bucket = buckets[hashIndex];
    if (!bucket.contains(value)) {
        bucket.add(value);
    }
}

private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
    int hashIndex = hashIndex(searchValue);
    LinkedList<Integer> bucket = buckets[hashIndex];
    return bucket.contains(searchValue);
}

static int hashIndex(int value) {
    return value % CAPACITY;
}

위 코드에서 주목할 점:

1. 배열의 각 요소가 LinkedList 객체임 (버킷)
2. 데이터를 추가할 때 해시 인덱스를 계산하고, 해당 인덱스의 LinkedList에 값을 추가
3. 이미 존재하는 값은 중복 저장하지 않음 (Set의 특성)
4. 데이터 검색 시 해시 인덱스를 계산하고, 해당 인덱스의 LinkedList에서 값을 검색

이 방식의 장점은 데이터의 유일성을 보장하면서도 해시 충돌이 발생하더라도 데이터 손실 없이 모든 값을 저장할 수 있다는 것입니다. 단점은 최악의 경우 (모든 데이터가 같은 인덱스에 저장되는 경우) 검색 성능이 O(n)으로 저하될 수 있다는 점입니다.

HashSet 직접 구현하기

이제 체이닝 방식을 사용하여 간단한 HashSet을 직접 구현해 보겠습니다

public class MyHashSetV1 {
    private final int DEFAULT_INITIAL_CAPACITY = 16;
    LinkedList<Integer>[] buckets;
    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;

    public MyHashSetV1() {
        initBucktes();
    }

    public MyHashSetV1(int capacity) {
        this.capacity = capacity;
        initBucktes();
    }

    private void initBucktes() {
        buckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    public boolean add(int value) {
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex];
        if (bucket.contains(value)) {
            return false;  // 이미 존재하는 값이면 추가하지 않음
        }
        bucket.add(value);
        size++;
        return true;
    }

    public boolean contains(int searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<Integer> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }

    public boolean remove(int value) {
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex];
        boolean result = bucket.remove(Integer.valueOf(value));
        if (result) {
            size--;
            return true;
        } else {
            return false;
        }
    }

    private int hashIndex(int value) {
        return value % capacity;
    }

    public int getSize() {
        return size;
    }

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

이 구현은 정수형 값만 저장할 수 있는 간단한 HashSet입니다. 주요 특징은 다음과 같습니다:

1. 초기화: 생성자에서 지정한 크기(또는 기본 크기)의 LinkedList 배열을 생성합니다.
2. add 메서드: 값을 추가하기 전에 중복 여부를 확인하고, 중복되지 않은 경우에만 추가합니다.
3. contains 메서드: 해시 인덱스를 계산하여 해당 버킷에 값이 존재하는지 확인합니다.
4. remove 메서드: 해시 인덱스를 계산하여 해당 버킷에서 값을 제거합니다.

문자열의 해시 코드 계산

지금까지는 정수형 값을 해시 인덱스로 변환했지만, 실제로는 문자열이나 객체 같은 다양한 타입의 데이터를 해시 테이블에 저장해야 할 경우가 많습니다. 다음은 간단한 문자열 해시 코드 계산 방법입니다:

public class StringHashMain {
    static final int CAPACITY = 10;

    public static void main(String[] args) {
        char charA = 'A';
        char charB = 'B';
        System.out.println(charA + " = " + (int)charA);  // A = 65
        System.out.println(charB + " = " + (int)charB);  // B = 66

        // 해시코드 계산
        System.out.println("hashCode(A) = " + hashCode("A"));        // 65
        System.out.println("hashCode(B) = " + hashCode("B"));        // 66
        System.out.println("hashCode(AB) = " + hashCode("AB"));      // 131 (65+66)
        System.out.println("hashCode(C) = " + hashCode("C"));        // 67

        // 해시 인덱스 계산
        System.out.println("hashIndex(A) = " + hashIndex(hashCode("A")));     // 5
        System.out.println("hashIndex(B) = " + hashIndex(hashCode("B")));     // 6
        System.out.println("hashIndex(AB) = " + hashIndex(hashCode("AB")));   // 1
        System.out.println("hashIndex(C) = " + hashIndex(hashCode("C")));     // 7
    }

    static int hashIndex(int a) {
        return a % CAPACITY;
    }

    static int hashCode(String a) {
        char[] charArray = a.toCharArray();
        int sum = 0;
        for (char c : charArray) {
            sum += c;  // 문자의 ASCII 값을 합산
        }
        return sum;
    }
}

위 코드는 문자열을 구성하는 각 문자의 ASCII 값을 합산하여 해시 코드를 계산하는 간단한 방법을 보여줍니다. 실제 자바의 String 클래스의 hashCode() 메서드는 더 복잡한 알고리즘을 사용하지만, 기본 원리는 유사합니다.

HashSet의 성능 특성

HashSet의 성능은 다음과 같은 특성을 가집니다:

1. 평균 시간 복잡도:
   • add, remove, contains: O(1)
   • 최악의 경우(해시 충돌이 많을 때): O(n)
2. 공간 복잡도:
   • O(n) - 저장되는 요소의 수에 비례
3. 해시 함수의 품질:
   • 좋은 해시 함수는 값들을 고르게 분포시켜 충돌을 최소화합니다.
   • 자바의 Object.hashCode() 메서드는 대부분의 경우 좋은 분포를 제공합니다.

실제 자바 HashSet과의 차이점

우리가 구현한 간단한 HashSet과 실제 자바의 HashSet 클래스 사이에는 몇 가지 중요한 차이점이 있습니다:

1. 제네릭 지원: 실제 HashSet은 제네릭을 지원하여 다양한 타입의 객체를 저장할 수 있습니다.
2. 동적 리사이징: 실제 HashSet은 저장되는 요소의 수에 따라 내부 배열의 크기를 동적으로 조정합니다.
3. 로드 팩터: 배열의 크기를 조정하는 기준으로 '로드 팩터'라는 개념을 사용합니다.
4. 해시 함수: 더 발전된 해시 함수와 인덱싱 방식을 사용합니다.

실무에서의 활용

HashSet은 다음과 같은 상황에서 특히 유용합니다:

1. 중복 제거: 컬렉션에서 중복된 요소를 제거할 때
2. 멤버십 테스트: 특정 요소가 집합에 포함되어 있는지 빠르게 확인할 때
3. 집합 연산: 합집합, 교집합, 차집합 등의 집합 연산을 수행할 때

예를 들어, 웹 크롤러에서 이미 방문한 URL을 추적하거나, 텍스트에서 고유한 단어를 추출하는 등의 작업에 HashSet이 자주 사용됩니다.

요약 및 결론

이번 포스팅에서는 해시 알고리즘의 기본 원리, 해시 충돌과 그 해결 방법인 체이닝에 대해 알아보았습니다. 또한 이를 바탕으로 간단한 HashSet을 직접 구현해보고, 문자열의 해시 코드 계산 방법도 살펴보았습니다.

해시 테이블은 평균적으로 O(1)의 시간 복잡도로 데이터를 검색할 수 있어 매우 효율적인 자료구조입니다. 이러한 특성 때문에 HashSet, HashMap 등의 컬렉션이 자바에서 널리 사용되고 있습니다.

자바 개발자라면 해시 알고리즘과 해시 기반 컬렉션의 내부 동작 원리를 이해하는 것이 중요합니다. 이를 통해 코드의 성능을 최적화하고, 적절한 자료구조를 선택하는 데 도움이 될 것입니다.

---

이 글이 해시와 HashSet에 대한 이해에 도움이 되셨나요? 궁금한 점이나 추가적인 내용이 있으시면 댓글로 남겨주세요! 다음에는 HashMap과 TreeSet 등 다른 컬렉션 클래스에 대해서도 살펴보도록 하겠습니다. 함께 자바 컬렉션 프레임워크의 세계를 탐험해봐요! 🚀