컬렉션 프레임워크 - Set 직접 구현해보기 (hash, hashCode()에 대해)

참고자료:

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

 

Set을 직접 구현해 보기 전 먼저 List와 Set은 어떤 차이가 있는지 알아보자.

List

• 순서가 보장된다. 넣는 순서대로 저장된다.
• 중복을 허용한다.

Set

• 순서가 보장되지 않는다.
• 중복을 허용하지 않는다.

Set은 중복된 값을 방지할 수 있는 좋은 자료구조이다. 그리고 해당 값이 있는지 빠르게 찾아낼 수 있는 방법을 가지고 있다.

어떻게 중복을 방지하고 값의 존재 유무를 빠르게 알아낼 수 있는지 직접 구현해 보면서 알아보자.

 

우선 가장 첫 번째 고민거리로, 배열이란 것을 생각해 볼 때 배열의 조회는 O(1)의 시간복잡도를 가진다. 인덱스로 한 번에 해당 메모리에 접근해서 값을 꺼내올 수 있으니 말이다. 그럼 배열에서 탐색은 O(n)의 시간복잡도를 가진다. 왜냐하면 원하는 값이 어디 있는지 모르니까 하나씩 순회하면서 찾아야 하니 말이다. 

 

이 말을 반대로 생각해 보면 배열에서 탐색을 O(1)의 시간복잡도로 갖게 하려면 저장하려는 값과 인덱스값이 일치하면 되지 않을까?

저장하려는 값과 인덱스 값을 일치시켜 탐색을 O(1)의 시간 복잡도로

 

인덱스를 통해 찾아가는 건 O(1)이니까 원하는 값과 인덱스가 일치하면 원하는 값을 탐색하는 것도 O(1)으로 해결할 수 있게 된다.

굉장히 좋은 생각 같지만 만약에 데이터가 (1, 2, 5, 8, 90) 5개인 경우를 생각해 보면 데이터는 고작 5개지만 배열의 크기는 91이어야 한다. 인덱스 90을 수용하려면 91개의 공간이 필요하기 때문에. 그래서 탐색 성능은 높아지지만 메모리의 낭비가 심해진다.

 

메모리 낭비를 나머지 연산으로 해결

이것을 효율적으로 해결하는 방법은 정해진 사이즈에서 적당한 자리를 찾을 수 있도록 나머지 연산을 사용하는 것이다.

이렇게 나머지 연산으로 얻어낸 결과를 해시라고 하자. (이후에 해시코드라는 것으로 이 비슷한 알고리즘을 구현해 낼 거라서 그렇다.)

1, 2, 5, 8, 90 5개의 데이터를 보관하기 위해서 10개의 공간을 가지는 배열을 만들었다고 가정해 보자. 

 

그럼 그 10개라는 공간으로 각 데이터를 나눈 나머지를 구해보는 것이다.

• 1 % 10 = 1
• 2 % 10 = 2
• 5 % 10 = 5
• 8 % 10 = 8
• 99 % 10 = 9

이렇게 나머지 연산을 통해 적절한 자리를 찾게 해서 배열의 사이즈로 인한 메모리 낭비도 줄이고 탐색할 때 시간도 최대한으로 끌어올릴 수 있을 것 같다. 결국 탐색을 위해서 필요한 연산은 나머지 연산 하나이고 그 나머지 연산의 결과로 얻어낸 인덱스를 바로 찾아가면 내가 원하는 값을 찾을 수 있으니까 말이다.

 

근데 여기에는 치명적인 단점이 있다. 나머지 연산에 충돌이 일어난다는 것. 9 % 10 = 9, 99 % 10 = 9 이다. 

이 경우에는 어떻게 하면 좋을까? 그러니까 상황을 생각해 보면 데이터 9가 이미 들어가 있는 상태이고, 데이터 99를 추가적으로 넣으려고 했더니 나머지 연산의 결과가 똑같이 9가 나와서 인덱스 9번으로 갔더니 이미 데이터가 있는 상황이다. 이 경우엔 그냥 그 자리에 같이 넣어버리면 된다. 다음 그림처럼 말이다.

 

 

