[Java] 김영한의 자바 중급 2편 #7 - HashSet

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

1. 직접 구현하는 Set1 - MyHashSetV1

이전에 구현한 성능이 O(n)으로 느린 MyHashSetV0를 다시 한번 확인해보자.

1.1. 단점

• add() 사용 시 중복 데이터가 있는지 전체 데이터를 항상 확인해야 한다. → o(n)
• contains()로 데이터를 찾을 때는 Set에 있는 모든 데이터를 찾고 비교해야 하므로 평균 O(n)이 걸린다.

→ 데이터를 추가할 때 중복 데이터가 있는지 체크하는 부분에서 성능이 o(n)으로 좋지 않다.

→ 이 부분을 평균 O(1)로 개선해보자.

1.2. 해시 알고리즘을 사용하도록 변경

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];    // 1. 바구니 가져오기
        if (bucket.contains(value)) {                       // 2. 바구니에 이미 있는지 확인
            return false;
        }

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

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

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

Main

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

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

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

// result
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}

1.2.1. 결과

• 생성 : new MyHashSetV1(10)을 사용하여 배열의 크기를 10으로 지정했음
• 저장 : 99, 9의 경우 해시 인덱스가 9로 충돌한다. 따라서 배열의 같은 9번 인덱스 위치에 저장된 것을 확인할 수 있다. 그리고 그 안에 있는 LinkedList에 99, 9가 함께 저장된다.
• 검색 : 9를 검색하는 경우에는 다음의 과정으로 검색한다.
  • 해시 인덱스 9를 구한다.
  • 9번 인덱스에 있는 연결 리스트를 찾는다.
  • 연결 리스트를 순서대로 비교하면서 9를 찾는다.
    • 99와 9를 비교할 때 실패하고, 9와 9를 비교할 때 성공하여 true를 반환하게 된다.

1.2.2. 문제점

현재 MyHashSetV1의 경우 A, B와 같은 문자열은 배열의 인덱스로 사용할 수 없다.

따라서 숫자가 아닌 문자열 데이터를 저장할 때 해시 인덱스를 사용하려면 어떻게 해야 할까?

2. 문자열 해시 코드

다음 코드를 통해 문자를 숫자로 변경하는 방법에 대해 알아보자.

package collection.set;

public class StringHashMain {

    static final int CAPACITY = 10;

    public static void main(String[] args) {

        // 1. char : 각 문자는 고유한 아스키 코드 값을 가지고 있다.
        char charA = 'A';
        char charB = 'B';
        System.out.println(charA + " = " + (int) charA);
        System.out.println(charB + " = " + (int) charB);

        // 2. hashCode : 문자열을 받아서 각 문자의 아스키 코드 값을 더한 값을 반환할 수 있다.
        System.out.println("hashCode(A) = " + hashCode("A"));
        System.out.println("hashCode(B) = " + hashCode("B"));
        System.out.println("hashCode(AB) = " + hashCode("AB"));

        // 3. hashIndex : hashCode를 통해 반환된 값을 CAPACITY로 나눈 나머지 값을 반환할 수 있다.
        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 % CAPACITY;
    }
}

// result
A = 65
B = 66

hashCode(A) = 65
hashCode(B) = 66
hashCode(AB) = 131

hashIndex(A) = 5
hashIndex(B) = 6
hashIndex(AB) = 1

2.1. 아이디어

• 모든 문자는 본인만의 고유한 숫자로 표현된다 → ASCII 코드
• 연속된 문자는 각각의 문자를 더하는 방식으로 고유한 숫자(?)로 표현될 수 있다.
• 이 고유한 숫자를 구하면 hashIndex를 구할 수 있게 된다.

2.2. hashCode와 hashIndex

 

• hashCode() 메서드를 사용해서 문자열을 해시 코드로 변경한다. → 해시 코드를 구함
• 숫자 값인 해시 코드를 사용해서 해시 인덱스를 생성한다.
• 이렇게 생성된 해시 인덱스를 배열의 인덱스로 사용할 수 있게 된다.

2.3. 용어 정리

해시 함수(Hash Function) : 임의의 길이의 데이터를 입력으로 받아, 고정된 길이의 해시값을 출력하는 함수이다.

• 같은 데이터를 입력하면 항상 같은 해시 코드가 출력된다.
• 다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있다. → 이것을 해시 충돌이라고 한다.

해시 코드(Hash Code) : 데이터를 대표하는 값을 뜻하며 보통 해시 함수를 통해 만들어진다.

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

