[자료구조] 16. 해시 충돌

Set 자료구조들을 포스팅 하다가 중요한 개념인 해시 충돌에 대해서 짚고 넘어가야 할것 같아 따로 포스팅을 하게 됐다. 해시 테이블에서만 뿐만 아니라 해시 기법 자체가 여러 곳에서 사용되기 때문에 해시 충돌에 대해서는 항상 염두에 두고 있어야 한다고 생각을 했기 때문이다.

 

해시 충돌

(지난 포스트에서도 다룬 내용임)

 

자바에서는 hasCode() 라는 간편한 함수의 존재로 해시함수를 굳이 구현할 필요가 없다. hashCode()를 통해 객체의 주소값을 이용하여 해시 알고리즘에 의해 생성된 고유의 정수값을 반환할 수 있다. 즉, 객체가 같은 메모리 주소를 가리키고 있다면 같은 정수값을 얻을 수 있다.

 

int a = X.hashCode();

 

그러나 객체가 같은 주소를 가리킬 경우에는 주의해야한다. 객체가 같은 내용을 지니더라도 가리키는 주소가 다르다면 다른 값을 지니기 때문이다.

 

public class Main {
    public static void main(String[] args) {
        // a 와 b 는 같은 내용을 담고 있고 각각 new 연산자로 다른 객체이다.
        HashingExample a = new HashingExample("aaa");
        HashingExample b = new HashingExample("aaa");

        // c 는 a 의 주소를 복사 받았다 (shallow copy)
        HashingExample c = a;

        System.out.println("a's  hashCode() : " + a.hashCode());
        System.out.println("b's  hashCode() : " + b.hashCode());
        System.out.println("c's  hashCode() : " + c.hashCode());
        
    }

    static class HashingExample {
        String str;

        public HashingExample(String str) {
            this.str = str;
        }
    }
}

a 객체와 b 객체는 내용이 같더라도 서로 다른 주소에 할당된 다른 객체이기 때문에 다른 값이 나오고 a 와 c는 같은 주소를 갖기 때문에 같은 값을 갖는다. 우리가 쓰는 String, int, double 등의 자료형들은 hashCode()를 오버라이드 하여 객체 내용이 비교될 수 있도록 재정의하고 있다.

 

그러나 hashCode()를 사용하더라도 1차적인 문제가 있다. int 형 범위를 예로 들어보자. int 형은 32비트로 표현되는 자료형이다. 즉 2^32의 경우의 수를 가질 수 있다는 의미이다. 2^32도 매우 큰 수임에는 틀림없지만 모든 객체를 표현하기에는 한계가 있다.

 

설령 생성되는 객체가 우연히 모두 2^32로 표현이 가능할지라도 문제는 그만큼의 배열 공간을 생성해야한다는 점이다. 이는 메모리 낭비가 심할뿐더러 Java에서는 단일 배열에 대해 약 21억 정도의 크기까지만 생성이 가능하다. 그렇기에 메모리 낭비를 줄이기 위해서 배열의 사이즈를 줄여서 사용한다. 예를 들어 M개의 인덱스를 갖고 있는 배열(테이블)이 있을 때 다음과 같이 인덱스를 지정한다.

 

int index = X.hashCode() % M;

 

이때 자바에서는 hashCode()가 음수값을 반환할 수도 있기 때문에 절댓값으로 양수로 변환하여 사용하는 것이 필요하다.

 

int index = Math.abs(X.hashCode()) % M;

 

하지만 이렇다 할지라도 해시 충돌의 경우와 버킷(배열)의 크기에 따른 값은 같은 인덱스를 참조하는 일이 발생할 수 밖에 없다. 이를 해결하는 방법은 크게 두가지로 나뉜다. 여러 방법이 있지만 두개의 방법을 응용한 방법이므로 두개를 이해한다면 나머지를 이해하는데 도움이 될 것이다.

 

해시 충돌 해결 방법

 

Open Addressing

Open Addressing은 위 그림과 같이 데이터를 삽입할때 해당 버킷이 사용중이라면 다른 해시 버킷에 데이터를 삽입하는 방식을 말한다. 아래 설명된 기법들은 데이터를 저장, 조회하는 기법들이다.

• 선형 탐사 (Linear probing)
  • 충돌이 발생했을 때 그 옆자리가 비어있는지 살펴보고, 비어있을 경우 그 자리에 대신 저장하는 방식. 위의 이미지가 선형 탐사의 그림이다.
  • 계산이 단순하다는 장점이 있으나 검색에 많은 시간이 소요되며 테이블 내에 데이터들이 일정한 키 값으로 모이는 현상이 발생한다.
• 제곱 탐사 (Quadratic probing) 
  • 선형 조사법이 n 칸 옆을 검사한다면 제곱 탐사는 n^2 칸 옆을 검사하는 것이다.
  • 일정한 키 값으로 모이는 현상은 방지하겠으나 모든 공간을 다 검사하지는 않게 된다.
• 이중 해싱 (Double hashing)
  • 해시 함수를 이중으로 두어서 하나는 최초의 주소를 얻고 다른 하나는 충돌이 발생했을 때 빈칸을 찾을 인덱스를 얻기 위해 사용된다.
• 재해싱 (Rehashing)
  • Hash Table의 크기를 늘리고 크기에 맞춰 테이블 내 모든 데이터를 다시 해싱하는 방법이다.
  • 다시 재배치가 되는 것은 좋으나 상당히 많은 비용이 발생한다.

 

[장점]

• 해시 충돌이 일어날 가능성이 적기 때문에 데이터의 개수가 작을수록 속도가 빨라진다.
• 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 좋아진다.

[단점]

• 해시 충돌이 발생하면 해당 객체의 인덱스 값이 바뀐다.
• 부하율 (load factor) 즉, 테이블에 저장된 데이터가 많아질수록(= 밀도가 높아질수록) 성능이 급격히 저하된다.

---

Separate Chaining

Separate Chaining은 Open Addressing과 다르게 추가적인 메모리를 사용하여 동일한 버킷에 값이 있다면 링크드 리스트를 활용하여 해당 값을 뒷 노드로 저장하는 방식을 취한다. 자바에서는 Separate Chaining을 적용하고 있다. 더불어 자바 8 이상에서는 데이터의 사이즈가 커지면 List 대신에 Tree의 값을 사용한다. 데이터 개수가 일정 이상 많아지면 리스트보다 이진 트리(Binary Tree)를 사용하는 것이 성능상 이점이 있기 때문이다.

 

[장점]

• 해시 충돌이 일어나더라도 연결리스트로 노드가 연결되기에 index가 변하지 않는다.
• 테이블의 각 인덱스는 연결리스트로 구현되기 때문에 데이터 개수의 제약을 거의 받지 않는다.

[단점]

• 부하율 (load factor) 에 따라 선형적으로 성능이 저하된다. 부하율이 작을 경우에는 Open Addressing 방식이 더 빠르다.

 

부하율 

보통 데이터가 70% ~ 80% 정도 채워질 경우 성능이 저하된다고 한다. 그래서 Java에서도 부하율 값을 0.75로 두고 있다.