[Java] 해싱과 equals() hashCode

 

남궁성님의 Java의 정석(3rd Edition)을 보고 정리한 글입니다.

 

1. 해싱이란?

• 해싱이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법이다.
• 해시함수의 결과를 가지고 데이터가 저장되어 있는 곳을 찾아 데이터를 빠르게 검색할 수 있다.
• 해싱에서 사용하는 자료구조는 배열과 LikedList 조합
• 해시함수는 자바에서 Object클래스의 메서드 hashCode() 개념과 동일하다.

배열과 링크드 리스트의 조합

 

 

 

2. 해시테이블 검색 과정

1. 검색하고자 하는 키로 해시함수를 호출한다.
2. 해시함수의 결과(해시코드)로 해당 값이 저장되어 LikedList를 찾는다.
3. LikedList에서 검색한 키와 일치하는 데이터를 찾는다. 

   

 

 

3. 해시 테이블 성능 개선

• 링크드 리스트는 검색에 불리한 자료구조 이기 때문에 링크드 리스트의 크기가 커질수록 검색 성능이 떨어지게 된다.
• 서로 다른 키에 대해서 중복된 해시코드의 반환을 최소화해야 검색속도가 빨라질 수 있으며 해시함수 알고리즘을 어떻게 구현하냐가 중요하다.

 

4. 동일성과 동등성

• 동일성은 Identity로 메모리 내 주소값이 같은지 비교
  • == 비교를 통해 비교하여 동일한지 검사
• 동등성은 Equality로 논리적으로 동등한지 비교
  • equals(), hashCode() 메서드를 통해 동등성을 검사

 

5. equals() 메서드

• 두 객체가 동등한지 확인하는 메서드

예제

• 사용자 정의 객체 Person 클래스 필드의 name과 age가 같으면 동등한 객체로 판단하려고 한다.
• 이런 경우에는 우선 equals()를 재정의해서 사용해야 한다.

class Person {
    String name;
    int age;

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

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Person) {
            Person tmp = (Person) obj;
            return name.equals(tmp.name) && age == tmp.age;
        }
        return false;
    }

    @Override
    public String toString() {
        return name + " : " + age;
    }
}

public class Main {
    public static void main(String[] args) {
        Set set = new HashSet();
        Person person1 = new Person("홍길동", 15);
        Person person2 = new Person("홍길동", 15);

        if(person1.equals(person2)) {
            System.out.println("두 객체는 동등합니다.");
        } else {
            System.out.println("두 객체는 동등하지 않습니다.");
        }

        set.add(person1);
        set.add(person2);

        System.out.println(set);
    }
}

실행결과
두 객체는 동등합니다.
[홍길동 : 15, 홍길동 : 15]

• 두 객체는 동등하지만, 중복을 허용하지 않는 Set은 두 객체를 동등 객체로 보지 않는다.
• 이걸 해결하려면 hashCode() 메서드에 대해서 알아봐야 한다.

 

6. hashCode()

• hashCode()를 재정의하여 동등성 기준을 재정의 할 수 있다.
• Hash Table을 사용하는 Set, Map 자료구는 해싱된 결과를 주소값으로 찾아가서 그곳에 같은 자료가 있는지 확인한다.

예제

 public class Main {
    public static void main(String[] args) {
        Set set = new HashSet();
        Person person1 = new Person("홍길동", 15);
        Person person2 = new Person("홍길동", 15);

        if(person1.equals(person2)) {
            System.out.println("두 객체는 동등합니다.");
        } else {
            System.out.println("두 객체는 동등하지 않습니다.");
        }

        set.add(person1);
        set.add(person2);

        System.out.println(set);
    }
}

class Person {
    String name;
    int age;

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

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Person) {
            Person tmp = (Person) obj;
            return name.equals(tmp.name) && age == tmp.age;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return (name + age).hashCode();
    }

    @Override
    public String toString() {
        return name + " : " + age;
    }
}

실행결과
두 객체는 동등합니다.
[홍길동 : 15]

 

HashMap, HashSet 등 hash 테이블을 사용하는 자료구조는 두 객체에 대해 equals()의 결과가 true인 동시에 hasCode의 반환값이 같아야 같은 객체로 인식한다.

동등성 검사나 hash 테이블을 사용하는 자료구조를 사용할 경우 사용자 정의 클래스를 사용할 때 Object 클래스의 equals(), hashCode() 재정의해서 사용하도록 하자.