HashSet

개요

Set은 중복을 허용하지 않고, 순서를 보장하지 않는 자료 구조이다.
따라서 이를 구현하는 방법은 단순하다. 인덱스가 없기 때문에 단순히 데이터를 저장하고, 데이터가 있는지 확인하고, 데이터를 삭제하는 정도면 된다. 그리고 중복을 허용하지 않기 때문에 데이터를 추가할 때 중복 여부를 체크하면 된다.

• add(value): set에 값을 추가한다. 중복 데이터는 저장하지 않는다.
• contains(value): set에 값이 있는지 확인한다.
• remove(value): set에 있는 값을 제거한다.

MyHashSetV0의 문제점

Set을 구현한 다음 MyHashSetV0 버전의 코드의 문제는 데이터를 추가할 때 중복 데이터가 있는지 체크하는 부분에서 성능이 O(n)으로 좋지 않다는 점이다. 왜냐하면 이때 중복 데이터가 있는지 모든 데이터를 다 찾아봐야 하기 때문이다. 이와 같은 맥락으로 모든 데이터를 찾을 때도 모두 순서대로 전체 데이터를 확인해야 하므로 평균 성능이 O(n)으로 좋지 않다. 이러한 MyHashSetV0를 해시 알고리즘을 사용해서 평균 O(1)로 개선해보고자 한다.

package src.set.v0;

import java.util.Arrays;

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

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

MyHashSetV1

클래스 코드

package src.set.v1;

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

    public boolean add(int value) {
        int hashIndex = getHashIndex(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 = getHashIndex(searchValue);
        LinkedList<Integer> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }

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

    public int getSize() {
        return size;
    }

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

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

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

main method

package src.set.v1;

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); // hashIndex 중복
        System.out.println(set);

        // 검색
        int searchValue = 9;
        boolean result = set.contains(searchValue);
        System.out.println("set.contains(" + searchValue + ") = " + result);

        // 삭제
        boolean removeResult = set.remove(searchValue);
        System.out.println("removeResult = " + removeResult);
        System.out.println(set);
    }
}

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

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

그런데 해시 인덱스를 사용하면 데이터의 값을 배열의 인덱스로 사용해야 한다. 그런데 배열의 인덱스는 0, 1, 2 같은 숫자만 사용할 수 있는데, 그렇다면 A, B같은 문자열 데이터를 저장할 때 해시 인덱스를 사용하려면 어떻게 해야할까?

문자열 해시 코드

컴퓨터는 문자를 직접 이해하지 못한다. 대신에 각 문자에 고유한 숫자를 할당해서 인식한다. 예를 들어, A는 65, B는 66으로 표현되며, 이를 확인하기 위해서는 char형을 int형으로 캐스팅하면 문자의 고유한 숫자를 확인할 수 있다. 그리고 AB와 같은 연속된 문자는 각각의 문자를 더하는 방식으로 숫자로 표현하면 된다. 즉, 65 + 66 = 131이다.

package src.set.hash_algorithm;

public class StringHashMain {
    static final int CAPACITY = 10;

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

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

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

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

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

용어 정리

해시 코드(Hash Code)

해시 코드는 데이터를 대표하는 값을 뜻한다. 이는 해시 함수를 통해 만들어진다. 예를 들어, 데이터 A의 해시 코드는 65이다.

해시 함수(Hash Function)

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

해시 인덱스(Hash Index)

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

자바의 hashCode()

해시 인덱스를 사용하는 해시 자료 구조는 데이터 추가, 검색, 삭제의 성능이 O(1)로 매우 빠르다. 그런데 이러한 해시 자료 구조를 사용하려면 정수로 된 숫자 값인 해시 코드가 필요하고, 자바에는 정수 int, Integer 뿐만 아니라 char, String, Double, Boolean, Member, User 등 수 많은 타입이 있다. 따라서 이 모든 타입을 해시 자료 구조에 저장하려면 모든 객체가 숫자 해시 코드를 제공할 수 있어야 한다.

Object.hashCode()

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

public class Object {
    public int hashCode();
}

• 이 메서드는 보통 Overriding 해서 사용한다.
• 이 메서드의 기본 구현은 객체의 참조값을 기반으로 해시 코드를 생성한다.
• 즉, 객체의 인스턴스가 다르면 해시 코드도 다르다.

IDE가 제공하는 자동 완성 기능을 사용해서 equals(), hashCode()를 생성하면, Member의 id값을 기준으로 equals 비교를 하고, hashCode도 생성한다.

package src.set.member;

import java.util.Objects;

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

package src.set.hash_algorithm;

import src.set.member.Member;

public class JavaHashAlgorithm {
    public static void main(String[] args) {
        // Object의 기본 hashCode는 객체의 참조값을 기반으로 생성한다.
        Object obj1 = new Object();
        Object obj2 = new Object();
        System.out.println("obj1.hashCode() = " + obj1.hashCode());
        System.out.println("obj2.hashCode() = " + obj2.hashCode());

        // 각 클래스들은 hashCode를 기본적으로 오버라이딩 해놨다.
        Integer i = 10;
        String strA = "A";
        String strAB = "AB";
        System.out.println("10.hashCode() = " + i.hashCode());
        System.out.println("A.hashCode() = " + strA.hashCode());
        System.out.println("AB.hashCode() = " + strAB.hashCode());

        // hashCode는 - 값이 들어올 수 있다.
        System.out.println("-1.hashCode() = " + Integer.valueOf(-1).hashCode());

        // 둘의 인스턴스는 다르지만, equals는 같다.
        Member member1 = new Member("idA");
        Member member2 = new Member("idA");

        System.out.println("(member1 == member2) = " + (member1 == member2));
        System.out.println("member1.equals(member2) = " + member1.equals(member2));
        System.out.println("member1.hashCode() = " + member1.hashCode());
        System.out.println("member2.hashCode() = " + member2.hashCode());
    }
}

Member는 hashCode()를 id 기반으로 재정의했고, 그 덕분에 인스턴스가 달라도 id값이 다르면 같은 해시 코드를 반환한다. 따라서 인스턴스가 다른 member1, member2 둘 다 같은 해시 코드를 반환하는 것을 확인할 수 있다.

정리하면, 자바가 기본으로 제공하는 클래스 대부분은 hashCode()를 재정의해두었으며, 객체를 직접 만들어야 하는 경우에는 hashCode()를 재정의하면 된다. 이 메서드만 재정의하면 필요한 모든 종류의 객체를 해시 자료 구조에 보관할 수 있다. 따라서 해시 자료 구조에 데이터를 저장하는 경우, hashCode()를 구현하면 된다.

MyHashSetV2

이번에는 Set에 모든 타입을 저장할 수 있도록 구현해보자. hashIndex() 메서드가 바뀌었는데, 해시 코드를 기반으로 해시 인덱스를 계산해서 반환한다.

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

package src.set.v2;

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

public class MyHashSetV2 {
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    LinkedList<Object>[] buckets;

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

