[Java/김영한] HashSet

https://inf.run/sDjcZ

김영한의 실전 자바 - 중급 2편| 김영한 - 인프런 강의

이 링크를 통해 구매하시면 제가 수익을 받을 수 있어요. 🤗

 

 

 

직접 구현하는 Set1

 

`MyHashSetV0`의 단점

• `add()`로 데이터를 추가할 때 셋에 중복 데이터가 있는지 전체 데이터를 항상 확인해야 한다. 따라서 O(n)으로 입력 성능이 나쁘다.
• `contains()`로 데이터를 찾을 때는 셋에 있는 모든 데이터를 찾고 비교해야 하므로 평균 O(n)이 걸린다.

 

이렇게 성능이 느린 `MyHashSetV0`을 해시 알고리즘을 사용해서 평균 O(1)로 개선해보자.

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 +
                '}';
    }
}

 

`MyHashSetV1`은 해시 알고리즘을 사용한 덕분에 등록, 검색, 삭제 모두 평균 O(1)으로 연산 속도를 크게 개선했다.

---

문자열 해시 코드

문자 데이터를 기반으로 숫자 해시 인덱스를 구하려면 어떻게 해야할까?

 

문자를 숫자로 변경하는 방법

public class StringHashMain {

    static final int CAPATICY = 10;

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

        //hash
        System.out.println("hash(A) = " + hashCode("A"));
        System.out.println("hash(B) = " + hashCode("B"));
        System.out.println("hash(AB) = " + hashCode("AB"));

        //hashIndex
        System.out.println("hashIndex(A) = " + hashIndex(hashCode("A")));
        System.out.println("hashIndex(B) = " + hashIndex(hashCode("B")));
        System.out.println("hashIndex(AB) = " + hashIndex(hashCode("AB")));
    }

    static int hashCode(String str) {
        char[] charArray = str.toCharArray();
        int sum = 0;
        for (char c : charArray) {
            sum += c;
        }
        return sum;
    }

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

 

모든 문자는 본인만의 고유한 숫자로 표현할 수 있다. 가장 단순하게 `char` 형을 `int` 형으로 캐스팅하면 문자의 고유한 숫자를 확인할 수 있다.

 

그리고 "AB"와 같이 연속된 문자는 각각의 문자를 더하는 방식으로 숫자로 표현하면 된다. 

 

 

해시 코드와 해시 인덱스

• `hashCode()` 메서드를 사용해서 문자열을 해시 코드로 변환한다. 그러면 고유한 정수 숫자 값이 나오는데, 이것을 해시 코드라 한다.
• 숫자 값인 해시 코드를 사용해서 해시 인덱스를 생성한다.
• 이렇게 생성된 해시 인덱스를 배열의 인덱스로 사용하면 된다.

---

용어 정리

해시 함수(Hash Function)

• 임의의 길이의 데이터를 입력으로 받아, 고정된 길이의 해시값(해시 코드)을 출력하는 함수
  • 여기서 의미하는 고정된 길이는 저장 공간의 크기를 뜻한다. 예를 들어 `int`형 `1`, `100`은 둘 다 4byte를 차지하는 고정된 길이를 뜻한다.
• 같은 데이터를 입력하면 항상 같은 해시 코드가 출력된다.
• 다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있다. (해시 충돌)

 

 

해시 코드(Hash Code)

데이터를 대표하는 값으로, 보통 해시 함수를 통해 만들어진다.

• 데이터 `A`의 해시 코드는 `65`
• 데이터 `B`의 해시 코드는 `66`
• 데이터 `AB`의 해시 코드는 `131`

 

해시 인덱스(Hash Index)

• 데이터의 저장 위치를 결정하는데, 주로 해시 코드를 사용해서 만든다.
• 보통 해시 코드의 결과에 배열의 크기를 나누어 구한다.

 

요약하면, 해시 코드는 데이터를 대표하는 값, 해시 함수는 이러한 해시 코드를 생성하는 함수, 그리고 해시 인덱스는 해시 코드를 사용해서 데이터의 저장 위치를 결정하는 값을 뜻한다.

---

자바의 HashCode()

해시 자료 구조를 사용하려면 정수로 된 숫자 값인 해시 코드가 필요하다. 자바에는 정수 `int`, `Integer` 뿐만 아니라 `char`, `String`, `Double`, `Boolean` 등 수 많은 타입이 있다. 뿐만 아니라 개발자가 직접 정의한 사용자 정의 타입도 있다. 

 