3. 자바의 hashCode()

해시 인덱스를 사용하는 해시 자료 구조는 데이터 추가, 검색, 삭제의 성능이 O(1)로 매우 빠르기 때문에 많은 곳에서 사용되는데 이 해시 자료 구조를 사용하려면 정수로 된 숫자 값인 해시 코드가 필요하다.

자바에서는 Integer, char, String, Double, Boolean 등 수 많은 타입이 있으며 이 뿐만 아니라 개발자가 직접 정의한 Member, User와 같은 사용자 정의 타입도 존재한다.

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

3.1. Object.hashCode()

자바는 모든 객체가 자신만의 해시 코드를 표현할 수 있는 기능을 제공하는데 바로 Object 클래스에 있는 hashCode() 메서드이다.

public class Object{
	public int hashCode();
}

3.2. 코드 구현해보기

Member Class

package collection.set.member;

import java.util.Objects;

public class Member {
    private String id;

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

    public String getId() {
        return id;
    }

    // IDE가 자동으로 생성한 equals()와 hashCode() 메소드
    @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 + '\\'' +
                '}';
    }
}

JavaHashCodeMain

package collection.set;

import collection.set.member.Member;

public class JavaHashCodeMain {

    public static void main(String[] args) {

        // 1. Object의 기본 hashCode는 객체의 메모리 주소를 기반으로 생성된다.
        Object obj1 = new Object();
        Object obj2 = new Object();
        System.out.println("obj1.hashCode() = " + obj1.hashCode());
        System.out.println("obj2.hashCode() = " + obj2.hashCode());

        // 2. 각 클래스마다 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());

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

        // 4. 직접 정의한 Member 클래스에서는 id 값을 기반으로 hashCode를 생성하도록 오버라이딩 했다.
        // 따라서 인스턴스는 다르지만, id 값이 같은 경우에 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());
    }

}

// result
obj1.hashCode() = 1175962212
obj2.hashCode() = 798154996
10.hashCode = 10
'A'.hashCode = 65
'AB'.hashCode = 2081
-1.hashCode = -1
(member1 == member2) =false
member1 equals member2 = true
member1.hashCode() = 104101
member2.hashCode() = 104101

• Object의 해시 코드 : Object가 기본으로 제공하는 hashCode()는 객체의 참조값을 해시 코드로 사용한다. 따라서 각각의 인스턴스마다 서로 다른 값을 반환한다.
• 자바의 기본 클래스들의 해시 코드
  • Integer, String 같은 자바의 기본 클래스들은 대부분 내부 값을 기반으로 해시 코드를 구할 수 있도록 hashCode()가 오버라이딩 되었다.
  • 따라서 데이터의 값이 같으면 같은 해시 코드가 반환된다.
  • 해시 코드의 경우 정수를 반환하기 때문에 마이너스 값이 나올 수 있다.

 

 

• 직접 구현하는 해시 코드
  • Member의 경우 id가 같을 경우 논리적으로 같은 회원으로 표현할 수 있다. 따라서 회원 id를 기반으로 동등성일 비교하도록 equals를 재정의해야 한다.
  • 여기에 hashCode()도 같은 원리가 적용된다. 회원 id가 같으면 논리적으로 같은 회원으로 표현할 수 있다. 따라서 회원 id를 기반으로 해시 코드를 생성해야 한다.

Member의 hashCode() 구현

• Member는 hashCode()를 재정의했다.
• hashCode()를 재정의할 때 Objects.hash()가 기본으로 제공하는 hashCode()를 사용하게 되는데 이것은 객체의 참조값을 기반으로 해시 코드를 제공하게 된다. 따라서 회원의 id가 같아도 인스턴스가 다르면 다른 해시 코드를 반환하게 된다.
  • hashCode()를 id 기반으로 재정의하게 되면 인스턴스가 달라도 id 값이 같으면 같은 해시 코드를 반환하게 된다.
  • 따라서 인스턴스가 다른 member1, member2 둘 다 같은 해시 코드를 반환하는 것을 확인할 수 있다.

3.3. 동일성과 동등성 비교

Object는 동등성 비교를 위한 equals() 메서드를 제공한다.

• 동일성(Identity) : == 연산자를 사용해서 두 객체의 참조가 동일한 객체를 가리키고 있는지 확인 → 물리적으로 같은 메모리에 있는 객체인지 참조값 확인
• 동등성(Equality) : equals() 메서드를 사용해서 두 객체가 논리적으로 동등한지 확인 → 논리적으로 같은지 확인

