[컬렉션 프레임워크] HashSet

HashSet

 

* HashSet이란?

자바에서 제공하는 Set 인터페이스의 구현체 중 하나로 중복 없는 데이터 저장, 빠른 탐색이 필요한 상황에서 사용

내부적으로 배열 + 해시 기반 구조를 가지며, 순서를 보장하지 않고 null 값은 하나만 저장 가능

 

* HashSet 특징

• 중복 불가 : equals()와 hashCode()로 동일한 객체 판별
• 순서 보장 X : 저장 순서와 출력 순서가 다를 수 있음
• null 허용 : null 값 1개만 저장 가능
• 빠른 검색/삽입/삭제 : 평균 시간복잡도 O(1)

* HashSet 내부 작동 원리

1. 객체를 저장할 때 hashCode() 메서드를 호출해 해시값 생성
   • 정수가 아닌 값들을 정수로 바꿔서 배열의 인덱스로 활용할 수 있게 변환
2. 해시값을 기준으로 배열 인덱스를 구함(hash % capacity)
3. 같은 인덱스가 중복되면(해시 충돌 발생) LinkedList(or Tree)를 통해 저장
4. 요소를 비교할 땐 hashCode() -> equals() 순서로 비교

* Hash 용어 정리

• 해시 함수(Hash Function) : 데이터를 고정된 크기의 숫자로 변환하는 함수 -> hashCode()
• 해시 코드(Hash Code) : 해시 함수를 통해 생성된 정수 값, 동일 객체는 동일 해시코드를 가져야 함
• 해시 인덱스(Hash Index) : 해시 코드를 배열의 인덱스로 변환한 값 -> hashCode % capacity
• 해시 충돌(Hash Collision) : 서로 다른 값이 동일한 해시 인덱스를 가질 때 발생하는 문제
• 버킷(Bucket) : 동일한 해시 인덱스를 가지는 요소들을 저장하는 공간(주로 리스트 형태)
• 체이닝(Chaining) : 해시 충돌 해결 방식 중 하나, 각 인덱스에 연결 리스트를 둬서 여러 값 저장

---

직접 구현한 HashSet

1. 배열 기반 Set

• 특징
  • int[ ] 배열 기반
  • 단순 반복을 통해 값 존재 여부 탐색 -> O(n)
• 문제점
  • 탐색 성능 낮음(선형 탐색)
  • 중복 체크 비효율적
  • 고정 크기 배열 -> 확장성 없음
• 개선 방향
  • 해시 인덱스 도입으로 탐색 속도 개선
  • 중복 체크를 빠르게 처리할 수 있는 자료구조 도입 필요

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;
        return true;
    }

    public boolean contains(int value) {
        for (int data : elementData) {
            if (data == value) return true;
        }
        return false;
    }
}

* 문자열 해시코드

 

1. 문자열도 해시코드를 가짐

• 자바의 모든 객체는 Object의 hashCode() 메서드를 가지고 있고, String 클래스는 이 메서드를 오버라이딩해서 고유의 해시코드를 계산

2. 해시 코드 계산(자바의 String hashCode)

s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1]

String str = "abc";
int hash = 'a'*31^2 + 'b'*31^1 + 'c'*31^0;


'a' = 97, 'b' = 98, 'c' = 99
hashCode = (97 * 31^2) + (98 * 31) + (99)
         = (97 * 961) + (98 * 31) + 99
         = 93217

3. 특징

• 같은 문자열이면 항상 같은 해시코드 반환
• 문자열이 다르면 해시 충돌이 발생할 수 있음(서로 다른 문자열인데 같은 해시 코드일 경우)
• equals() 도 함께 사용해야 진짜 동일한 값인지 판단 가능

4. HashSet에서 문자열 저장 순서

• 문자열의 hashCode() 호출 -> 인덱스 결정
• 해당 버킷으로 이동
• equals()로 중복 확인 -> 없으면 저장

- ASCII 코드 표

 

* 자바의 hashCode()

• hashCode란?
  • 자바의 Object 클래스에 정의된 모든 객체가 가진 메서드
  • 객체를 식별하기 위한 정수형 값(int)을 반환
  • 주로 HashSet, HashMap 등 해시 기반 자료구조에서 객체의 위치(버킷 인덱스)를 결정할 때 사용