이 모든 타입을 해시 자료 구조에 저장하려면 모든 객체가 숫자 해시 코드를 제공할 수 있어야 한다.

 

Object.hasCode()

자바는 모든 객체가 자신만의 해시 코드를 표현할 수 있는 기능을 제공한다. 바로 `Object`에 있는 `hashCode` 메서드이다.

public class Object {
    public int hashCode();
}

• 그대로 사용하기 보다는 보통 재정의(오버라이딩)해서 사용한다.
• 기본 구현은 객체의 참조값을 기반으로 해시 코드를 생성한다.
  • 쉽게 이야기해서 객체의 인스턴스가 다르면 해시 코드도 다르다.

 

 

자바의 기본 클래스의 해시 코드

• `Integer`, `String` 같은 자바의 기본 클래스들은 대부분 내부 값을 기반으로 해시 코드를 구할 수 있도록 `hashCode()` 메서드를 재정의해두었다.
• 따라서 데이터의 값이 같으면 같은 해시 코드를 반환한다.
• 해시 코드의 경우 정수를 반환하기 때문에 마이너스 값이 나올 수 있다.

 

동일성과 동등성

• 동일성(Identity):
  • `==` 연산자를 사용해서 두 객체의 참조가 동일한 객체를 가리키고 있는지 확인
  • 물리적으로 같은 메모리에 있는 객체인지 참조값 확인
• 동등성(Equality):
  • `equals()` 메서드를 사용하여 두 객체가 논리적으로 동등한지 확인
  • 보통 사람이 생각하는 논리적인 것에 기준을 맞춤

---

직접 구현하는 해시 코드

`Member`의 경우, 회원 `id`가 같으면 논리적으로 같은 회원으로 표현할 수 있다. 따라서 회원 `id`를 기반으로 동등성을 비교하도록 `equals()`를 재정의해야 한다. 

 

여기에 `hashCode()`도 같은 원리가 적용된다. 회원의 `id`가 같으면 논리적으로 같은 회원으로 표현할 수 있다. 따라서 회원 `id`를 기반으로 해시 코드를 생성해야 한다.

 

 

Member의 hashCode() 구현

 

class Member {
    private String id;

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

• `hashCode()`를 재정의할 때 `Objects.hash()`에 해시 코드로 사용할 값을 지정해주면 쉽게 해시 코드를 생성할 수 있다.
• `hashCode()`를 재정의하지 않으면 `Object`가 기본으로 제공하는 `hashCode()`를 사용하게 된다. 이것은 객체의 참조값을 기반으로 해시 코드를 제공한다. 따라서 회원의 `id`가 같아도 인스턴스가 다르면 다른 해시 코드를 반환하게 된다.
• `hashCode()`를 `id`를 기반으로 재정의한 덕분에 인스턴스가 달라도 `id` 값이 같으면 같은 해시 코드를 반환한다.

---

직접 구현하는 Set2

`MyHashSetV1`은 `Integer` 숫자만 저장할 수 있었다. 여기서는 모든 타입을 저장할 수 있는 `Set`인 `MyHashSetV2`를 만들어보자.

 

변경된 부분

private LinkedList<Object>[] buckets;

• 모든 타입을 저장할 수 있도록 `Object`를 사용한다.
• 추가로 저장, 검색, 삭제 메서드의 매개변수도 `Object`로 변경한다.

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

• `Object`의 `hashCode()`를 호출해서 해시 코드를 찾는다. 그리고 찾은 해시 코드를 배열의 크기(`capacity`)로 나머지 연산을 수행한다. 이렇게 해시 코드를 기반으로 해시 인덱스를 계산해서 반환한다.
• `Object`의 `hashCode()`를 사용한 덕분에 모든 객체의 `hashCode()`를 구할 수 있다. 물론 다형성에 의해 오버라이딩된 `hashCode()`가 호출된다.
• `hashCode()`의 실행 결과로 음수가 나올 수 있는데, 배열의 인덱스로 음수는 사용할 수 없다. `Math.abs()`를 사용하면 마이너스를 제거해서 항상 양수를 얻을 수 있다.

---

equals, hashCode의 중요성

해시 자료 구조를 사용하려면 `hashCode()`도 중요하지만, 해시 인덱스가 충돌할 경우를 대비해서 `equals()`도 반드시 재정의해야 한다. 해시 인덱스가 충돌할 경우 같은 해시 인덱스에 있는 데이터들을 하나하나 비교해서 찾아야한다. 이때 `equals()`를 사용해서 비교한다.

 

 

Object의 기본 기능

• `hashCode()`: 객체의 참조값을 기반으로 해시 코드를 반환
• `equals()`: `==` 동일성 비교를 한다. 따라서 객체의 참조값이 같아야 `true`를 반환한다.

 

hashCode, equals를 모두 구현하지 않은 경우

public class MemberNoHashNoEq {

