[Item11] equals를 재정의 하려거든 hashCode 도 재정의하라

왜 equals를 재정의하면 hashCode도 재정의 해야할까?

• Object의 일반 규약을 어기게 되기 때문이고,
• hashCode를 재정의 하지 않으면 hashMap, hashSet 을 사용하였을 때 문제를 일으킨다.

Object 일반 규약

• equals 가 사용하는 정보가 변경되지 않는다면 hashCode 를 여러 번 호출해도 동일 hash 값을 반환해야 한다.
• equals 메소드가 같다고 판정한 두 객체는 같은 hash 값을 반환해야 한다.
• equals 메소드가 다르다고 판정한 두 객체의 hash 값이 같을 수는 있다. 하지만 이런 일이 자주일어나면 성능이 떨어진다는점은 알고 있어야 한다.

일반규약에 따른 hashCode와 equals 간의 관계 유추

• equals 정보로 hashCode 값이 만들어진다.
• equals 정보가 같으면 hashCode는 같은 값을 반환한다.
• equals 정보가 같아도 같은 hash를 가지지만, 최대한 정보가 다르면 다른 hash를 반환하도록 해야한다.

HashMap 은 어떻게 put이 이뤄지는 건가

• hashMap은 객체의 값이 아닌, 객체의 hashCode(int) 로 값을 찾는다.

static final int hash(Object key) {
	int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
	Node<K,V>[] tab; Node<K,V> p; int n, i;
  if ((tab = table) == null || (n = tab.length) == 0)
	  n = (tab = resize()).length;
  if ((p = tab[i = (n - 1) & hash]) == null)
	  tab[i] = newNode(hash, key, value, null);
  else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
	    ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      for (int binCount = 0; ; ++binCount) {
	      if ((e = p.next) == null) {
	        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
          treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
	    ((k = e.key) == key || (key != null && key.equals(k))))
	      break;
      p = e;
    }
 }
 if (e != null) { // existing mapping for key
	 V oldValue = e.value;
   if (!onlyIfAbsent || oldValue == null)
	   e.value = value;
     afterNodeAccess(e);
     return oldValue;
 }
}
++modCount;
if (++size > threshold)
	resize();
  afterNodeInsertion(evict);
  return null;
}

적절하게 hashCode 를 정의하는 방법

• 나쁜 예

Map<PhoneMunber, String> m = new HashMap<>();
m.put(new PhoneNumber(707, 867, 5309), "제니");

-----------------------------------
// PhoneNumber.class

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

• 위처럼 hashCode를 정의하면, 모든 객체들이 같은 hashCode를 가져가게 된다. 즉 동치성이 다른 객체더라도 같은 hashCode를 가진다는 것이다.

• 좋은 예

// PhoneNumber.class
private final short areaCode, prefix, lineNum;

@Override public int hashCode() 
{
	int shourt = Short.hashCode(areaCode);
	result = 31* result + Short.hashCode(prefix);
	result = 31* result + Short.hashCode(lineNum);
	return result;
}

------------------------------------
// using Objects.hashCode()
@Override public int hashCode() 
{
	return Objects.hashCode(areaCode, prefix, lineNum);
}

-------------------------------------------------
// using caching
private int hashCode;
@Override public int hashCode() 
{
	int result = hashCoe;
	if(result == 0) {
		int shourt = Short.hashCode(areaCode);
		result = 31* result + Short.hashCode(prefix);
		result = 31* result + Short.hashCode(lineNum);
		hashCode = result;
	}
	return result;
}

• PhoneNumber의 핵심필드 세개만 사용해 간단한 계산을 수애한다.
• Obects.hashCode() 를 편리하게 제공하지만, 성능이 느리다.
  • 입력인수를 담기위한 배열이 만들어지고,
  • 입력 중 기본타입이 있다면 박싱과 언박싱도 거쳐야 한다.
• 해시코드를 계산하는 비용이 크다면 캐싱을 사용하는 방식을 고려한다.

String 의 hashCode

public int hashCode() {
	int h = hash;
    if (h == 0 && !hashIsZero) {
    	h = isLatin1() ? StringLatin1.hashCode(value)
        	: StringUTF16.hashCode(value);
    	if (h == 0) {
    		hashIsZero = true;
    	} else {
        	hash = h;
    	}
    }
    return h;
}
--------------------------
// StringLatin1.hashCode()
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
    	h = 31 * h + (v & 0xff);
    }
    return h;
}
// StringUTF16.hashCode()
public static int hashCode(byte[] value) {
	int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
    	h = 31 * h + getChar(value, i);
    }
    return h;
}

• 31을 사용하는 이유는, 31이 소수이며 또한 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다.
• 32는 2^5이므로 32를 곱한 값은 shift 연산으로 쉽게 구현할 수 있다.
• 따라서 N에 31을 곱한 값은 (N << 5) - N과 같다.

❗ 결론

equals와 hashCode는 한 몸이다.
기본 Objects는 논리적 동치성이 같더라도 다른 hashCode를 가지므로, equals가 같을 때는 같은 hashCode를 가지도록 재정의를 꼭 해주어야 한다.
해주지 않은 경우에는 hashMap이 hashCode를 identifier로 사용하기 때문에, 같은 객체더라도 다른 key값으로 인식하게 된다.
기본 hashCode는 검색해보니 여러블로그에서 메모리주소로부터 가져오게 된다는데 이부분에 대해 궁금증이 생겼다. 이 부분은 따로 포스팅을 할 예정이다.