그럼 이 상태에서 99를 탐색할 땐 어떻게 할까?

• 99를 탐색하겠다고 해시값을 구하면 결과는 9다. 
• 인덱스 9번을 갔더니 값이 여러 개가 존재한다.
• 하나씩 비교해서 찾아낸다.

 

이렇게 해시값과 Set이라는 자료 구조를 통해 연산 시 시간 복잡도는 어떻게 될까?

• 탐색
  • 시간복잡도는 평균적으로 O(1), 최악의 경우 O(n).
  • 해시 충돌이 일어나지 않는다면, 찾고자 하는 값으로 해시값을 구하기 O(1), 해당 해시값에 저장된 값 꺼내기 O(1).
  • 모든 값이 전부 다 해시 충돌이 일어나서 하나의 인덱스에만 데이터가 들어간 경우 해시값 구하기 O(1), 해당 인덱스에서 원하는 값 찾아내기 O(n).
• 추가
  • 시간복잡도는 평균적으로 O(1), 최악의 경우 O(n).
  • 해시 충돌이 일어나지 않는다면, 추가하려는 값으로 해시값 구하기 O(1), 해당 해시값을 인덱스로 데이터 넣기 O(1).
  • 해시 충돌이 빈번하게 일어나는 경우, 추가하려는 값으로 해시값 구하기 O(1), 해당 해시값을 인덱스로 하여 해당 메모리에 데이터를 넣기 위해 기존에 같은 데이터가 있는지 확인하는 탐색작업 O(n), 데이터 넣기 O(1)

 

그래서 결론은 일반적으로 O(1)으로 생각하면 된다. 

그럼 이런 내용을 토대로 한번 직접 HashSet을 구현해보자.

 

MyHashSetV1

package org.example.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;
    private int capacity = DEFAULT_INITIAL_CAPACITY;

    public MyHashSetV1() {
        initBuckets(capacity);
    }

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

    private void initBuckets(int capacity) {
        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 removed = bucket.remove(Integer.valueOf(value));
        if (removed) {
            size--;
            return true;
        }
        return false;
    }

    public int getSize() {
        return size;
    }

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

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

• 우선, Set에서 자료를 담을 자료구조는 LinkedList의 배열을 선택한다. LinkedList<Integer>[] buckets;
• 그리고 기본 크기는 16으로 설정했는데 이는 원하는 값을 생성자에서 받을 수도 있고 그대로 사용할 수도 있다.
• 생성자로부터 이 HashSet의 객체가 만들어지면, 각 인덱스별 LinkedList를 초기화한다.
• add(int value): 데이터를 저장하는 메서드. 해시값을 구하고 그 해시값을 인덱스로 배열의 위치를 결정한다. 그리고 그 위치에 저장된 LinkedList안에 저장하고자 하는 데이터가 있는지 판단한다. Set의 특성상 있다면 저장하지 않고 없다면 저장한다. 
• contains(int searchValue): 찾고자 하는 값이 존재하는지 판단하는 메서드. 해시값을 구하고 그 해시값을 인덱스로 배열의 위치를 결정한다. 그 위치에 저장된 LinkedList안에 찾고자 하는 데이터가 존재하는지 확인한다.
• remove(int value): 데이터를 지우는 메서드. 해시값을 구하고 그 해시값을 인덱스로 배열의 위치를 결정한다. 그 위치에 저장된 LinkedList안에 지우고자 하는 데이터를 찾아 (있다면) 지운다.
• getSize(): 저장된 전체 데이터의 개수를 반환한다.
• hashIndex(int value): 해시값을 구해내는 프라이빗 메서드. 주어진 값을 배열의 크기로 나머지 연산을 통해 해시값을 구한다.

모든 메서드가 전부 해시값을 구하고 그 해시값을 기반으로 데이터를 찾고, 저장하고, 삭제한다. 즉, 가장 핵심이 되는 건 해시값이다.

직접 실행해 보고 어떻게 되는지 한번 확인해 보자.

 

MyHashSetV1Main

package org.example.collection.set;