    private String id;

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

    public String getId() {
        return id;
    }

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

 

public class HashAndEqualsMain1 {

    public static void main(String[] args) {
        //중복 등록
        MyHashSetV2 set = new MyHashSetV2(10);
        MemberNoHashNoEq m1 = new MemberNoHashNoEq("A");
        MemberNoHashNoEq m2 = new MemberNoHashNoEq("A");
        System.out.println("m1.hashCode() = " + m1.hashCode());
        System.out.println("m2.hashCode() = " + m2.hashCode());
        System.out.println("m1.equals(m2) = " + m1.equals(m2));

        set.add(m1);
        set.add(m2);
        System.out.println(set);

        //검색 실패
        MemberNoHashNoEq searchValue = new MemberNoHashNoEq("A");
        System.out.println("searchValue.hashCode() = " + searchValue.hashCode());
        boolean contains = set.contains(searchValue);
        System.out.println("contains = " + contains);
    }
}

 

실행 결과

m1.hashCode() = 1004 //인스턴스의 참조이므로 변한다.
m2.hashCode() = 1007 //인스턴스의 참조이므로 변한다.
m1.equals(m2) = false 
MyHashSetV2{buckets=[[MemberNoHashNoEq{id='A'}], [], [], [], [MemberNoHashNoEq{id='A'}], [], [], [], [], []], size=2, capacity=10} 
searchValue.hashCode() = 1008
contains = false

 

 

 

데이터 저장 문제

• `m1`, `m2`의 해시 코드가 서로 다르기 때문에 다른 위치에 각각 저장된다.
• 회원 id가 "A"로 같은 회원의 데이터가 중복 저장된다.

 

데이터 검색 문제

• `MemberNoHashNoEq searchValue = new MemberNoHashNoEq('A')`
• 회원 id가 "A"인 객체를 검색하기 위해 회원 id가 "A"인 객체를 만들었다. 이 객체의 참조값은 `1008`이라 가정하자.
• 데이터를 검색할 때 `searchValue` 객체의 해시 코드는 `1008`이다. 따라서 다른 위치에서 데이터를 찾게 되고, 검색에 실패한다.

 

---

hashCode는 구현했지만 equals를 구현하지 않은 경우

public class MemberOnlyHash {

    private String id;

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

