티스토리 뷰

1) 개요


지난 포스팅에서 HashMap과 HashTable을 알아보며 Map 인터페이스를 상속한 구현체임을 알아봤다.


키-값을 통해 자료를 관리하는 구현체들을 성능상 차이점을 들어 비교를 했었다.

지속적으로 개선되고있는 HashMap의 사용을 권장하는 식으로 마무리 하였는데, 관련 자료를 찾던 중 이러한 주장은 오류가 있다는 것을 발견하였다.


Naver D2에서 Hello world의 포스팅 내용에 따르면 


" HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하는 것에 있기 때문에, 이 둘 사이에 성능과 기능을 비교하는 것은 큰 의미가 없다고 할 수 있다."


즉 "같은 환경에서라면 보조 해시 함수를 사용하는 HashMap이 성능상 이점이 있는 것은 맞지만 상황에 따라 HashTable을 사용하는 것이 옳을 수도 있다."로 결론 내릴 수 있을 것 같다.


여기까지 지난 포스팅에 대한 피드백을 마치고 이번 주제인 해시충돌에 대해 알아보겠다.


2) 해시 충돌 (hash collision)


그림 1 함수에서의 맵


해시함수를 사용하여 해시값으로 특정 자료를 분류하는데 있어 항상 따라오는 문제로 충돌에 대한 이슈가 있다.


특히 암호값을 해시함수를 사용한 값을 통해 사용자 인증을 하는(리눅스의 passwd)시스템의 경우 서로 다른 값을 해싱한 결과가 같을 수 있는 문제는 큰 문제라 할 수 있다. 

이런 보안적인 문제는 다른 포스팅에서 다루도록 하고 이 포스팅은 자바의 HashMap에서 키값을 해싱하는 과정에서의 충돌만을 다루도록 하겠다.


해시맵에서 키로 사용되는 각종 자료형들에 대해 완벽한 해시 함수를 제공할 수는 없다.

서로가 구별되거나 Number객체는 객체가 나타내려는 값 자체를 해시 대상 값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있지만, String이나 POJO(plain old java object)에 대하여 완전한 해시 함수를 제작하는 것은 사실상 불가능 하다.


또한 자바에서 해시값을 생성하는 메소드인 hashCode()의 결과 자료형은 int이다. 32비트 정수 자료형으로는 완전한 자료 해시 함수를 만들 수 없다.

객체의 수가 2의 32승보다 많을 수 있고, 모든 hashMap이 2의 32승만큼의 배열을 가지고 있을 수는 없기 때문이다.


따라서 HashMap을 비롯한 많은 해시 함수를 이용하는 associative array(Dictionay, Map, Symbol Table 등) 구현체에서는 메모리 절약을 위해 실제 해시 함수의 표현 정수 범위 N보다 작은 M개의 원소가 있는 배열만을 사용한다. 


int index = X.hashCode() % M;  


다음과 같이 객체에 대한 해시 코드의 나머지 값을 해시 버킷 인덱스 값으로 사용한다.


이런 방식을 사용하면, 서로 다른 해시 코드를 가지는 서로 다른 객체가 1/M의 확률로 같은 해시 버킷을 사용하게 된다. 이것이 자바의 해시 충돌 문제이다. 해시 함수 구현상의 문제가 아닌 또 다른 종류의 해시 충돌인 셈이다.


3) 해시 충돌 회피 방법


이런 충돌이 일어나도 키-값 쌍데이터를 안정적으로 저장하고 조회할 수 있도록 하는 대표적인 방법으로 두가지가 있다.



대표적으로 Open Addressing과 Separate Chaining이 있다.


첫 번째로 Open Addressing은 해시 충돌이 발생하면 다른 해시버킷에 해당 자료를 삽입하는 방식이다. 


두 번째인 Separate Chaining은 충돌 시 해당 버킷값을 첫 부분으로 하는 링크드 리스트로 해결한다.


첫 번째인 Open Addressing은 데이터 개수가 적다면 Separate chaining보다 더 성능이 좋다. 하지만 배열의 크기가 커질수록(M값) 연속된 공간에 데이터를 저장하여 캐시효율이 높다는 장점이 사라지게 되어 Separate chaining을 사용하는 것이 더 현명 해 보인다.


또한 remove()호출 빈도에 따라 효율이 달라진다. 삭제 처리 시 효율이 높은 linked list방식인 Separate chaining이 open addressing보다 remove() 메소드 호출이 잦은 HashMap에서 더 좋은 효율을 보인다.


자바는 HashMap에서 Separete Chaning방식을 채용하고 있다.


위에서 설명한 바와 같은 이유들로 왜 이방식을 채용하는 지는 충분한 이해가 될 것 같다.



4) 향상된 충돌 회피 (Java8)


최신 버전인 Java8에서는 더 향상된 방법을 사용하여 충돌을 회피한다.


이는 HashMap에 대한 지속적인 개발이 이뤄지고 있다는 것을 반증한다.


탐색에 있어 더 높은 효율을 보이는 트리를 접목시켰다.


하나의 버킷에 충돌이 집중되는 현상을 해결하기 위한 방법으로 충돌된 키-값 쌍의 데이터가 8개가 모이면 링크드 리스트를 트리로 변경한다. 해당 값이 6개에 이르면 다시 링크드 리스트로 변경시킨다. 차이값이 8-7이 아니라 8-6인 이유는 잦은 링크드 리스트와 트리로의 변경으로 인한 성능저하를 막기 위함이라 한다.


하지만 트리의 특성 상 트리 순회 시 사용하는 판단 기준이 대소에 대한 구분이 있어야 하는데 이를 자바8에서는 레드 블랙 트리라는 것을 적용시켰다.


판단 기준으로 해시 함수 값을 사용하고 Total Ordering?을 해결하기 위해 tieBreakOrder()메소드로 해결한다.


static int tieBreakOrder(Object a, Object b) {

         // TreeNode에서 어떤 두 키의comparator 값이 같다면 서로 동등하게 취급된다.
         // 그런데 어떤 두 개의 키의 hash 값이 서로 같아도 이 둘은 서로 동등하지 
         // 않을 수 있다. 따라서 어떤 두 개의 키에 대한 해시 함수 값이 같을 경우, 
         // 임의로 대소 관계를 지정할 필요가 있는 경우가 있다. 
        }



5) 정리


해시맵과 충돌, 회피, 향상된 부분을 겉핥아 보았다.


이 외에도 보조 해시 함수, String 객체에 대한 해시 함수, 해시 버킷 동적 확장(일정 키-값 데이터가 쌓이면 버킷의 개수를 2배로 늘린다 = 해시 충돌 확률이 떨어진다) 등 다뤄야 할 문제가 많지만 자바의 해시충돌이라는 큰 틀에서 필수적으로 다뤄야할 내용을 보았다.


정리하자면


자바에서 말하는 해시충돌은 실제 해시 범위보다 적은 M만큼의 배열을 선언하여 메모리의 효율을 높였고 해시 값의 % M 값을 버킷값으로 삼아 이것이 충돌하는 것을 뜻한다.


해결 방법으로 Separate Chaining과 보조 해시 함수를 사용하고 자바8에서는 링크드 리스트 대신 트리(Red-black Tree)를 사용한다.


다음 포스팅은 JVM의 Garbage Collector를 다뤄볼 예정이다.


6) 출처


http://d2.naver.com/helloworld/831311 (이 포스팅의 모든 내용은 이 출처의 내용을 정리한 것이나 다름없다)





댓글
댓글쓰기 폼