[Java] 해시 충돌

 

오늘은 해시 충돌에 대해서 알아보고자 한다. 얼마전 hashCode() 와 equals() 메소드를 파헤쳐보았다. 이 글을 좀 더 쉽게 읽기 위해서는 아래의 링크를 클릭해서 해당 메소드들을 필수적으로 이해를 해야한다. 

 

[Java] equals 와 hashCode

 

 

개념

해시 충돌 그게 무엇인가?? 

코딩 테스트를 준비를 하면서 Java 개발자들은 HashMap 이라는 자료구조를 정말 많이 쓴다. 

혹시 HashMap 이 어떠한 방식으로 데이터가 저장되는지 깊게 생각해본 적이 있는가?

 

오늘은 HashMap 자료구조에 대해서 자세히 살펴보려고 한다. 

해당 자료구조는 Key-Value 형식으로 이루어져있는 것은 Java 개발자라면 기본적으로 알고 있을 것이다. 

 

여기서 알아둬야하는 점은 HashMap은 배열로 이루어져있다. 

쉽게 말해서 Key는 배열의 인덱스를 뜻한다고 보면 된다. 하지만 배열은 무한하지 않다. 

메모리는 무한이 아니기 때문에 한정된 크기를 가지고 있다는 뜻이다.

 

지금부터 이 배열을 "해시 버킷" 이라고 부르겠다. 

 

 

이전 포스팅을 참고해보면 해시 자료구조에서는 hashCode를 먼저 비교를 하고, 결과가 같다면 equals로 추가로 비교한다고 말을 했다. 왜 hashCode를 먼저 비교를 하냐? 

 

객체의 동일성을 비교할 때 내용물을 하나하나 비교(equals()) 하기 전에 해시값을= 비교를 먼저해준다면 비용을 낮출 수 있기 때문에 hashCode를 먼저 비교를 하는 것이다. 

 

하지만 여기서 중요한 점이 있다. 아래의 코드를 살펴보자. 

 

String a = "Z@S.ME";
String b = "Z@RN.E";

if(a.hashCode()==b.hashCode()) System.out.println("same");
else System.out.println("different");

//출력은 same

 

분명 String a 와 String b 는 다른 문자열을 담고 있다. 하지만 hashCode 값은 동일하다는 점이다. String의 hashCode() 를 살펴보자. 

 

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

 

 

문자열 a 와 b의 hashCode() 를 호출하면 문자열의 각각의 Byte의 아스키 코드 공식을 통해 더해진 총합을 hash 값으로 사용하고 있다. 즉, 문자열 a,b 가 서로 내용물이 다르더라도 같은 hash값을 반환할 수 있다는 점이다. 

 

Map <String, Integer> map = new HashMap<>(); 
map.put(a,1); 
map.put(b,1); 
System.out.println(map.size());
//2

 

그렇다면 hashcode가 같으니까 HashMap 에다가 한 번 담아 보자. 사이즈가 1이 뜰 줄 알았지만 2가 나온다. 

hashcode 를 key 로 가졌으면 동일한 hashcode를 갖는 문자열 a,b를 넣으면 결국 마지막에 넣은 놈으로 덮어 쓰여져야하는거 아냐??? 

 

답은 아니다. 여기서 오늘 포스팅 할 내용이 나온다. 

 

해시 충돌 

해시 충돌이란 해시함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 즉, 서로 다른 두개의 문자열이 같은 해시값을 가지면서 같은 버킷을 가리키게 되는 것이다. 이러한 경우, 크게 두 가지 알고리즘을 통해 해결할 수 있다. 

 

체이닝 (Chaining) 

 

 

그림을 먼저 살펴보자. John Smith 와 Sandra Dee 는 내용물이 달라도 해시값이 동일한 문제점이 발생했다. 