    public MyHashSetV2() {
        initBuckets();
    }

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

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

    public int getSize() {
        return size;
    }

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

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

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

👉 String의 hashCode는 각 문자의 유니코드 값에 31을 누적 곱한 다항식이다. 예를 들면, "S"+"E"+"T"의 해시코드는 S = 83, E = 69, T = 84이므로, hash = (31_0 + 83) + ((31_0 + 83)_31 + 69) + (((31_0 + 83)_83 + 69)_31 + 84) = 81955 이다.

MyHashSetV3

MyHashSetV2는 Object를 받을 수 있다. 따라서 직접 만든 Member와 같은 객체도 보관할 수 있는데, 이때 반드시 직접 만든 객체는 hashCode(), equals() 두 메서드를 구현해야 한다.
아래 코드에서는 Member의 hashCode()를 id 값을 기반으로 재정의해 두었으므로, MyHashSetV2에서 hashIndex(Object value)에서 value.hashCode()를 호출하면 실제로는 Member에서 재정의한 hashCode()가 호출된다. 이렇게 반환된 해시 코드를 기반으로 해시 인덱스를 생성하는 것이다.
마지막으로 JPA를 조회할 때, 해시 인덱스는 0이므로, 배열의 0번 인덱스를 조회한다. 이 0번 인덱스에는 [hi, JPA]라는 2명의 회원이 있다. 이 것들을 하나하나 비교할 때, equals()를 사용해서 비교하게 된다. 따라서 해시 자료 구조를 사용할 때는 hashCode()는 물론이고, equals()도 반드시 재정의해야 하는 것이다. 물론 자바로 제공하는 기본 클래스들은 대부분이 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 + '\'' +
                '}';
    }
}

public class MyHashSetV2 {
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    LinkedList<Object>[] buckets;

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

    public MyHashSetV2() {
        initBuckets();
    }

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

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

    public int getSize() {
        return size;
    }

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

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

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

// 직접 만드는 객체를 Set에 보관
public class MyHashSetV3Main2 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2(10);
        Member hi = new Member("hi");
        Member jpa = new Member("JPA");
        Member java = new Member("java");
        Member spring = new Member("spring");

        System.out.println("hi.hashCode() = " + hi.hashCode());
        System.out.println("jpa.hashCode() = " + jpa.hashCode());
        System.out.println("java.hashCode() = " + java.hashCode());
        System.out.println("spring.hashCode() = " + spring.hashCode());

        set.add(hi);
        set.add(jpa);
        set.add(java);
        set.add(spring);
        System.out.println(set);

        Member searchValue = new Member("JPA");
        boolean result = set.contains(searchValue);
        System.out.println("set.contains(" + searchValue + ") = " + result);
    }
}

hi.hashCode() = 3360
jpa.hashCode() = 73690
java.hashCode() = 3254849
spring.hashCode() = -895679956
MyHashSetV2{buckets=[[Member{id='hi'}, Member{id='JPA'}], [], [], [], [], [], [Member{id='spring'}], [], [], [Member{id='java'}]], size=4}
set.contains(Member{id='JPA'}) = true

equals, hashCode의 중요성

