[kotlin] equals와 hashCode의 관계, 그리고 해시 충돌까지...

왕왕조현·2026년 6월 10일

2026 Hash Collision kotlin

kotlin

목록 보기

7/8

왜 이 주제를 공부하게 되었는가?

상태에 해당하는 객체를 만들기 위해 data class를 주로 사용하지만, 이 내부의 구현 함수들에 대해서는 깊게 알아보지 않았다. 내부에서 생성해주는 함수들을 알지 못해도, data class를 사용하면 동등성 비교를 쉽게 할 수 있다!, toString()을 보기 좋게 출력할 수 있다! 처럼 단순하게 생각하고 사용했다.

Kotlin in Action을 읽다보니 equals를 구현할 때는 항상 hashCode도 함께 구현해야한다는 규칙을 알게 되었는데, 왜? 같이 구현해야하는지 의문이 생겼다. 그래서 이번 기회에 내부 함수에 대해서 알아보고자 했다. 그 중에 equals와 hashCode의 관계를 깊게 알아보고자 하였다.

hashCode()를 사용해본 적이 없다보니 더더욱 의문이 생긴 것 같다.

equals의 동작원리

equals는 두 객체의 동등성을 비교한다. 즉, 값만을 비교하는 것이다.

class Product(
	val name: String,
    val address: String
)

fun main() {
    val product1 = Product("건담", "안성")
    val product2 = Product("건담", "안성")
    
    println(product1 == product2) // false
}

하지만 아래의 출력문은 false를 반환한다. equals를 오버라이딩하지 않았다면, 동등성 비교가 아닌 참조 비교를 한다.

왜냐하면 자바에서 equals는 동등성 비교(값 비교)가 아닌 참조 비교(주소 비교)다. 마찬가지로 코틀린의 == 도 내부에서 equals를 호출하여 객체를 비교한다. 그렇기에 두 값이 같아 보이더라도 == 또는 equals를 사용해서 비교하면 두 값이 다르다고 나타낸다. 하지만 오버라이딩하여 구현한다면, 두 객체의 값을 비교하여 참이 되도록 구현할 수 있다.

class Product(
	val name: String,
    val address: String
) {
    override fun equals(other: Any?): Boolean {
        if (other == null || other !is Product)
        	return false
        return name == other.name && address == other.address
    }
}

fun main() {
    val product1 = Product("건담", "안성")
    val product2 = Product("건담", "안성")
    
    println(product1 == product2) // true
}

hashCode()의 동작 원리

equals를 구현했음에도 hashSet에 넣고 사용할 때는 두 값을 다르다고 판단한다.

class Product(
	val name: String,
    val address: String
) {
    override fun equals(other: Any?): Boolean {
        if (other == null || other !is Product)
        	return false
        return name == other.name && address == other.address
    }
}

fun main() {
    val product1 = Product("건담", "안성")
    val product2 = Product("건담", "안성")
    
    val processed = hashSetOf(product1)
    println(processed.contains(product2)) // false
}

분명 두 객체의 동등성 비교는 참인데 hashSet안에는 들어가있지 않는다고 결과가 나타난다…

이는 객체를 생성할 때마다 hashcode가 다르게 생성되기 때문인데, equals와 마찬가지로 hashCode()를 오버라이딩해서 구현한다면, hash 값을 같게 만들 수 있다.

class Product(
	val name: String,
    val address: String
) {
    override fun equals(other: Any?): Boolean {
        if (other == null || other !is Product)
        	return false
        return name == other.name && address == other.address
    }
    
    override fun hashCode(): Int = name.hashCode() * 31 + address.hashCode()
}

fun main() {
    val product1 = Product("건담", "안성")
    val product2 = Product("건담", "안성")
    
    val processed = hashSetOf(Product("건담", "안성"))
    println(processed.contains(Product("건담", "안성"))) // true
}

어? 근데 equals와 hashCode는 함께 구현하라는 규칙이 있다?

내가 생각했을 때는 equals와 hashCode의 역할이 다르다. equals는 두 객체의 동등성을 비교하기 위함이고, hashCode는 객체가 가진 고유의 값?을 설정하기 위함이라고 생각한다. 또한 두 객체의 동등성을 비교할 때 hashCode를 사용하지도 않는다… 마찬가지로 hashCode를 구현할 때 동등성을 비교하지도 않는다….

그렇다면 왜? equals와 hashCode를 함께 구현하라는 규칙이 생긴걸까??

해시 기반 컬렉션은 어떻게 동작하는가?

hashSet이나 hashMap이 어떤 객체가 들어있는지 찾을 때는 아래와 같은 순서로 검사한다.

hashCode() 호출 : 객체의 해시 코드를 구해서 몇 번 상자에 들어있는지 확인하고 그 상자로 순간 이동한다.
equals() 호출 : 그 상자 안에 들어있는 객체들과 하나씩 비교하면 진짜 내용물이 똑같은 것인지 최종 확인한다.