    public String getId() {
        return id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

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

• `Objects.hash(id)`를 사용해서 `id`를 기준으로 해시 코드를 생성했다.

 

public class HashAndEqualsMain2 {

    public static void main(String[] args) {
        //중복 등록
        MyHashSetV2 set = new MyHashSetV2(10);
        MemberOnlyHash m1 = new MemberOnlyHash("A");
        MemberOnlyHash m2 = new MemberOnlyHash("A");
        System.out.println("m1.hashCode() = " + m1.hashCode());
        System.out.println("m2.hashCode() = " + m2.hashCode());
        System.out.println("m1.equals(m2) = " + m1.equals(m2));

        set.add(m1);
        set.add(m2);
        System.out.println(set);

        //검색 실패
        MemberOnlyHash searchValue = new MemberOnlyHash("A");
        System.out.println("searchValue.hashCode() = " + searchValue.hashCode());
        boolean contains = set.contains(searchValue);
        System.out.println("contains = " + contains);
    }
}

 

실행 결과

m1.hashCode() = 96
m2.hashCode() = 96
m1.equals(m2) = false
MyHashSetV2{buckets=[[], [], [], [], [], [], [MemberOnlyHash{id='A'},
MemberOnlyHash{id='A'}], [], [], []], size=2, capacity=10}
searchValue.hashCode() = 96
contains = false

 

 

데이터 저장 문제

• `hashCode()`를 재정의했기 때문에 같은 `id`를 사용하는 `m1`, `m2`는 같은 해시 코드를 사용한다. → 같은 해시 인덱스에 데이터 저장
• 그런데 `add()` 로직은 중복 데이터를 체크하기 때문에 같은 데이터가 저장되면 안된다.
  • `contains()` 내부에서 데이터를 순차 비교할 때 `equals()`를 사용한다.
  • 그런데 재정의를 하지 않았으므로 `Object`의 `equals()`를 상속받아서 인스턴스의 참조값을 비교한다.      
  • 따라서 인스턴스가 서로 다른 `m1`, `m2`를 모두 저장한다.
• 결과적으로 같은 회원 `id`를 가진 중복 데이터가 저장된다.

 

 

데이터 검색 문제

• `MemberOnlyHash searchValue = new MemberOnlyHash('A')`
• 회원 id가 "A"인 객체를 검색하기 위해 회원 id가 "A"인 객체를 만들었다. 해시 코드가 구현되어 있다. →`searchValue`는 해시 인덱스 6을 정확히 찾을 수 있다.
• 해시 인덱스에 있는 모든 데이터를 `equals()`를 통해 비교해서 같은 값을 찾아야 한다.

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

• `MemberOnlyHash`는 `equals()`를 재정의하지 않았으므로 `Object`의 `equals()`를 상속 받아서 사용한다. 따라서 인스턴스의 참조값을 비교한다. 인스턴스가 서로 다른 `searchValue`와 `m1`, `m2`는 비교에 실패한다.
• 결과적으로 데이터를 찾을 수 없다.

---

hashCode, equals 모두 구현한 경우

public class Member {

    private String id;

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

    public String getId() {
        return id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Member member = (Member) o;
        return Objects.equals(id, member.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

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

 

실행 결과

m1.hashCode() = 96
m2.hashCode() = 96
m1.equals(m2) = true
MyHashSetV2{buckets=[[], [], [], [], [], [], [Member{id='A'}], [], [], []],
size=1, capacity=10}
searchValue.hashCode() = 96
contains = true

 

 

데이터 저장

• 처음에 `m1`을 저장한다.
• 다음으로 `m2` 저장을 시도한다. `m1`과 같은 해시 코드를 사용하므로 해시 인덱스도 같다.
• 여기서 중복 데이터를 저장하면 안되므로 `m1`과 `m2`를 `equals` 비교한다. 같은 데이터가 이미 있으므로 `m2`는 저장에 실패한다.
• 결과적으로 중복 데이터가 저장되지 않는다.

 

 

데이터 검색

• `searchValue`의 해시 코드로 6번 해시 인덱스를 찾는다.
• `searchValue`와 6번 해시 인덱스 내부의 데이터를 모두 `equals` 비교한다. `searchValue`와 `m1`이 `equals` 비교에 성공하므로 참을 반환한다.

 

 

`hashCode()`를 항상 재정의해야 하는 것은 아니다. 하지만 해시 자료 구조를 사용하는 경우 `hashCode()`와 `equals()`를 반드시 함께 재정의해야 한다. 

---

제네릭과 인터페이스 도입

지금까지 만든 해시 셋에 제네릭을 도입해서 타입 안전성을 높여보자.

 

public interface MySet<E> {
    boolean add(E element);
    boolean remove(E value);
    boolean contains(E value);
}

• 핵심 기능을 인터페이스로 뽑았다.
• 이 인터페이스를 구현하면 해시 기반이 아니라 다른 자료 구조 기반의 Set도 만들 수 있다.

 

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

    @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 searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<E> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }

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

• 이전 코드에서 `Object`로 다루던 부분들을 제네릭 타입 매개변수 `E`로 변경했다.

 

public class MyHashSetV3Main {

    public static void main(String[] args) {
        MyHashSetV3<String> set = new MyHashSetV3<>(10);
        set.add("A");
        set.add("B");
        set.add("C");
        System.out.println(set);

        //검색
        String searchValue = "A";
        boolean result = set.contains(searchValue);
        System.out.println("bucket.contains(" + searchValue + ") = " + result);
    }
}

• 제네릭 덕분에 타입 안전성이 높은 자료 구조를 만들 수 있다.