[Java] Hash ( eqauls, hashCode )

[ equals /  hashCode ] 

 

해쉬 자료구조를 사용 하려면 equals, hashCode를 오버라이딩 해야 합니다.

오버라이딩 하지 않으면 어떤 문제가 발생 하는지 알아 보겠습니다.

회원 객체를 Set 자료구조에 저장 하는 예제 입니다.

public class HashSetTest {
    public static void main(String[] args) {
        Set<Member> memberSet = new HashSet<>();

        Member member1 = new Member("1번", 10);
        Member member2 = new Member("2번", 20);
        Member member3 = new Member("1번", 10);
        memberSet.add(member1);
        memberSet.add(member2);
        memberSet.add(member3);

        Iterator<Member> iterator = memberSet.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    private static class Member {
        private final String name;
        private final int age;

        public Member(String name, int age) {
            this.name = name;
            this.age = age;
        }

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

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

    }
}

 

회원은 이름과 나이를 가지고 있습니다.

이름과 나이가 같으면 논리적으로 같은 회원이라고 equals를 오버라이딩 하였습니다.

원하는 결과는 Set은 중복을 허용 하지 않기 때문에

[ 회원1, 회원3 ]은 나이 이름이 같은 회원이니 회원3을 제외한 [ 회원 1, 회원2 ] 만 출력 되기를 바랍니다.

 

 

하지만 원하는 결과 값이 나오지 않았습니다.

hashCode만 오버라이딩 해보겠습니다.

@Override
public int hashCode() {
   return Objects.hash(name, age);
}

 

 

결과는 같습니다.

equals와 hascode를 둘다 오버라이딩 해보겠습니다.

 

원하는 결과값이 나옵니다. 왜 그럴까요?

이를 이해 하기 위해서는 처음으로 돌아가 HastSet을 구현 하려면 어떻게 해야 할지 고민 해야 합니다.

어떻게 하면 객체를 시간 복잡도 O(1)로 찾을수 있을까요?

그 방법은 객체의 인덱스를 알 수 있으면 바로 찾을 수 있습니다.

 

어떻게 객체 인덱스를 바로 찾을수 있을까요?

이에 대한 답이 hashCode 입니다. 그림으로 알아 보겠습니다.

 

 

 

객체를 hash 함수를 통해 hashCode로 만들고 hashCode를 통해 hashIndex를 만듭니다.

hashIndex를 통해 배열에 저장 하는 것입니다.

 

어떻게 hashCode를 만들수 있을까요? hashCode에 대해 알아 보겠습니다.

자바에는 Object.hashCode, Objects.hashCode가 있습니다.

먼저 Object.hashCode() 에 대해 알아 보겠습니다.

 

[ Object.hashCode ] 

회원의 toString, hashCode 오버라이딩 없이 출력해 보겠습니다.

public static void main(String[] args) {
        Member member1 = new Member("1번", 10);
        Member member2 = new Member("2번", 20);
        Member member3 = new Member("1번", 10);

        System.out.println(member1);
        System.out.println(member2);
        System.out.println(member3);

        System.out.println(member1.hashCode());
        System.out.println(member3.hashCode());
}

 

객체의 타입뒤에 Member@? 로 나타납니다. 저 값은 해쉬 코드를 16진수로 나타낸것입니다.

모든 클래스는 Object가 부모이므로 hashCode를 오버라이딩 하지 않는다면 Object.hashCode를 사용 합니다.

 

 

Object.hashCode는 객체의 참조 값을 토대로 만들어 집니다.

1,3번 회원이 equals를 통해 논리적으로 같다고 표현 했지만 hashCode 값이 다른것을 볼 수 있습니다.

 

[ Objects.hashCode ] 

@Override
public int hashCode() {
   return Objects.hash(name, age);
}

 

각 객체의 hashCode를 호출 하여 이전 해쉬 코드 값에 반영 하고 있습니다.

해쉬코드는 순서에도 영향을 받습니다.

계산을 해보면 hashCode(1, 2) / hashCode(2, 1)의 결과가 다른것을 알 수 있습니다.

 

-> Objects.hashCode를 오버라이딩 하여 사용 하면 됩니다.

 

[  hashCode가 같으면 같은 객체 인가요? ]

답은 아니요 입니다.

다른 객체 인데 hashcode가 우연히 같을 수 있습니다.

 

[ 해쉬 충돌 ]

 

다른 객체인데 우연히 해쉬코드가 같을 수 있습니다.

이를 해쉬 충돌이라고 합니다. 어떻게 둘을 구분 할 수 있을까요?

이에 대한 답이 equals 오버라이딩 입니다.

 

해쉬 인덱스의 내부를 돌며 equals를 통해 동등성 비교를 하면 같은 객체 인지 알 수 있습니다.

배열 안에 어떻게 여러 객체가 있죠? 자료구조를 이용 하면 됩니다.!

 

정리 하면 hashCode를 통해 hashIndex를 만들고

hashIndex 번째 LinkedList를 돌며 같은 객체가 있는지 equals를 통해 찾으면 되는거죠!

이렇게 한다면 O(1) 로 객체를 찾을수 있게 됩니다.

 

간단히 LinkedList를 통해 hashSet을 구현해 보겠습니다.

 

[ 참고 ] 

자바8 이전 : LinkedList 구현

자바8 이후 : Tree

이유:  LinkedList : 조회 성능(n) / Tree 조회 성능 (log n)

 

[ SimpleHashSet 구현 ] 

public class SimpleHashSet<T> {

