Java - hashCode(), 사용하는 이유? 구현 방법?

Java에서 객체의 hashcode를 가져올 때, hashCode() 메소드를 호출하면 hashcode가 리턴됩니다. 이 글에서는 hashcode를 사용하는 이유와 hashCode()를 구현할 때 꼭 알아야할 내용 및 구현 방법을 소개합니다.

1. Hashcode

Hashcode는 객체를 식별하는 Integer 값입니다. 객체가 갖고 있는 데이터를 어떤 알고리즘에 적용하여 계산된 정수 값을 hashcode라고 할 수 있습니다.

어떤 객체의 hashcode를 계산할 때, hashCode() 메소드를 호출하면 hashcode가 리턴됩니다. String.java의 경우, 아래와 같이 hashCode()를 재정의하고 있습니다. 알고리즘을 보면 hashcode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]으로 hashcode를 계산합니다. 여기서 s[0]는 문자열의 0번 Index의 char입니다.

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {

    private final char value[];

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
}

2. Hashcode를 사용하는 이유

Hashcode를 사용하는 이유 중에 하나는, 객체를 비교할 때 드는 비용을 낮추기 위해서 입니다. 자바에서 2개의 객체가 같은지 비교할 때 equals()를 사용하는데, 여러 객체를 비교할 때 equals()를 사용하면 Integer를 비교하는 것에 비해 많은 시간이 소요됩니다. Java에서 hashcode는 Integer이며, hashcode를 이용하여 객체를 비교하면 equals()를 이용하는 것보다 시간이 단축됩니다. 보통 HashMap에서 hashcode를 이용하여 객체를 매핑하며 객체를 찾을 때 사용합니다.

두 객체의 hashcode가 다르면 두 객체는 같지 않습니다. 따라서, 객체를 비교할 때 먼저 hashcode를 비교하면, 절대 같을 수 없는 경우를 빠른 연산으로 확인할 수 있습니다. 그리고 hashcode가 같을 때는 equals()로 두 객체가 같은지 비교할 수 있습니다.

  • hashcode가 다르면, 두개의 객체가 같지 않다
  • hashcode가 같으면, 두개의 객체가 같거나 다를 수 있다

3. hashCode(), equals() 구현 방법

Java에서 hashCode()equals()는 Object 클래스에 구현되었으며, 모든 객체는 이 메소드를 상속합니다. 따라서, 클래스에서 이 메소드들을 사용하거나 오버라이드하여 재정의할 수 있습니다.

public class Object {
  public boolean equals(Object obj) {
      return (this == obj);
  }

  /**
   * Returns a hash code value for the object. This method is
   * supported for the benefit of hash tables such as those provided by
   * {@link java.util.HashMap}.
   * <p>
   * The general contract of {@code hashCode} is:
   * <ul>
   * <li>Whenever it is invoked on the same object more than once during
   *     an execution of a Java application, the {@code hashCode} method
   *     must consistently return the same integer, provided no information
   *     used in {@code equals} comparisons on the object is modified.
   *     This integer need not remain consistent from one execution of an
   *     application to another execution of the same application.
   * <li>If two objects are equal according to the {@code equals(Object)}
   *     method, then calling the {@code hashCode} method on each of
   *     the two objects must produce the same integer result.
   * <li>It is <em>not</em> required that if two objects are unequal
   *     according to the {@link java.lang.Object#equals(java.lang.Object)}
   *     method, then calling the {@code hashCode} method on each of the
   *     two objects must produce distinct integer results.  However, the
   *     programmer should be aware that producing distinct integer results
   *     for unequal objects may improve the performance of hash tables.
   * </ul>
   * <p>
   * As much as is reasonably practical, the hashCode method defined by
   * class {@code Object} does return distinct integers for distinct
   * objects. (This is typically implemented by converting the internal
   * address of the object into an integer, but this implementation
   * technique is not required by the
   * Java&trade; programming language.)
   *
   * @return  a hash code value for this object.
   * @see     java.lang.Object#equals(java.lang.Object)
   * @see     java.lang.System#identityHashCode
   */
  public native int hashCode();
}

hashCode()의 주석을 보면 아래 두가지 규칙을 소개하고 있습니다.

  • 두 객체가 같으면(equals()가 true 리턴), hashCode()는 같은 값을 리턴해야 합니다.
  • 두 객체가 같지 않을 때 (hashCode()가 false), hashCode()가 꼭 다른 값을 리턴해야하는 것은 아닙니다. 하지만 다른 값을 리턴하면 hash table의 성능이 향상됩니다.

첫번째 규칙은 equals()가 같을 때 hashCode()도 같은 값을 리턴해야하는 것인데요. 즉, equals()를 오버라이드하여 재정의하면, hashCode()도 재정의하여 같은 객체에 대해서 같은 값을 리턴하도록 구현해야 합니다. 커스텀 클래스가 hash table을 사용하지 않고 자신의 코드 내에서 equals()만 사용할 때는 hashCode()를 오버라이드 하지 않아도 문제는 없겠지만, 나중에 HashMap에서 사용될 때 문제가 될 수 있습니다.

두번째 규칙은 객체가 달라도 계산된 hashcode가 같을 가능성이 있다는 것인데요. hashcode가 같으면 equals()로 같은 값을 찾기 때문에 문제가 되지는 않습니다. 하지만 hashing 알고리즘이 중복된 hashcode를 적게 만들 수록 hash table의 equals()를 적게 사용하여 hash table의 성능이 향상될 수 있다는 것으로 해석할 수 있습니다.

4. hashCode() 구현 예제

예를 들어, 아래와 같이 동일한 값을 리턴하는 것은 잘못된 구현의 예입니다. 이렇게 구현하면 모든 객체의 hashcode가 같기 때문에 hash table의 성능적인 이점이 없어집니다.

public static class Foo {
    String name;
    int age;


    @Override
    public int hashCode() {
        return 1;
    }
}

다른 예로, String.java는 아래와 같은 알고리즘으로 hashcode를 계산합니다. 31을 제곱하는 것은 중복될 가능성이 적다고 생각해서 인 것 같습니다.

  • hashcode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
public final class String {
    private final char value[];

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
}

hashcode를 계산할 때 왜 31을 곱하는지 StackOverflow - Why does Java's hashCode() in String use 31 as a multiplier?에 질문과 답변이 있습니다.

위의 알고리즘과 비슷하게, 31을 제곱해주고 String.hashCode() 값을 이용하여 구현할 수 있습니다. 다른 객체가 쉽게 같은 hashcode로 계산되는 알고리즘이라면 hash table의 성능이 좀 안좋아지겠지만, HashMap이 잘못 동작하진 않을 것입니다.

public class HashCodeExample {

    public static class Foo {
        private String name;
        private int age;

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

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 31 * hash + age;
            hash = 31 * hash + (name == null ? 0 : name.hashCode());
            return hash;
        }
    }

    public static void main(String[] args) {
        Foo foo = new Foo("John", 30);
        System.out.println(foo.hashCode());

        Foo foo2 = new Foo("Doe", 35);
        System.out.println(foo2.hashCode());
    }
}

Output:

2322196
76702

References

Loading script...

Related Posts

codechachaCopyright ©2019 codechacha