기록하고 공유하는 기술 블로그

Objects.hash를 객체의 식별자로 사용하다가 장애를 내는 경험을 했다.

문제가 된 코드는 다음과 같다.

var itemGroup = itemRepository.findByOrderSeqIn(orderIds)
        .stream().collect(Collectors.groupingBy(item -> Objects.hash(item.getItemSeq(), item.getOrderSeq())));

hash 는 중복이 일어날 수 있다는 것을 간과한 채, item의 pk와 order의  pk의 조합으로 hash값을 만들고 이를 식별자로 사용한 것이다.

그럼 hash값은 얼마나 자주 중복이 발생할까?

Objects.hash()의 구현을 보면 아래와 같다.

public static int hash(Object... values) {
    return Arrays.hashCode(values);
}

public static int hashCode(Object[] a) {
        if (a == null)
            return 0;

        int result = 1;

        for (Object element : a)
            result = 31 * result + (element == null ? 0 : element.hashCode());

        return result;
    }

element.hashCode() 메소드의 구현체는 타입별로 좀 상이한데 long 기준으로 살펴보자. 

public static int hashCode(long value) {
  return (int)(value ^ value >>> 32);
}

이는 상위 32비트와 하위 32비트를 XOR 연산한 후, 그 결과를 int로 캐스팅하여 출력하라는 뜻이다.

예를 들어 값이 다음과 같으면,

orderSeq: 246385, itemSeq: 5215

orderSeq: 246411, itemSeq: 4409

(31 + 246385) * 31 + 5215 = (31 + 246411) * 31 + 4409 로 중복이 발생한다.

 element가 하나라면 중복 가능성은 훨씬 높아지는 것이다.

그럼 해시 중복이 문제가 될까?

해시는 애초에 식별자로 사용되기 위한 목적을 가진 것이 아니다. 물론 식별이 가능하긴 하지만, 정확한 목적은 효율적인 검색이며, 해시 테이블이나 해시 맵과 같은 자료 구조에서 빠르게 검색하고 저장하기 위해 사용하는 것이다.

또한 해시 함수의 입력 데이터의 크기는 무한할 수 있지만, 출력 값은 고정된 크기로 제한되기 때문에 중복이 발생할 수 밖에 없고, 해시를 사용하는 자료구조들은 이를 감안하여 구현되어 있다.

Java 해시 맵으로 확인해보자.

해시 맵에 원소를 추가하는 putVal 메소드에 해시 충돌을 해결하는 부분을 보면 아래와 같다.

...

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;
    }
}

...

기본 적으로는 linked list를 만들어 처리하고, 리스트가 길어지면 tree 구조를 만들어 처리하는 것을 볼 수 있다.

추가로 확인할 수 있는 부분은,

HashMap 의 탐색 복잡도가 O(1) 인데, 해시 값이 충돌되면 정확히 O(1)은 아니고 추가적으로 linked list나 tree 탐색이 필요하니,

hash 값이 겹치지 않도록 구성하는게 성능 향상에 도움이 되는 것을 확인할 수 있다.