[컬렉션 프레임워크] HashSet

1. Set이란?

☑︎ 중복을 허용하지 않고, 순서를 보장하지 않는 자료구조

☑︎ 대표적인 구현체: HashSet, LinkedHashSet, TreeSet

---

2. Set의 기본 동작

☑︎ add(value) : 중복이면 저장하지 않음

☑︎ contains(value) : 포함 여부 확인

☑︎ remove(value) : 데이터 삭제

☹︎ 하지만 일반적인 Set 구현체는 내부 데이터를 일일이 비교 → 시간 복잡도 O(n)

---

3. HashSet이란?

☑︎ 내부적으로 해시 함수를 이용한 배열 기반의 구조

☑︎ hashCode()와 equals()를 기준으로 중복 여부를 판단

☑︎ 탐색 속도 빠름 (평균 시간 복잡도 O(1))

---

4. 직접 구현하는 Set - MyHashSetV1 (정수형 전용)

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<>();
        }
    }

    // 해시 인덱스 계산
    private int hashIndex(int value) {
        return value % capacity;
    }

    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);
        return buckets[hashIndex].contains(searchValue);
    }

    public boolean remove(int value) {
        int hashIndex = hashIndex(value);
        boolean removed = buckets[hashIndex].remove(Integer.valueOf(value));
        if (removed) size--;
        return removed;
    }

    public int getSize() {
        return size;
    }

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

---

5. 문자열 해시 함수 구현

☹︎ 문제점: "BC"(66+67=133), "AD"(65+68=133) → 해시 충돌 발생!

static int hashCode(String str) {
    char[] chars = str.toCharArray();
    int sum = 0;
    for (char c : chars) {
        sum += c; // 각 문자의 유니코드 합산
    }
    return sum;
}

static int hashIndex(int hashCode) {
    return hashCode % 10; // capacity = 10 기준
}

---

6. 자바의 String 해시코드 계산 방식

• 31을 곱하는 이유: 충돌 방지 + 계산 최적화(31 = 32-1)
• equals()가 true인 경우에는 반드시 hashCode()도 같아야 함

String str = "AB";
int hash = 0;
for (char c : str.toCharArray()) {
    hash = 31 * hash + c;
}

---

7. Object의 hashCode()는 참조값 기반

☑︎ Object의 기본 hashCode()는 주소 기반이므로, 서로 다른 객체는 다른 값

Object obj1 = new Object();
Object obj2 = new Object();
System.out.println(obj1.hashCode()); // ex) 123456
System.out.println(obj2.hashCode()); // 서로 다름

---

8. Member 클래스 예제 (hashCode + equals 오버라이딩)

public class Member {
    private String id;

    public Member(String id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Member)) return false;
        Member other = (Member) o;
        return Objects.equals(this.id, other.id); // id 기준 비교
    }

    @Override
    public int hashCode() {
        return Objects.hash(id); // id의 해시코드를 사용
    }

    @Override
    public String toString() {
        return "Member{id='" + id + "'}";
    }
}

---

9. 직접 구현하는 Set - MyHashSetV2 (Object 타입으로 확장)

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(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }

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

    private int hashIndex(Object value) {
        return Math.abs(value.hashCode()) % capacity;
    }

    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 value) {
        return buckets[hashIndex(value)].contains(value);
    }

    public boolean remove(Object value) {
        boolean removed = buckets[hashIndex(value)].remove(value);
        if (removed) size--;
        return removed;
    }

    public int getSize() {
        return size;
    }

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

---

10. equals/hashCode 미구현 시 발생 문제

☑︎ Object 기본 equals()는 참조 비교 (==)

☑︎ hashCode()만 오버라이딩하면 equals() 실패 → 중복 감지 못 함

☑︎ equals()만 오버라이딩해도 해시 버킷 위치가 다르면 탐색 불가

☑︎ 반드시 둘 다 구현해야 Set에서 정상 작동

---

11. 제네릭 기반의 Set 구현 - MyHashSetV3

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(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }

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

    private int hashIndex(Object value) {
        return Math.abs(value.hashCode()) % capacity;
    }

    @Override
    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;
    }

    @Override
    public boolean contains(E value) {
        return buckets[hashIndex(value)].contains(value);
    }

    @Override
    public boolean remove(E value) {
        boolean removed = buckets[hashIndex(value)].remove(value);
        if (removed) size--;
        return removed;
    }

    public int getSize() {
        return size;
    }

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

---

12. 용어 정리

용어	의미
해시 함수	객체 → 정수값(해시 코드)으로 바꿔주는 함수
해시 코드	객체를 대표하는 정수값
해시 인덱스	해시 코드 % 배열 크기
equals()	두 객체의 논리적 동등성 비교
hashCode()	객체의 해시값 반환, equals와 일치해야 함
Set 자료구조	중복 없음, 순서없음, equals/hashCode 기준 비교

 

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