public class MyHashSetV1Main {
    public static void main(String[] args) {
        MyHashSetV1 set = new MyHashSetV1(10);
        set.add(1);
        set.add(2);
        set.add(5);
        set.add(8);
        set.add(14);
        set.add(99);
        set.add(9);
        System.out.println("set = " + set);

        int searchValue = 9;
        boolean ifContains = set.contains(searchValue);
        System.out.println("set.contains(" + searchValue + ") = " + ifContains);

        boolean removed = set.remove(searchValue);
        System.out.println("removed = " + removed);
        System.out.println("set = " + set);
    }
}

실행결과

set = MyHashSetV1{buckets=[[], [1], [2], [], [14], [5], [], [], [8], [99, 9]], size=7, capacity=10}
set.contains(9) = true
removed = true
set = MyHashSetV1{buckets=[[], [1], [2], [], [14], [5], [], [], [8], [99]], size=6, capacity=10}

 

해시값의 충돌 가능성을 인정하고 충돌이 날 경우 그 공간에 같이 데이터를 보관한다. 그리고 충돌의 확률은 배열의 크기에 따라 조정이 되기 때문에 적당한 충돌 관리를 잘한다면 이렇게 데이터를 잘 저장할 수 있다.

 

근데, 한 가지 의문이 생긴다. 지금의 구조로는 해시값은 나머지 연산을 통해 숫자를 뱉어낸다. 나머지 연산을 하기 위해선 항의 타입이 무조건 숫자여야 한다. 이것이 지금 구조에서 가장 큰 문제가 된다. 이것을 해결하기 위해 탄생한 게 자바의 hashCode().

 

자바의 hashCode()

해시 인덱스를 사용하는 해시 자료 구조는 추가, 검색, 삭제의 성능이 O(1)으로 매우 빠르다. 그래서 많은 곳에서 사용된다. 근데 해시 자료 구조를 사용하려면 앞에서 본 것처럼 정수로 된 숫자 값인 해시 코드가 필요한데, 자바에서는 int, Integer 뿐만 아니라 String, char, Double, Boolean 등 수많은 타입이 있다. 그뿐 아니라 개발자가 직접 정의한 Member, User와 같은 사용자 정의 타입도 있다. 이 모든 타입을 해시 자료 구조에 저장하려면 모든 객체가 숫자 해시 코드를 제공할 수 있어야 한다.

 

모든 타입이 숫자 해시 코드를 제공한다. 모든 타입의 부모 = Object. 그래서 Object가 hashCode()를 가지고 있는 것이다.

 

hashCode() 특징은 다음과 같다.

•  equals() 메서드처럼 재정의해야 한다.
  • 왜냐하면, 기본으로 제공되는 hashCode()는 참조값으로 해시값을 구하기 때문에 인스턴스가 다르면 다른 해시값을 반환해 버린다. IDE의 도움을 받아 hashCode() 재정의 하는 것은 너무 간단하다.
• equals()와 hashCode()는 같이 재정의해야 한다.
  • 결국 해시 기반 자료 구조에서 사용되는 가장 중요한 값인 해시값이 같다는 것은 논리적으로 같음을 의미한다. 그래서 equals()에서 논리적으로 같음을 판단하는 기준이 되는 모든 것들을 hashCode()에도 적용해줘야 한다. equals()만 재정의하고 hashCode()를 재정의하지 않으면 hashCode()는 Object가 기본으로 가지고 있는 hashCode()를 사용하는데 이때 사용하는 기준이 참조값뿐이기 때문에 equals()가 동일하다고 판단했음에도 hashCode()가 달라지는 문제가 생긴다. 그 결과 해시 기반 구조를 사용하는데 equals()만 재정의하고 hashCode()는 재정의하지 않는다면 논리적으로 같은 객체임에도 다른 해시값을 반환해 버려서 검색, 추가, 삭제 모든 연산에 문제가 생긴다. 물론 이 객체에 대해 해시 기반 자료 구조를 사용 안 하면 equals()만 재정의해도 크게 문제는 없다.
