Java의 HashSet에서 String, Object의 비교

자바에서는 고유한 객체들을 담을 수 있는 Set 자료구조, 정확히는 인터페이스를 제공하고 있다. 이를 구현한 객체는 HashSet, TreeSet, LinkedHashSet 등이 있으며 자주 사용하는 것은 HashSet일 것이다.

 

그런데 요즘 LeetCode에서 알고리즘 공부를 하다가 HashSet에 String 객체를 넣었을 때 이를 어떻게 비교하는 거지?라는 궁금증이 들었다. 분명 String도 결국엔 객체고 일반적으로 서로 다른 객체끼리는 다르다고 비교되는데 문자열은 어떻게 비교되는 것일까? 문득 HashSet의 contains 메서드를 사용하다가 이와 같은 의문이 들었기 때문에 좀 조사해보았다.

 

예전에 학교 다닐 때 자바 수업에서도 귀가 아프게 들었던 얘기지만 String 클래스의 equals, hashCode 메서드는 다음과 같이 재정의 되어있다.

public boolean equals​(Object anObject)
Compares this string to the specified object. The result is true if and only if the argument is not null and is a String object that represents the same sequence of characters as this object.

public int hashCode()
Returns a hash code for this string. The hash code for a String object is computed as s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

객체가 동일한지 비교하는 equals 메서드는 null이 아닌 String 객체에 대하여 각각의 문자(character)들이 완전히 일치하면 동일하다고 반환한다. 객체의 해시값을 구하는 hashCode는 문자열의 각 문자에 대하여 일정한 규칙의 연산을 수행한 값을 합산하여 반환한다. 그렇기 때문에 같은 문자를 가진 String 객체끼리는 같은 객체라고 판단되는 것이다.

 

그렇다면 이 String을 Set에 넣어서 contains로 비교할 때는 어떻게 되는 것일까? 이를 위해서는 HashSet이 내부적으로 어떻게 구현되는지 알아볼 필요가 있다. 자바 문서에서 HashSet 클래스를 조사해보면 다음과 같은 설명이 있는 것을 볼 수 있다.

This class implements the Set interface, backed by a hash table (actually a HashMap instance).

즉 Set 인터페이스를 구현한 이 HashSet 객체는 내부적으로 HashMap 객체를 생성하여 사용하고 있다는 것이다. 이 HashMap 객체는 키 값을 해시하여 사용하기 때문에 속도가 매우 빠른데 Map 인터페이스는 키와 값으로 이루어져 있다. 그러면 키를 HashSet에 등록된 객체로 사용한다면 값으로는 뭘 넣어야 할까? 여기서는 아무런 값이나 넣어도 되지만 Java에서는 PRESENT라는 이름의 Object 객체를 삽입하고 있다. HashSet에 필요한 것은 HashMap을 이용하여 객체들의 중복을 방지하는 것이기 때문에 객체 자체를 HashMap의 키로 사용하기만 하면 되기 때문이다. 자세한 내용은 링크를 참고해보자.

How HashSet Works Internally In Java?

그렇기 때문에 리터럴 방식으로 생성한 문자열이든 객체 방식으로 생성한 문자열이든 HashSet 내부에서는 equals, hashCode 메서드로 비교하여 같은 문자열이라면 같은 HashMap에 포함되어 있다고 판단하여 HashSet 자체에서의 중복을 판단하는 것이다. 이는 다음과 같은 코드로 알 수 있다.

import java.util.Set;
import java.util.HashSet;


public class Main
{
    private static Set<String> set = new HashSet<>();
	public static void main(String[] args) {
		set.add("1,2");
		
		System.out.println(set.contains("1,2")); // true
		System.out.println(set.contains(new String("1,2"))); // true
		System.out.println(set.contains(String.format("%d,%d",1,2))); // true
	}
}

HashSet에 리터럴 방식으로 생성한 문자열 "1,2"를 넣었을 때 세 가지 방법(리터럴, 객체 생성, format 메서드)으로 생성한 같은 내용의 문자열이 HashSet에 포함되어 있는지 contains 메서드로 확인한 결과 모두 true를 반환하는 것을 볼 수 있었다.

 

그렇다면 일반 객체는 어떨까? 이때는 equals, hashCode 메서드가 재정의되지 않았기 때문에 false가 출력된다.

import java.util.Set;
import java.util.HashSet;


class Test{
    private int id;
    public Test(int _id){
        id = _id;
    }
}

public class Main
{
    private static Set<Test> set = new HashSet<>();
	public static void main(String[] args) {
		set.add(new Test(1));
		
		System.out.println(set.contains(new Test(1))); // false
	}
}

그렇기 때문에 equals, hashCode 메서드를 재정의해주면 String 객체처럼 HashSet에서도 동일한 객체를 비교할 수 있는 것을 볼 수 있다.

import java.util.Set;
import java.util.HashSet;


class Test{
    private int id;
    public Test(int _id){
        id = _id;
    }
    
    @Override
    public boolean equals(Object t){
        if(t instanceof Test){
            return id == ((Test)t).id;
        } else {
            return false;
        }
    }
    
    @Override
    public int hashCode(){
        return id;
    }
}

public class Main
{
    private static Set<Test> set = new HashSet<>();
	public static void main(String[] args) {
		set.add(new Test(1));
		
		System.out.println(set.contains(new Test(1))); // true
	}
}

이때 hashCode 메서드를 재정의하지 않으면 여전히 HashSet에서 동일한 객체를 찾지 못한다. 이는 HashSet 내부의 HashMap에서 객체를 해싱한 값(hashCode)을 사용하기 때문이라고 추측된다. 만약 재정의하지 않는다면 Object의 hashCode 메서드에서는 객체의 주소 값을 반환하기 때문에 따로 생성된 객체들은 당연히 HashMap에서 찾을 수 없다. 그래서 HashSet에 포함되어 있지 않다고 판단하는 것이다.

import java.util.Set;
import java.util.HashSet;


class Test{
    private int id;
    public Test(int _id){
        id = _id;
    }
    
    @Override
    public boolean equals(Object t){
        if(t instanceof Test){
            return id == ((Test)t).id;
        } else {
            return false;
        }
    }
}

public class Main
{
    private static Set<Test> set = new HashSet<>();
	public static void main(String[] args) {
		set.add(new Test(1));
		
		System.out.println(set.contains(new Test(1))); // false
	}
}