이럴 경우 해당 해시값 위치의 버킷에다가 연결을 해주는 것이다. 그러니까 John Smith 객체를 먼저 HashMap 에다가 put 을 했다고 가정해보자. 그리고나서 Sandra Dee 객체를 put할 때 먼저 152 버킷으로 간다. 근데 이미 연결되어 있는 놈이 있네?? 그러면 그 놈 뒤에다가 갖다 붙인다는 뜻이다. 

 

그렇다면 Sandra Dee 객체를 찾을 때는 어떻게 하는가? 

 

먼저 HashCode 기반으로 비교를 한다. 하지만 지금 152으로 일치하니까 사슬로 연결되어 있는 놈들을 하나하나 equals 연산을 통해서 비교를 하는 것이다. 이 방식이 체이닝 방법이다. Java에서는 기본적으로 체이닝 방법을 사용하기 때문에 어떤식으로 돌아가는지에 대해선 알고 있어야한다. 

 

특징

연결 리스트만 사용하면 된다. (계산식 x)

연결 리스트가 쌓이면 탐색에 O(n) 이 소요된다.

데이터가 채워짐에 따라 성능이 적게 감소된다.

 

 

개방 주소법 (Open Addressing) 

개방주소법은 해시 충돌이 발생했을 시 정해진 규칙에 따라 비어있는 다른 버킷을 결정해서 해당 버킷에 데이터를 보관하는 것이다. 크게 3가지 방식이 있다. 

 

• 선형 탐색(Linear Probing) - 해시충돌 시 다음 버킷 또는 비어 있지 않다면 몇 개 건너뛰어 데이터를 삽입.
• 제곱 탐색(Quadratic Probing - 해시충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입.
• 이중 해시(Double Hashing) - 해시충돌 시 해시를 한번 더 적용해서 나온 버킷에 데이터를 삽입.

 

이게 무슨 말인가 할 수 있다. 선형탐색에 대해서 알아보면 나머지도 쉽게 이해할 수 있을 것이다. 

 

 

지금 52라는 해시 값에 a(172)라는 객체가 들어있다고 가정해보자. 여기서 만약 52 라는 해시 값을 갖는 b라는 객체를 넣을려고 하는데 이미 존재하네?? 

 

그러면 그 밑에를 살펴보는 거다. 근데 밑에도 있네? (53)

그러면 그 밑에를 살펴보는 거다. 근데 밑에도 있네? (54)

그러면 그 밑에를 살펴보는 거다. 근데 밑에도 있네? (55)

그러면 그 밑에를 살펴보는 거다. 근데 밑에도 있네? (56)

그러면 그 밑에를 살펴보는 거다. 이제 없네? (57)

 

그러면 57에 넣으면 되는 것이다. 

 

선형탐색에 대해서 이해가 되었다면 제곱 탐색과 이중 해시 방식도 짐작 올 것이다. 쉽게 말하자면, 버킷을 어떻게 뛰어넘을 것인가에 대한 차이라고 생각하면 된다. 

 

특징

n차 충돌이 발생할 수 있다.

메모리 효율이 높다.

다른 자료구조가 필요없다.

사입, 삭제 오버헤드가 적다.

데이터가 적을 때 유리하다.

 

 

---

 

 

 

 

위의 그림은 체이닝 기법과 개방 주소법 선형 탐색의 차이를 비교한 것이다. 버킷은 80% 이상이 가득 차게 되면 선형 탐색의 경우 캐시 미스가 급격하게 올라간다. 위에서 언급했던 것처럼 충돌이 여러번 발생해서 5번을 확인을 해야 빈 공간을 찾을 수 있었다. 즉, 버킷이 많이 채워져 있다면 그런 문제점이 발생할 수 있다는 점이다. 

 

하지만 해시 알고리즘이 일반적으로 충분히 빠르기도 하고 메모리 사용량도 과도하다고 간주되지는 않는다. 그래서 이러한 해시 충돌 전략은 메모리가 과도하지 않다면 성능 차이는 미미하다고 한다. 

 

 

https://jaehoney.tistory.com/169

https://mhwan.tistory.com/59

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=cestlavie_01&logNo=220551648015