• hashCode()는 음수도 나올 수 있음
  • 반환 타입이 int 이기 때문에, -2^31 ~ 2^31-1 범위 내 정수
  • 해시 인덱스를 만들 때는 Math.abs() 또는 hash & 0x7fffffff 등으로 양수 처리 필요
• 동일성(identity) vs 동등성(equality)
  • 동일성(identity)
    • 완전히 같은 객체(주소 비교)
    • == 연산자
  • 동등성(equality)
    • 의미상 같은 객체(값 비교)
    • .equals() 메서드
• Object의 기본 hashCode()
  • Object의 기본 구현은 객체의 메모리 주소를 기반으로 해시 코드 생성
  • 참조가 다르면 hashCode도 다름
• String의 hashCode()
  • equals()와 hashCode() 모두 재정의됨 -> 동등성 비교 시 동작 잘 됨
  • 내부적으로는 문자 배열 기반 해시 계산

 

2. 해시 인덱스 기반 Set(LinkedList[ ] 사용)

• 특징
  • LinkedList<Integer>[ ] 형태의 해시 버킷 사용
  • value % capacity 를 해시 인덱스로 사용(정수 기반 해싱)
• 문제점
  • 정수(Integer)만 저장 가능
  • 값 자체를 해시 기준으로 사용하므로 다양한 타입 저장 불가
• 개선 방향
  • 객체 저장을 위해 Object 타입 도입
  • equals()와 hashCode()를 활용한 정확한 비교 필요

package collection.set;