만약 hashCode만 구현했거나 equals만 구현했다면, hashSet에서 객체를 찾는 동작은 항상 false가 나타날 것이다.

그렇기에 아래와 같은 규칙이 생긴 것이다.

두 객체의 eqauls() 결과가 같다면, 두 객체의 hashCode() 값은 무조건 같아야 한다.

하지만 반대로 해시 값이 같다고 해서 equals가 무조건 같을 필요는 없다.

즉, hashCode 함수를 구현할 때는 equals를 사용하지 않지만, 이 함수를 실행할 때는 equals를 사용해 객체가 맞는지 최종 검증을 한다. 그렇기에 eqauls가 참이라면 hashCode도 참이 되도록 구현해야 한다.

하지만…이 해시 값마저 중복된다면 어떻게 될까? 바로 해시 충돌이 발생하게 된다.

해시 충돌이 무엇인가?

코틀린에서 hashCode() 함수가 반환하는 값은 Int 타입이다. Int 타입이 표현할 수 있는 숫자의 개수는 42억 개라는 개수로 한정되어 있다. 그렇다는 것은 억지로 넣다보면 결국 중복되는 해시코드가 생길 수도 있다는 것이다…

이를 수학에서는 비둘기집 원리라고 부른다. (비둘기가 10마리인데 집이 9개면, 한 집에는 무조건 2마리가 들어가야 한다!)

해시 테이블의 내부 구조

HashMap이나 HashSet 내부에는 데이터를 저장하기 위한 고정된 크기의 배열(Array)가 선언되어 있다. 이를 버킷 배열 또는 테이블이라고 부른다.

코틀린/자바의 HashMap을 만들면 내부 크기가 기본으로 16인 배열이 생성된다.

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
    static final int DEFAULT_INITIAL_CAPACITY = 16;

하지만 hashCode()가 반환할 수 있는 숫자는 42억 개다. 반환될 수 있는 숫자에 비해 배열의 크기가 상당히 작은데, 어떻게 배열에 넣는 것일까?

배열에 넣기 위해 해시코드를 그대로 사용하는 것이 아닌 Modulo 연산을 사용하여 배열의 인덱스 범위 안으로 압축한다.

인덱스 계산 식: index = hashCode() % 배열의 크기(16)

이 연산을 통해 다른 해시코드가 나왔더라도, 나머지 값이 같으면 배열의 같은 인덱스를 배정받게 되는 ‘해시 충돌(hash collsion)’이 매우 빈번하게 발생하게 된다.

그러면 해시 충돌이 일어났을 때 어떻게 해결할까?

HashMap 또는 HashSet은 두 데이터가 같은 상자 번호를 들고 왔을 때, 번호가 중복되었다고 밀어내지 않는다. 대신 체이닝이라는 방식을 사용한다.

체이닝 기법의 핵심은 배열의 각 인덱스에 데이터 객체를 바로 넣는 것이 아니라, 연결 리스트의 첫 번째 노드의 주소값을 넣는 것이다.

내부적으로 해시 테이블에 저장되는 데이터는 노드 객체다. Node 객체는 아래와 같이 생겼다.

static class Node<K, V> implements Map.Entry<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int var1, K var2, V var3, Node<K, V> var4) {
            this.hash = var1;
            this.key = var2;
            this.value = var3;
            this.next = var4;
        }
}

이 방식을 활용해 객체가 배열의 빈 인덱스에 들어왔다면 새로운 Node를 생성하고, 배열의 해당 인덱스에 이 노드의 주소값을 할당한다. 만약 이미 다른 노드가 인덱스에 존재한다면 equals를 사용해 값을 비교한다. 그치만 서로 값이 다르다면, 기존 노드의 맨 뒤에 새로운 노드를 연결하는 방식이다.

그러면 데이터 조회는 어떻게 하는거야?

데이터 조회는 아래와 같은 순서로 적용된다.

hashMap.get(key)를 호출하면, 입력받은 key의 해시코드로 인덱스를 먼저 계산한다.
계산된 인덱스로 배열에 다이렉트 접근한다. 여기까지는 O(1)의 시간복잡도를 갖는다.
만약 해당 인덱스(상자)가 텅 비어있다면? 찾는 데이터가 없다는 뜻이므로 즉시 null을 반환하고 종료한다.
만약 인덱스에 노드가 존재한다면, 내가 찾는 key와 그 노드의 key가 같은지 equals()로 동등성을 비교한다.
만약 겹쳐진 다른 노드라면 next 포인터를 타고 다음 노드로 이동하며 equals() 비교를 반복한다. 이 연결 리스트를 탐색하는 과정은 최악의 경우 O(N)의 시간복잡도를 갖는다.