[Think Data Structures] 해싱(hashing)의 동작방식

해싱의 동작방식

---

해시함수의 근본적인 요구사항은 같은 객체는 매번 같은 코드를 만들어야된다는 것이다.

불변객체(immutable object)일 때는 상대적으로 쉽지만, 가변 객체(mutable object)일 때는 고민이 필요하다.

불변객체(immutable object)의 예

객체를 생성할 때 항상 생각해야하는게 equals, hashcode 의 오버라이드 이다.

두 메서드는 일치해야 하는데, equals 메서드가 true 이면 해시코드 또한 같아야 한다. 하지만 이 요구사항은 단방향 이기 때문에 두 객체의 해시 코드가 같더라도 그들이 같은 객체일 필요는 없다.

String 객체를 캡슐화하는 SillyString 클래스를 정의

public class SillyString{
    private final String innerString;
    
    public SillyString(String innerString){
        this.innerString = innerString;
    }
    
    public String toString(){
        return innerString;
    }
    
    @Override
    public boolean equals(Object other){
        return this.toString().equals(other.toString());
    }
    
    @Override
    public int hashCode(){
        int total = 0;
        for(int i=0; i<innerString.length(); i++){
            total += innerString.charAt(i);
        }
        return total;
    }
}

SillyString 클래스의 해시 함수는 정확하게 동작한다. 하지만 좋은 성능을 보장하지는 못한다.

이는 많은 서로 다른 문자열들이 같은 해시 코드로 변환되기 때문이다.

두 문자열에 같은 문자가 순서만 다르게 포함되어 있다면 해시코드가 같다. 심지어는 같은 글자가 아니더라도 같음 ('ab', 'ba'), ('ac', 'bb')

많은 객체가 동일한 해시 코드를 갖는다면 결국 같은 하위 맵으로 몰리게 된다.

어떤 하위 맵(A)에 다른 맵(B)보다 많은 엔트리가 있으면 k개의 하위 맵으로 인한 성능 향상은 k보다 줄어들게 된다.

그래서 해시 함수의 목표 중 하나가 균등(uniform)해야 한다는 것이다.

즉, 일정 범위에 있는 어떤 값으로 고루 퍼지도록 해시 코드를 생성해야 한다.

해싱과 변형

String 클래스는 불변이며, innerString 변수가 final로 선언되었기 때문에 SillyString 클래스 또한 불변

SillyString 객체를 생성하면 innerString 변수는 다른 String 객체를 참조할 수 없고 참조하는 String 객체 또한 변경할 수 없음 따라서 항상 같은 해시 코드 값을 갖게됨

가변객체라면 어떤 일이 일어날까? 

SillyArray 클래스 정의

public class SillyArray {
    private final char[] array;
    
    public SillyArray(char[] array){
        this.array = array;
    }
    
    public String toString(){
        return Arrays.toString(array);
    }
    
    @Override
    public boolean equals(Object other){
        return this.toString().equals(other.toString());
    }
    
    @Override
    public int hashCode(){
        int total = 0;
        for(int i=0; i<array.length; i++){
            total += array[i];
        }
        System.out.println(total);
        return total;
    }
    
    public void setChar(int i, char c){
        this.array[i] = c;
    }
    
}

SillyArray 클래스는 배열에 있는 문자를 변경할 수 있음

SillyArray 객체를 생성하고 맵에 추가합니다.

SillyArray array1 = new SillyArray("word1".toCharArray());

map.put(array1, 1); // 해시코드 461

array1.setChar(0, 'C'); // 해시코드 441

Integer value = map.get(array1); 

변형 후 해시코드가 변경이되어 잘못된 해위 맵을 조회할 수 있다. 이러한 상황에서는 키가 맵에 있어도 찾을 수 없게 된다.

일반적으로 해싱을 사용하는 자료구조에서 가변 객체를 키로 사용하는 것은 위험함. (변경이 되지 않음을 보장한다 해도 피하는 것이 좋음)