• equals()가 같다고 판단한 두 객체는 hashCode() 값이 무조건 같아야 하고 그 반대는 성립되지 않는다.
  • equals()가 같다고 판단한 두 객체는 논리적으로 같음을 의미한다. 그 얘기는 해시 기반 자료구조에서 자료를 저장할 때 이 두 객체는 무조건 같다는 판단이 나와야 한다. 근데 반대는? 해시 충돌이 일어났을 때 두 값이 같지 않아도 충돌은 일어날 수 있다.

 

이제 hashCode()에 대해서는 어느 정도 알아봤고 이 hashCode()를 사용해서 Set이라는 자료구조를 만들어 내보자.

 

MyHashSetV2

package org.example.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;
    private int capacity = DEFAULT_INITIAL_CAPACITY;

    public MyHashSetV2() {
        initBuckets(capacity);
    }

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

    private void initBuckets(int capacity) {
        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 removed = bucket.remove(value);
        if (removed) {
            size--;
            return true;
        }
        return false;
    }

    public int getSize() {
        return size;
    }

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

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

 

가장 핵심적으로 바뀌는 부분은 hashIndex(Object value) 메서드이다. 기존에는 저장하고자 하는 모든 데이터를 정수형으로만 취급했기 때문에 상관이 없었지만 정수형뿐만 아니라 모든 타입으로도 이 Set이라는 자료구조는 자료를 담을 수 있어야 한다. 그런데 그때 해시값을 구하는 메서드가 hashCode()가 되는 것이다. 

 

근데 자세히 보면, Math.abs(value.hashCode()) % capacity; 이렇게 되어 있다. 이 이유는 hashCode()는 음수가 나올 수 있기 때문이다. 하지만, 배열에서는 음수값인 인덱스는 없으니까 절댓값을 사용해야 한다.

 

그럼 이제 대표적으로 add() 메서드를 주의 깊게 봐보자.

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

• int hashIndex = hashIndex(value); : 먼저 넣고자 하는 값의 해시값을 구한다.
• LinkedList<Object> bucket = buckets[hashIndex]; : 그 해시값으로 배열의 특정 인덱스를 선택하게 된다. 그래서 해당 인덱스로 가보면 LinkedList가 있다.
• if (bucket.contains(value)) : 그 LinkedList에서 내가 추가하고자 하는 값이 있는지를 확인한다. 이 contains() 메서드 내부적으로 equals()를 사용할 거다.
• 이미 있다면 추가하지 않고 `false`를 반환하고 없다면 추가한 후 사이즈를 하나 증가한 후 `true`를 반환한다.

 

결론은 해시 기반 자료 구조를 사용하려면 반드시 hashCode(), equals() 동시에 재정의해야 한다. hashCode()는 해당 객체에 대한 해시코드를 반환한다. 근데 그 해시코드를 만들어내는 기준들이 equals()가 논리적으로 동등하다고 판단하는 모든 기준들과 일치해야 한다. 그래야 인스턴스가 달라도 논리적으로 같으면 같은 해시코드를 내뱉을 것이고 그래야 이미 그 데이터가 자료구조에 저장이 되어 있는지 판단할 수 있다. 그리고 여기서 판단은? equals() 메서드로 하게 된다. 그렇기 때문에 해시 기반 자료 구조에서 검색, 추가, 삭제와 같은 작업을 정상적으로 수행하려면 hashCode(), equals() 둘 다 오버라이딩 해야 한다는 것.

 

참고로, String, Boolean, Double 이런 래퍼 클래스는 자바가 미리 equals()와 hashCode()를 우리 대신 다 구현해놨다.

 

이제 모든 타입을 받아줄 수 있는 HashSet을 직접 만들어 봤다. 만들어 놓고 나니 왜 hashCode()와 equals()를 IDE의 도움을 받아 만들 때 같이 만들어지는지 알게 됐고, 어떻게 해서 해시값을 활용해서 데이터를 저장하고 검색하는지 알게 됐다. 여기에 하나 더, 이렇게 해시값을 이용하면 굉장히 성능이 좋은 자료구조가 된다는 것도.

 

equals()와 hashCode()를 제대로 구현하지 않았을 때 발생하는 문제 확인해보기

말만 하면 이해가 잘 안되니 직접 이 문제의 상황을 만들어서 어떤 문제가 발생하는지 확인해보자. 경우의 수는 3가지다.