이번 절에서는 hashCode(), equals()를 제대로 구현하지 않으면 어떤 문제가 발생하는지 알아보고자 한다.
그 전에 먼저 Object의 기본 기능은 다음과 같은데, 만약에서 클래스를 만들 때 hashCode(), equals()를 재정의하지 않으면, 해시 지료 구조에서 Object가 기본으로 제공하는 hashCode(), equals()를 사용하게 되고, Object가 기본으로 제공하는 단순 인스턴스 참조를 기반으로 동작하게 된다.

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

그럼 이제 hashCode, equals를 제대로 구현하지 않은 경우에 발생하는 문제를 알아보자.

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

다음 코드에서 m1.hashCode(), m2.hashCode()는 Object의 기본 기능을 사용하기 때문에 객체의 참조값을 기반으로 해시 코드를 생성한다. 따라서 실행할 때마다 값이 달라질 수 있다. 따라서 각 객체의 해시 코드가 서로 다르기 때문에 set.add시 각기 다른 위치에 저장된다. 또한 searchValue객체의 해시 코드 또한 다른 값이 나와 검색에 실패한다.

public class HashAndEqualsMain1 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2();
        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() = 1175962212
m2.hashCode() = 798154996
m1.equals(m2) = false
MyHashSetV2{buckets=[[], [], [], [], [MemberNoHashNoEq{id='A'}, MemberNoHashNoEq{id='A'}], [], [], [], [], [], [], [], [], [], [], []], size=2}
searchValue.hashCode() = 1067040082
contains = false

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

이번에는 hashCode()만 재정의하고, equals()는 재정의하지 않는 경우에 어떤 문제가 발생하는지 알아보자.
hashCode()를 재정의했기 때문에 같은 id를 사용하는 m1, m2는 같은 해시 코드를 사용한다. 따라서 같은 인덱스에 데이터가 저장된다.
하지만 add() 로직은 중복 데이터를 체크하는데, 이때, bucket.contains() 내부에서 데이터를 순차 비교할 때 equals()를 사용한다. 하지만 MemberOnlyHash는 equals()를 재정의하지 않았으므로 Object의 equals()를 상속 받아서 사용한다. 따라서 인스턴스의 참조값으로 비교하므로, 인스턴스가 서로 다른 m1, m2는 비교에 실패한다.

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

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() = 65
m2.hashCode() = 65
m1.equals(m2) = false
MyHashSetV2{buckets=[[], [], [], [], [], [MemberOnlyHash{id='A'}, MemberOnlyHash{id='A'}], [], [], [], []], size=2}
searchValue.hashCode() = 65
contains = false

hashCode와 equals를 모두 구현한 경우

이번에는 hashCode()와 equals() 모두 재정의한 경우를 알아보자.
처음에 m1을 저장하고, m2 저장을 시도한다. 이때, m1과 같은 해시 코드를 사용하므로 해시 인덱스도 같고, 데이터 저장시 equals를 사용해 비교한다. 여기서 같은 데이터가 이미 있으므로 m2는 저장에 실패한다. 따라서 결과적으로 중복 데이터가 저장되지 않는다.

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

public class HashAndEqualsMain3 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2(10);
        Member m1 = new Member("A");
        Member m2 = new Member("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);

        // 검색 성공
        Member searchValue = new Member("A");
        boolean contains = set.contains(searchValue);
        System.out.println("contains = " + contains);
    }
}

정리

물론 hashCode()를 항상 재정의해야 하는 것은 아니다. 하지만 해시 자료 구조를 사용하는 경우, hashCode()와 equals()를 반드시 함께 재정의해야 한다.
또한 해시 함수는 해시 코드가 최대한 충돌하지 않게 설계해야 하는데, 왜냐하면 다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있기 때문이다. 이를 해시 충돌이라고 한다. 자바의 해시 함수는 이러한 해시 충돌을 최대한 피하기 위해 내부에서 복잡한 추가 연산을 수행한다. 덕분에 다양한 범위의 해시 코드가 만들어지므로 해시가 충돌할 가능성이 낮아지고, 결과적으로 해시 자료 구조를 사용할 때 성능이 개선된다.
다만 해시 함수는 같은 입력에 대해서는 항상 동일한 해시 코드를 반환해야 하고, 좋은 해시 함수는 해시 코드가 한 곳에 뭉치지 않고 균일하게 분포해주는 것이 좋다. 그래야 해시 인덱스도 골고루 분포되어서 해시 자료 구조의 성능을 최적화할 수 있기 때문이다.

제네릭과 인터페이스 도입

마지막으로 Set에 제네릭을 도입해서 타입 안정성을 높여보자. 먼저 핵심 기능을 뽑아서 interface를 만들었다. 그 후 이 인터페이스를 구현하면 해시 기반이 아니라 다른 자료 구조 기반으릐 Set도 만들 수 있게 된다.

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

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

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

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

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

    public int getSize() {
        return size;
    }

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

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

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

package src.set.v4;

public class MyHashSetV4Main {
    public static void main(String[] args) {
        MyHashSetV4<String> set = new MyHashSetV4<>(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("result = " + result);
    }
}

MyHashSetV3{buckets=[[], [], [], [], [], [A], [B], [C], [], []], size=3, capacity=10}
result = true