4. 직접 구현하는 MyHashSetV2

모든 타입을 저장할 수 있는 Set을 만들어본ㅂ다.

자바의 hashCode()를 구하면 타입과 관계없이 해시 코드를 편리하게 구할 수 있다.

package collection.set;

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;

    }
}

• buckets 링크드리스트
  • Object를 저장함으로써 모든 타입을 사용한다.
  • 저장, 검색, 삭제 메서드의 매개변수도 Object로 변경
• hashIndex()
  • Object의 hashCode()를 호출해서 해시 코드를 찾는다. 그리고 찾은 해시 코드를 배열의 크고(capacity)로 나머지 연산을 수행하여 해시 인덱스를 계산해서 반환한다.
  • Object의 hashCode()를 사용한 덕분에 모든 객체의 hashCode()를 구할 수도 있다.
  • hashCode의 실행 결과로 음수가 나올 수 있는데, 배열의 인덱스로 음수는 사용할 수 없다. Math.abs()를 사용하면 마이너스를 제거하여 항상 양수를 얻을 수 있다.

Main 코드

package collection.set;

public class MyHashSetV2Main1 {

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

        set.add("A");
        set.add("B");
        set.add("C");
        set.add("D");
        set.add("AB");
        set.add("SET");
        System.out.println(set);

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

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

// result
MyHashSetV2{buckets=[[], [AB], [], [], [], [A], [B, SET], [C], [D], []], size=6, capacity=10}
A.hashCode=65
B.hashCode=66
AB.hashCode=2081
SET.hashCode=81986
set.contains(SET) = true

 

 

• 자바의 String은 hashCode()를 오버라이딩해두었음 (자바의 해시 함수는 단순히 문자들을 더하기만 하는 것이 아니라 더 복잡한 연산을 사용해서 해시 코드를 구한다.)
• hashIndex(Object value)에서 value.hashCode()를 호출하면 실제로 String에서 재정의한 hashCode()가 호출된다.
• 이렇게 반환된 해시 코드를 기반으로 해시 인덱스를 생성한다.

5. 직접 구현하는 MyHashSetV2 - 직접 만든 객체 보관

MyHashSetV2는 Object를 받을 수 있다. 따라서 직접 만든 Member와 같은 객체도 보관할 수 있다.

<주의 사항>

• hashCode(), equals() 메서드는 반드시 오버라이딩해야 한다.

Main 코드

package collection.set;

import collection.set.member.Member;

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

        // Member 객체 생성 : hi, jpa, java, spring
        Member hi = new Member("hi");
        Member jpa = new Member("JPA");
        Member java = new Member("java");
        Member spring = new Member("spring");

        // 1. hashCode() 조회
        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());

        // 2. 직접 구현한 MyHashSetV2에 추가
        set.add(hi);
        set.add(jpa);
        set.add(java);
        set.add(spring);
        System.out.println(set);

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

// 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, capacity=10}
set.contains(Member{id='JPA'}) = true

 

 

 

• Member의 hashCode()를 id 값을 기반으로 오버라이딩 했음
  • hashIndex(Object value)에서 value.hashCode()를 호출하면 실제로 Member에서 재정의한 hashCode()가 호출된다.
  • 이렇게 반환된 해시 코드를 기반으로 해시 인덱스를 생성한다.

equals() 사용처

특정 값을 조회할 때 hashCode()를 통해 구한 인덱스에 저장되어 있는 데이터들을 하나하나 비교해봐야 한다. 이 때 equals() 메서드를 사용해서 비교한다.

그렇기 때문에 hashCode()는 물론이고 equals() 메서드도 재정의해야 한다.

6. equals, hashCode 중요성1

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

그렇다면 hashCode()나 equals()를 제대로 구현하지 않을 경우 어떤 문제가 발생하는지 확인해본다.

6.1. Object의 기능 기능

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

클래스를 만들 때 hashCode(), eauqls()를 재정의하지 않으면 해시 자료 구조에서 Object가 기본으로 제공하는 hashCode(), equals()를 사용하게 된다. 그런데 Object가 기본으로 제공하는 기능은 단순히 인스턴스의 참조값을 기반으로 시작한다.

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

package collection.set.member;
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 + '\\'' +
                '}';
    }
}

-> hashCode(), equals()를 재정의하지 않았다. 따라서 Object 의 기본 기능을 사용한다.

Main 코드

package collection.set.member;

