컬렉션 프레임워크 - HashSet

직접 구현하는 Set1 - MyHashSetV1

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

 

 

---

문자열 해시 코드

해시 코드와 해시 인덱스

 

---

자바의 hashCode()

해시 인덱스를 사용하는 해시 자료 구조는 데이터 추가, 검색, 삭제의 성능이 O(1)로 매우 빠르다. 따라서 많은 곳에서 자주 사용된다. 그런데 앞서 학습한 것 처럼 해시 자료 구조를 사용하려면 정수로 된 숫자 값인 해시 코드가 필요하다. 자바에는 정수뿐만 아니라 String, double 등 많은 타입이 있으며 개발자가 정의한 사용자 정의 타입도 있다.

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

 

Object.hashCode()

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

public class Object {
	public int hashCode();
}

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

package collection.set;

import collection.set.member.Member;

public class JavaHashCodeMain {

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

        //equals, hashcode를 오버라이딩 하지 않는 경우와, 한 경우를 비교
        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());
    }
}

 

실행 결과

obj1.hashCode() = 284720968
obj2.hashCode() = 1534030866
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()는 객체의 참조값을 해시 코드로 사용한다. 따라서 인스턴스마다 서로 다른 값을 반환한다.

그 결과 obj1, obj2는 서로 다른 해시 코드를 반환한다.

 

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

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

 

동일성과 동등성

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

자바는 두 객체가 같다는 표현을 2가지로 분리해서 사용한다.

• 동일성(Identity):  == 연산자를 사용해서 두 객체의 참조가 동일한 객체를 가리키고 있는지 확인
• 동등성(Equlity): equals() 메서드를 사용하여 두 객체가 논리적으로 동등한지 확인

쉽게 이야기해서 동일성은 물리적으로 같은 메모리에 있는 객체인지 참조값을 확인하는 것이고, 동등성은 논리적으로 같은지 확인하는 것이다.

동일성은 자바 머신 기준이고 메모리의 참조가 기준으로 물리적이다. 동등성은 보통 사람이 생각하는 논리적인 것에 기준을 맞춘다.

 

 

정리

자바가 기본으로 제공하는 클래스는 대부분 hashCode()를 재정의 해두었다.

객체를 직접 만들어야 하는 경우에 hashCode()를 재정의하면 된다.

hashCode() 만 재정의하면 필요한 모든 종류의 객체를 해시 자료 구조에 보관할 수 있다.

정리하면 해시 자료 구조에 데이터를 저장하는 경우 hashCode()를 구현해야 한다.

---

직접 구현하는 Set2 - MyHashSetV2

 

 

---

직접 구현하는 Set3 - 직접 만든 객체 보관

직접 만든 객체를 Set에 보관하려면 hashCode(), equals() 두 메서드를 만드시 구현해야한다.

 

package collection.set;

import collection.set.member.Member;

public class MyHashSetV2Main2 {

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

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

 

실행 결과

hi.hashCode() = 3329
JPA.hashCode() = 73659
java.hashCode() = 3254818
spring.hashCode() = -895679987
MyHashSetV2{buckets=[[Member{id='hi'}, Member{id='JPA'}], [], [], [], [], [], [Member{id='spring'}], [], [], [Member{id='java'}]], size=4, capacity=10}
set.contains(Member{id='JPA'}) = true
set.remove(Member{id='JPA'}) = true
MyHashSetV2{buckets=[[Member{id='hi'}], [], [], [], [], [], [Member{id='spring'}], [], [], [Member{id='java'}]], size=3, capacity=10}

 

 

 

equals() 사용처

그렇다면 equals()는 언제 사용할까?

"JPA"를 조회할 때 해시 인덱스느 0이다. 따라서 배열의 0번 인덱스를 조회한다.

여기에는 [Hi, JPA]라는 회원 두 명이 있다. 이것을 하나하나 비교해야 한다. 이 때 equals()를 사용해서 비교한다.

따라서 해시 자료 구조를 사용할 때는 hashCode()와 equals() 모두 반드시 재정의 해야 한다.

 

---

equals, hashCode의 중요성1

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

 

Object의 기본 기능

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

 

---

equals, hashCode의 중요성2

 

정리

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

 

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

다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있다. 이것을 해시 충돌이라 한다.

해시 함수로 해시 코드를 만들 떄 단순히 문자의 숫자를 더하기만 해서는 해시가 충돌할 가능성이 높다.

이를 막기 위해 자바의 해시코드는 복잡한 추가 연산으로 다양한 범위의 해시 코드가 만들어지게 하였고 이는 결과적으로 해시 자료 구조를 사용할 때 성능이 개선된다.

 

 

 

---

직접 구현하는 Set4 - 제네릭과 인터페이스 도입

package collection.set;

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

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

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

    //linkedList는 값을 지우는 방법이 2가지 있다.
    //1. 인덱스로 지우는 방법, 2. 값으로 지우는 방법
    //int로 넣으면 1번 인덱스로 인식해버리기때문에 Integer.valueOf()로 래퍼를 씌워주자
    public boolean remove(Object value) {
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        boolean remove = bucket.remove(value);
        if (remove) {
            size--;
            return true;
        } else {

            return false;
        }
    }

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

    //Object.hashCode() 메서드는 음수가 나올 수 있으므로 절대값으로 만들어준다.
    private int hashIndex(Object value) {
        return Math.abs(value.hashCode()) % capacity;
    }


    public int size() {
        return size;
    }


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

 

 

 

 

 

 

 

 

 

 

 

출처 - 김영한의 실전 자바 중급 2편