• 둘 다 구현 안했을 때
• equals()만 구현했을 때
• hashCode()만 구현했을 때

둘 다 구현 안했을 때

MemberNoHashNoEq

package org.example.collection.set.member;

public class MemberNoHashNoEq {
    private String id;

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

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

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

이 클래스는 둘 다 구현하지 않은 케이스이다. 한번 어떻게 되는지 보자. 

 

HashAndEqualsMain1

package org.example.collection.set.member;

import org.example.collection.set.MyHashSetV2;

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 = " + set);

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

실행결과

m1.hashCode() = 112810359
m2.hashCode() = 205029188
m1.equals(m2) = false
set = MyHashSetV2{buckets=[[], [], [], [], [], [], [], [], [MemberNoHashNoEq{id='A'}], [MemberNoHashNoEq{id='A'}]], size=2, capacity=10}
searchValue.hashCode() = 1265094477
set.contains(MemberNoHashNoEq{id='A'}) = false

 

Member라는 객체를 만들 때 약속하기를 ID가 같은 객체를 논리적으로 동등한 것으로 판단하기로 했다. 그러나 equals(), hashCode()를 둘 다 구현하지 않았다. 그러고 해시 기반 자료 구조에 저장을 한다면 중복으로 저장된다. Set은 중복으로 저장될 수 없다. 첫번째 문제가 발생한 것.

 

그리고 문제는 끝나지 않았다. 검색에도 실패한다. 논리적으로 같음에도 hashCode()를 재정의하지 않았기에 다른 해시 코드 결과를 뱉어내고 뱉어낸 해시코드로 해시값을 구해 인덱스로 찾아가도 내가 찾고자하는 객체는 없다. 정말 운이 좋아서 해시 코드 값이 나머지 연산시 동일한 값으로 나왔다고 해도 검색에 실패한다. 왜냐? equals()를 재정의하지 않았으니까.

 

hashCode()만 구현했을 때

이번엔 equals()를 구현하지 않고 hashCode()만 구현했을 때를 보자.

 

MemberOnlyHashCode

package org.example.collection.set.member;

import java.util.Objects;

public class MemberOnlyHashCode {
    private String id;

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

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

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

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

 

HashAndEqualsMain2

package org.example.collection.set.member;

import org.example.collection.set.MyHashSetV2;

public class HashAndEqualsMain2 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2(10);

        MemberOnlyHashCode m1 = new MemberOnlyHashCode("A");
        MemberOnlyHashCode m2 = new MemberOnlyHashCode("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 = " + set);

        MemberOnlyHashCode searchValue = new MemberOnlyHashCode("A");
        System.out.println("searchValue.hashCode() = " + searchValue.hashCode());

        // 검색에 실패한다.
        boolean ifContains = set.contains(searchValue);
        System.out.println("set.contains(" + searchValue + ") = " + ifContains);
    }
}

실행결과:

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

 

이젠 해시코드는 구현했기 때문에 논리적으로 같은 기준이라면 같은 해시코드를 반환한다. 그래서 결과를 보면 m1, m2의 해시코드가 동일하다. 그러니까 당연히 해시값을 통해 구해낸 인덱스는 같은 곳이지만 둘 다 들어간다. 왜냐? equals()를 구현하지 않았기 때문에 Object가 가지고 있는 `==`비교를 하게 된다. 당연히 논리적으로 같아도 참조값은 다르기 때문에 두 객체를 동일하다고 판단하지 않고 둘 다 넣어버리는 것이다. 검색도 마찬가지로 안된다. 역시나 equals()를 구현하지 않았으니까.

 

equals()만 구현했을 때

마찬가지로 문제가 될 것이다.

MemberOnlyEq

package org.example.collection.set.member;

import java.util.Objects;

public class MemberOnlyEq {
    private String id;

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

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

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

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

 

HashAndEqualsMain3

package org.example.collection.set.member;

import org.example.collection.set.MyHashSetV2;

public class HashAndEqualsMain3 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2(10);

        MemberOnlyEq m1 = new MemberOnlyEq("A");
        MemberOnlyEq m2 = new MemberOnlyEq("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 = " + set);

