Collection 자료구조 중 Map은 key-value쌍을 이용해서 데이터를 관리하고, Set은 데이터를 중복 없이 담을 수 있습니다.

Map과 Set은 인터페이스이기 때문에 이 둘을 사용할 때는 HashMap, HashSet처럼 구현체를 만들어줘야합니다. 이들 자료구조에서의 연산들은 상수 시간 복잡도를 기대할 수 있는데, 결정적인 이유는 해시 사용 때문입니다.

해시

x,y 좌표를 나타내는 Coord 클래스를 정의해봅니다.

private static class Coord{
	public final int x;
    public final int y;
    
    private Coord(int x, int y){
    	this.x = x;
        this.y = y;
    }
}

여기서 멤버 변수 x,y를 이용해서 특정 데이터의 대표 값을 뽑아내는 것이 해시입니다.

해시 테이블

임의의 데이터에 해시 함수를 적용하면 해시 값을 얻을 수 있습니다. 이 해시 값을 이용하면 원본 데이터를 삽입, 검색, 삭제할 수 있습니다.

검색하고자하는 key값을 입력받아서 해시 함수를 돌려 해시 값을 받환받습니다. 이 해시 값을 인덱스로 환산해서 원본 데이터 값에 접근하는 자료구조가 해시 테이블 입니다.

해시 테이블은 원본 데이터와 변환된 해시 값을 저장해 두었다가 해시 값이 입력되면 대응하는 원본 데이터를 찾아줍니다.

해시 값으로 배열의 인덱스를 참조하면 원본 데이터가 있는 리스트에 인덱스를 이용하여 바로 접근할 수 있습니다. 따라서 매우 빠른 시간에 데이터의 연산이 가능합니다.

해시 충돌

객체 안에 있는 값과 다른 객체의 값과 비교하여 같고 다름을 판별하는게 복잡한 데이터라면 해시를 통해 해시 값을 얻고 이를 비교하여 값의 동등 비교를 유사하게 할 수 있습니다.

주의할 점은 해시 값은 특정 데이터를 대표하는 값일 뿐 고유한 값이 아니다라는 것입니다. 해시값을 구하는 해시 함수를 어떻게 정의하는지에 따라 서로 다른 여러개의 데이터들이 똑같은 해시 값으로 변환할 수 있습니다.
이런 현상을 해시 충돌(hash collision)이라고 합니다.

자바에서의 해시

javadoc에 따르면 객체는 기본적으로 할당된 주소값을 이용해 해시값을 생성합니다.

public static void main(String[] args){
	Set<Coord> set = new HashSet<>();
    
    Coord coord1 = new Coord(1,2);
    set.add(coord1);
    
    Coord coord2 = new Coord(1,2);
    
    System.out.println(set.contains(coord2)); //false
}

따라서 coord1과 coord2는 같은 x,y값을 가진 객체지만 주소값(해시)이 달라 Set에 coord2가 포함되지 않는다는 결과를 반환합니다.
Set에 있는 객체의 값을 제대로 비교하려면 어떻게 해야할까요?

자바에서는 모든 클래스의 조상 클래스인 Object 클래스에서 해시를 위한 hashCode() 메서드를 제공합니다. 직접 클래스를 작성할때 이 hashCode() 메서드를 오버라딩해서 새로 정의할 수 있습니다.

javadoc에 따르면 hashCode() 메서드를 오버라이딩할 때는 다음 규칙을 따라야 합니다.

• 하나의 객체에서 hashCode() 메서드를 여러번 호출하더라도 항상 같은 값을 반환해야 한다.

• 두 객체가 equals() 메서드로 같다로 정의되면 hashCode() 메서드도 값은 값을 반환해야 한다.

• 두 객체가 equals() 메서드로 다르다고 정의되도 hashCode() 메서드는 같은 값을 반환할 수 있다.(해시 충돌)

hashCode() 오버라이딩

이 규칙들을 지키면서 해시 충돌도 최대한 피하는 방향으로 hashCode() 메서드를 정의해야합니다. 코딩테스트에서 해시 함수에 많은 시간을 소비할 수 없으므로 다음과 같은 방법을 이용하면 좋습니다.

클래스의 모든 변수를 문자열로 묶은 후 String 클래스의 hashCode() 메서드를 호출하는 방법입니다. 이때 중복을 피하기 위해 각 멤버 변수를 이어 붙일 때 임의의 문자를 하나씩 연결하면 해시 충돌을 더 잘 피할 수 있습니다.

private static class Coord{
	public final int x;
    public final int y;
    
    private Coord(int x, int y){
    	this.x = x;
        this.y = y;
    }
    
    @Override
    public int hashCode(){
     return (x + "," + y).hashCode();
    }
}

이제 서로 다른 두 객체를 다시 비교해보겠습니다.

public static void main(String[] args){
	Set<Coord> set = new HashSet<>();
    
    Coord coord1 = new Coord(1,2);
    set.add(coord1);
    
    Coord coord2 = new Coord(1,2);
    
    System.out.println(set.contains(coord2)); //false
}

hashCode()를 오버라이딩하여 해시 값은 같은 값을 반환하지만 여전히 두 객체를 같은 데이터로 인식하지 않습니다. 아까 hashCode() 오버라이딩 조건에서 세 번째 조건을 보면 해시 충돌이 허용됨을 알 수 있습니다.

HashSet 클래스 또한 이렇게 해시 총돌이 일어날 수 있다는 것을 알고 있습니다. 따라서 해시 값이 같으면 해시 충돌이 발생한 것인지 아닌지 검사합니다. 이 검사는 equals() 메서드로 수행합니다.

equals() 오버라이딩

hashCode() 메서드로 같은 해시 값을 반환했지만 equals() 메서드를 이용한 검사 결과가 false로 나온다면 이는 해시 충돌로 간주하여 서로 다른 데이터로 인식합니다. 따라서 hashCode() 메서드를 정의할 때는 equals() 메서드를 항상 같이 정의해야 합니다.

private static class Coord{
	public final int x;
    public final int y;
    
    private Coord(int x, int y){
    	this.x = x;
        this.y = y;
    }
    
    @Override
    public int hashCode(){
     return (x + "," + y).hashCode();
    }
    
    @Override
    public boolean equals(Object obj){
    	if(!(obj instanceof Coord)) return false;
        Coord o = (Coord) obj;
        return x == o.x && y == o.y;
    }
}

이제 두 객체가 같은 데이터를 나타내는지 여부 검사를 다시 검사해보겠습니다.

public static void main(String[] args){
	Set<Coord> set = new HashSet<>();
    
    Coord coord1 = new Coord(1,2);
    set.add(coord1);
    
    Coord coord2 = new Coord(1,2);
    
    System.out.println(set.contains(coord2)); //true
}

드디어 두 객체를 HashSet을 이용하여 포함 여부를 검사 할 수 있습니다.