import java.util.Arrays;
import java.util.LinkedList;

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

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

        initBuckets();
    }

    private void initBuckets() {
        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 "MyHashSetV1{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}

 

3. 객체 저장을 위한 개선(Object 사용)

• 특징
  • LinkedList<Objcet>[ ] 사용 -> 다양한 객체 저장 가능
  • hashCode() 기반 해시 인덱스
  • equals()를 통한 중복 판별
• 문제점
  • 타입 안정성 부족
  • 값 꺼낼 때 형변환 필요
  • Objcet 기반으로 작성된 로직 -> 제네릭 적용 필요
• 개선 방향
  • 제네릭 적용을 통해 타입 안정성 확보
  • 형변환 제거, 유지보수성 향상

package collection.set;

import java.util.Arrays;
import java.util.LinkedList;

public class MyHashSetV2 {

    static final int DEFAULT_INITIAL_CAPACITY = 16;

    private LinkedList<Object>[] buckets;

    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;

    public MyHashSetV2() {
        initBuckets();
    }

    public MyHashSetV2(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }

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

    public boolean add(Object value) {
        int hashIndex = hashIndex(value);
        LinkedList<Object> bucket = buckets[hashIndex];
        if (bucket.contains(value)) {
            return false;
        }

        bucket.add(value);
        size++;
        return true;
    }

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

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

    private int hashIndex(Object value) {
        //hashCode의 결과로 음수가 나올 수 있다. abs()를 사용해서 마이너스를 제거한다.
        return Math.abs(value.hashCode()) % capacity;
    }

    public int getSize() {
        return size;
    }

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

 

4. 제네릭 기반 타입 안전 HashSet

• 특징
  • 제네릭 기반 구현 -> 타입 안정성 보장
  • 다양한 타입 저장 가능 + 형변환 불필요
  • 실무에서 사용하는 구조와 유사
• 문제점
  • 근본적인 구조 문제는 없지만 해시 충돌 대비 방식은 체이닝 한정

package collection.set;

import java.util.Arrays;
import java.util.LinkedList;

public class MyHashSetV3<E> implements MySet<E> {

    static final int DEFAULT_INITIAL_CAPACITY = 16;

    private LinkedList<E>[] buckets;

    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;

    public MyHashSetV3() {
        initBuckets();
    }

    public MyHashSetV3(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }

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

    public boolean add(E value) {
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        if (bucket.contains(value)) {
            return false;
        }

        bucket.add(value);
        size++;
        return true;
    }

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

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

    private int hashIndex(Object value) {
        //hashCode의 결과로 음수가 나올 수 있다. abs()를 사용해서 마이너스를 제거한다.
        return Math.abs(value.hashCode()) % capacity;
    }

    public int getSize() {
        return size;
    }

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

package collection.set;

public interface MySet<E> {

    boolean add(E element);

    boolean remove(E value);

    boolean contains(E value);
}

 

요약

핵심 구조	특징	문제점	개선 방향
int[ ] 배열 기반	단순 배열 저장 순차 탐색	O(n) 선형 탐색 중복 제거 비효율	성능 개선 필요 -탐색 속도
LinkedList[ ] 해시 버킷	나머지 연산 기반 해시 인덱스 사용 -> O(1)	해시 충돌 발생 가능 충돌 해결 구조 필요	체이닝 방식 도입
Object 타입 사용	다양한 타입 저장 가능	타입 안정성 부족 캐스팅 필요	제네릭 적용 필요
제네릭 + Object.hashCode() 사용	모든 참조형 객체에 대해 동작 가능 타입 안정성 확보	hashCode()가 잘 정의되지 않으면 충돌 가능성 증가	equals() + hashCode() 오버라이딩 필요

 

---

equals
& hashCode 의 중요성

 

* equals() & hashCode() 의 중요성

해시 기반 컬렉션(HashSet, HashMap)은 객체의 중복 여부와 탐색 위치를 판단할 때 두 메서드를 조합해서 사용

• hashCode() : 객체의 저장 위치(버킷 인덱스)를 결정
• equals() : 해당 위치에서 객체가 실제로 같은지 확인

* 동작 순서

1. 객체 저장 요청 → hashCode() 호출 → 배열 인덱스 계산
2. 해당 인덱스의 버킷 확인
3. 동일 hashCode 값의 객체가 있다면 → equals() 호출
4. equals() 결과가 true면 → 중복으로 간주 (저장 안 함)

* 케이스 별 문제

1. 둘 다 오버라이딩 하지 않은 경우

• Object의 기본 메서드 사용 -> 참조 주소 비교
• 값이 같아도 인스턴스가 다르면 다르게 인식됨
• 문제
  • HashSet, HashMap에서 중복제거/탐색 실패

new User("kim") != new User("kim") // 주소가 다름
→ Set에 중복으로 저장됨

 

2. equals()만 오버라이딩 한 경우

• hashCode는 여전히 주소 기반
• 같은 값인데 다른 해시값 -> 다른 버킷에 저장됨
• 문제
  • 버킷 자체가 달라서 equals()까지 도달 못함
  • 즉, 중복 판단 실패

User user1 = new User("kim");
User user2 = new User("kim");

user1.equals(user2) == true
user1.hashCode() != user2.hashCode() // 다른 버킷 → 다른 객체로 저장됨

 

3. hashCode()만 오버라이딩한 경우

• 버킷은 같아짐 -> 탐색 가능
• equals()가 주소 비교할 때 다른 객체로 판단
• 문제
  • 논리적으로는 같지만 중복 제거 실패

user1.hashCode() == user2.hashCode()
user1.equals(user2) == false → 중복 허용됨

 

4. 둘 다 제대로 오버라이딩 한 경우

• 버킷 인덱스도 동일하고 equals() 도 true
  • 완벽한 중복 제거 가능

 

결론 : 해시 기반 컬렉션 사용 시 핵심

• equals()와 hashCode()는 반드시 함께 오버라이딩해야 한다
• 둘 중 하나라도 누락되면 중복 제거와 탐색이 정상 작동하지 않는다

---

총정리

• HashSet
  • 중복 X, 순서 X 컬렉션(Set 인터페이스 구현체)
  • 내부적으로 해시 기반 저장 구조 사용
  • hashCode()로 해시값 생성, equals()로 중복 판별
  • 탐색, 추가, 삭제 속도 빠름 -> 평균 O(1)
• 문자열 해시코드 : 내부적으로 31을 활용한 계산 방식
• 해시 충돌 : 같은 인덱스에 여러 값인 경우 체이닝 방식으로 해결
• equals() & hashCode() : 둘 다 오버라이딩 필수, 논리적 동등성 판단

---

<참고> - 김영한의 실전 자바 중급2편 강의 섹션 8. 컬렉션 프레임워크 HashSet