        MemberOnlyEq searchValue = new MemberOnlyEq("A");
        System.out.println("searchValue.hashCode() = " + searchValue.hashCode());

        // 검색에 실패한다.
        boolean ifContains = set.contains(searchValue);
        System.out.println("set.contains(" + searchValue + ") = " + ifContains);
    }
}

실행결과

m1.hashCode() = 112810359
m2.hashCode() = 205029188
m1.equals(m2) = true
set = MyHashSetV2{buckets=[[], [], [], [], [], [], [], [], [MemberNoHashNoEq{id='A'}], [MemberNoHashNoEq{id='A'}]], size=2, capacity=10}
searchValue.hashCode() = 1265094477
set.contains(MemberNoHashNoEq{id='A'}) = false

 

실행 결과를 보면 equals()를 구현했으니 두 객체는 동등하다고 나오지만, 해시코드가 다른 값을 뱉는다. 그 말은 해시값이 달라지고 그 말은 인덱스가 서로 다르기 때문에 equals() 비교자체를 하지 않고 둘 다 넣어버리게 된다. 결국 이 상황도 중복으로 데이터가 저장되고 검색도 안되는 문제가 여전히 생긴다.

 

결론, 해시 자료구조를 사용한다면 둘 다 꼭 재정의하자.

 

이제 마지막으로 남은 제네릭을 사용해서 HashSet을 완성시켜보자.

Set 인터페이스

package org.example.collection.set;

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

Set 구현 클래스

package org.example.collection.set;

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

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

    private final int DEFAULT_CAPACITY = 16;
    private LinkedList<E>[] buckets;
    private int size;
    private int capacity = DEFAULT_CAPACITY;

    public MyHashSet() {
        initBucket();
    }

    public MyHashSet(int capacity) {
        this.capacity = capacity;
        initBucket();
    }

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

    private int hash(E element) {
        return Math.abs(element.hashCode()) % capacity;
    }

    @Override
    public boolean add(E element) {
        int hashIndex = hash(element);
        LinkedList<E> bucket = buckets[hashIndex];
        if (bucket.contains(element)) {
            return false;
        }
        bucket.add(element);
        size++;
        return true;
    }

    @Override
    public boolean remove(E element) {
        int hashIndex = hash(element);
        LinkedList<E> bucket = buckets[hashIndex];

        boolean removed = bucket.remove(element);
        if (removed) {
            size--;
            return true;
        }
        return false;
    }

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

    @Override
    public int size() {
        return size;
    }

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

제네릭까지 마무리지어서 완전한 Set을 직접 구현해봤다. 앞으로는 절대 직접 구현할 일 없고 자바가 잘 만들어둔 좋은 Set을 사용하면 된다. 그래도 어떤 동작원리로 어떻게 자료를 저장하는지 직접 구현해보는 게 굉장히 뜻깊은 시간이라고 생각한다.

자바가 제공하는 Set

자바가 제공하는 Set은 크게 3가지가 있다.

• HashSet
• LinkedHashSet
• TreeSet

HashSet은 직접 구현한 Set과 거의 동일하고 추가적인 기능이나 성능 최적화가 훨씬 잘 되어 있는 정도다.

LinkedHashSet은 HashSet이긴 한데 데이터끼리 전과 후를 알고 있다. 말 그대로 `Linked`HashSet인데, 이렇게 만든 이유는 Set은 순서가 보장되지 않는데 이 LinkedHashSet은 순서를 보장해준다.

TreeSet은 Binary Search Tree 구조로 저장되는 Set이다. 

그래서 TreeSet을 사용할 경우엔 데이터의 정렬 기준에 맞게 조회한다. 3, 1, 2 이렇게 데이터가 들어가 있으면 1, 2, 3 순서로 조회가 된다는 뜻이다.

 

보통은 HashSet을 가장 많이 사용하고 Set의 근본 목적인 '중복값을 허용하지 않는다'에 초점을 두기 때문에 순서가 반드시 보장되어야 한다면 Array, List, LinkedHashSet을 사용하는 것이 일반적이다.