    private int capacity = 10;
    private int size = 0;
    private List<List<T>> set = new LinkedList<>();

    public SimpleHashSet() {
        for(int i = 0; i < capacity; i++){
            set.add(new LinkedList<>());
        }
    }

    public void add(T data){
        int hashIndex = getHashIndex(data);
        List<T> list = set.get(hashIndex);

        if(!isContain(list, data) && size + 1 < capacity){
            size++;
            list.add(data);
        }
    }

    public boolean contains(T data){
        int hashIndex = getHashIndex(data);
        List<T> list = set.get(hashIndex);
        return isContain(list, data);
    }

    public boolean remove(T data){
        int hashIndex = getHashIndex(data);
        List<T> list = set.get(hashIndex);
        return isRemoveSuccess(data, list);
    }

    private int getHashIndex(T data){
        int hashCode = data.hashCode();
        int hashIndex = hashCode % capacity;
        return hashIndex;
    }

    private boolean isContain(List<T> list, T data) {
        Iterator<T> iterator = list.iterator();
        while(iterator.hasNext()){
            T next = iterator.next();
            if(next.equals(data)){
                return true;
            }
        }
        return false;
    }

    private boolean isRemoveSuccess(T data, List<T> list) {
        Iterator<T> iterator = list.iterator();
        while(iterator.hasNext()){
            T next = iterator.next();
            if(next.equals(data)){
                list.remove(data);
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        for (List<T> list : set) {
            if(!list.isEmpty()) {
                for (T t : list) {
                    sb.append(t).append(" ");
                }
            }
        }
        sb.append("] ").append("\n");
        return sb.toString();
    }
}

 

LinkedList를 사용하여 capacity가 10 이하일때 사용할수 있는 HashSet 입니다.

사용하기엔 미흡하지만 대략적인 HashSet 동작 방식을 이해 하기에는 도움이 될것 같아요!

 

[ 테스트 ] 

public class SimpleHashSetTest {
    public static void main(String[] args) {
        SimpleHashSet<Integer> hashSet = new SimpleHashSet<>();

        // add
        hashSet.add(1);
        hashSet.add(2);
        hashSet.add(3);
        hashSet.add(1);
        System.out.print(hashSet);

        // contains
        boolean contains1 = hashSet.contains(4);
        System.out.println("4 포함 여부 : " + contains1);
        boolean contains2 = hashSet.contains(1);
        System.out.println("1 포함 여부 : " + contains2);

        // remove
        boolean removed1 = hashSet.remove(4);
        System.out.println("4 제거 여부 : " + removed1);
        boolean removed2 = hashSet.remove(1);
        System.out.println("1 제거 여부 : "  + removed2);
    }
}

 

 

[ 정리 ]

HashSet의 동작 방식에 대해서 간단히 알아보았습니다.

HashSet은 내부적으론 HashMap을 사용하며 value가 없는 상태로 사용 합니다.

다음엔 실제 HashMap이 어떻게 hashCode를 만들고 Index를 찾는지 간단하게 알아 보겠습니다.!