import 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);

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

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

// result
m1.hashCode() = 2055281021
m2.hashCode() = 1392838282
m1.equals(m2) = false
MyHashSetV2{buckets=[[], [MemberNoHashNoEq{id='A'}], [MemberNoHashNoEq{id='A'}], [], [], [], [], [], [], []], size=2, capacity=10}
searchValue.hashCode() = 1670782018
contains = false

m1 과 m2 는 인스턴스는 다르지만 둘다 "A"라는 같은 회원 id 를 가지고 있다. → 따라서 논리적으로 같은 회원으로 보아야 한다

 

6.2.1. 데이터 저장 시 발생하는 문제

 

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

6.2.2. 데이터 검색 시 발생하는 문제

 

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

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

hashCode()만 재정의했고 equals()는 재정의하지 않았다면?

→ 예상되는 문제로는 겹치는 데이터를 구분하지 못할 것이라고 생각

package collection.set.member;

import java.util.Objects;

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

→ hashCode 메서드를 재정의하였다. id 기준으로 해시 코드를 생성했다.

Main 코드

package collection.set.member;

import collection.set.MyHashSetV2;

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

// result
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

 

6.3.1. 데이터 저장 시 발생하는 문제

 

• hashCode() 를 재정의했기 때문에 같은 id 를 사용하는 m1 , m2 는 같은 해시 코드를 사용한다.
  • 따라서 같은 해시 인덱스에 데이터가 저장된다.
  • 그런데 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;
}

• bucket.contains() 내부에서 데이터를 순차 비교할 때 equals() 를 사용한다.
• 그런데 MemberOnlyHash는 equals()를 재정의하지 않았으므로 Object 의 equals()를 상속 받아서 사용한다.
• 따라서 인스턴스의 참조값을 비교한다. 인스턴스가 서로 다른 m1 , m2 는 비교에 실패한다.
• add() 로직은 중복 데이터가 없다고 생각하고 m1 , m2 를 모두 저장한다.

결과적으로 같은 회원 id 를 가진 중복 데이터가 저장된다.

 

6.3.2. 데이터 검색 시 발생하는 문제

 

• MemberOnlyHash searchValue = new MemberOnlyHash("A") → 동일한 회원 ID인 A로 만들어진 객체를 통해 검색하려고 한다.
• hashCode()를 오버라이딩했기 때문에 hashIndex는 정확히 찾을 수 있다.
• 하지만 해당 hashIndex에 있는 모든 데이터를 equals()를 통해 비교해서 같은 값을 찾아야 한다.
• bucket.contains(xxx) 내부에서 연결 리스트에 있는 모든 항목을 searchValued와 equals()로 비교하게 된다.

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

• equals()를 재정의하지 않았다. → 따라서 논리적인 회원 ID를 비교하는게 아니라 참조값을 비교하게 된다. 따라서 m1, m2 비교에 실패하게 된다.

결과적으로 데이터를 찾을 수 없다.

따라서 hashCode와 equals를 모두 구현해야 한다.

참고 - 해시 함수는 해시 코드가 최대한 충돌하지 않도록 설계

앞서 직접 만든 해시 함수의 해시 코드 충돌의 예

"BC" B(66) + C(67) = 133

"AD" A(65) + D(68) = 133

해시 함수는 같은 입력에 대해서 항상 동일한 해시 코드를 반환해야 한다.

좋은 해시 함수는 해시 코드가 한 곳에 뭉치지 않고 균일하게 분포하는 것이 좋다.

그래야 해시 인덱스도 골고루 분포되 어서 해시 자료 구조의 성능을 최적화할 수 있다.

이런 해시 함수를 직접 구현하는 것은 쉽지 않다.

자바가 제공하는 해 시 함수들을 사용하면 이런 부분을 걱정하지 않고 최적화 된 해시 코드를 구할 수 있다.

하지만 자바가 제공하는 해시 함수를 사용해도 같은 해시 코드가 생성되어서 해시 코드가 충돌하는 경우도 간혹 존재한다. 예)

"Aa".hashCode() = 2112 "BB".hashCode() = 2112

이 경우 같은 해시 코드를 가지기 때문에 해시 인덱스도 같게 된다.

하지만 equals() 를 사용해서 다시 비교하기 때문에 해시 코드가 충돌하더라도 문제가 되지는 않는다.

그리고 매우 낮은 확률로 충돌하기 때문에 성능에 대한 부분도 크게 걱정하지 않아도 된다.