[Java] Hashcode

면접 질문에서, Hashcode의 대한 질문을 받았다.

👨🏻‍🏫 HashCode는 무엇이고, 어떤 기능을 하나요?

 

 

 

HashCode란

객체를 식별하는 하나의 정수값을 말한다. Object의 HashCode() 메소드는 객체의 메모리 번지를 이용해서 해시코드를 만들어서 리턴하기 때문에 객체마다 다른 값을 가지고 있다. 

또한, 동등성 비교 시 컬렉션 프레임워크 중 HashSet, HashMap, HashTable 들은 hashCode를 통해서 동등한지 비교한다.

 

 

👨🏻‍🏫 그렇다면, 동등성 비교할 때, Equals로도 충분히 가능하지 않을까요?

그렇다, equals의 기능으로도 동등성 비교는 충분히 가능하다. HashCode는 같은 객체 인지 판별하는 기능만 있는게 아니다. 

 

 

hashCode()를 사용해 객체의 위치(bucket)를 빠르게 찾거나 적절한 곳에 저장할 수 있다.

즉, hashcode는 인덱싱 힌트이다.

 

 

컬렉션 프레임워크에 equals를 통해 모든 객체를 순회하여 비교한다면 O(n)이 걸린다.

하지만, hashCode를 통해서, O(1)으로 같은 데이터를 가져올 수 있다.

 

 

Java HashTable

hashTable을 통해서 더 자세히 보자,

hashTable은 Key, Value 형태로 데이터를 저장한다.

이때, 해시 함수를 이용하여 key 값을 기준으로 고유한 식별 값인 해시값을 만든다. 

이때, key값을 기준으로 고유한 식별값이 hash 값을 만드는데, 여기에서 hashCode가 사용된다.

이 hash값을 기준으로 Bucket에 저장하게 된다.

위 과정으로, 앞서 말한 데이터를 hash 인덱싱 기능을 할 수 있게 되는 것이다.

 

해당 과정에서, hash 값이 같은 객체가 이미 있다면, Equals를 통해서 (true)덮어 쓸지, (false)같은 레벨에 체이닝 방식(LinkedList)으로 저장된다.

 

 

HashCode와 Equals 어떻게 사용할까?

다음은 해시코드 규약이다.

• equals 비교에 사용되는 정보가 변경되지 않았다면, 애플리케이션이 실행되는 동안 그 객체의 hashCode 메소드는 몇 번을 호출해도 일관되게 항상 같은 값을 반환해야 한다.(단, 애플리케이션을 다시 실행한다면 이 값이 달라져도 상관없다.)
• equals(Object)가 두 객체를 같다고 판단했다면, 두 객체의 hashCode는 똑같은 값을 반환해야 한다.
• equals(Object)가 두 객체를 다르다고 판단했더라도, 두 객체의 hashCode가 서로 다른 값을 반환할 필요는 없다. 단, 다른 객체에 대해서는 다른 값을 반환해야 해시테이블의 성능이 좋아진다.

 

Hash 성능을 향상시키기 위해서는 충돌을 방지해야한다.

충돌이 발생하지 않도록 계산 결과가 최대한 겹치지 않도록 고려하여 계산 식을 마련해야한다. 

 

 

표준 HashCode

인텔리제이에서 만들어주는 hashCode를 보면 기본 제공하는 Object.hash()를 사용한다.

public class User {

    private long id;
    private String name;
    private String email;

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

 

여기에서, 숫자 31을 곱해주는 이유는

31이 소수(Prime)이기 때문에, 충돌을 줄일 수 있다. 또한, 비트 연산으로 계산이 가능해서 빠르다.

 

 

---

만약, Hash 컬렉션 프레임워크를 사용한다면 HashCode와 Equals를 고려해보자.

출처: https://jisooo.tistory.com/entry/java-hashcode%EC%99%80-equals-%EB%A9%94%EC%84%9C%EB%93%9C%EB%8A%94-%EC%96%B8%EC%A0%9C-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B3%A0-%EC%99%9C-%EC%82%AC%EC%9A%A9%ED%95%A0%EA%B9%8C

https://go-coding.tistory.com/30