chirho's network world

이 글은 NBP(네이버 비즈니스 플랫폼)의 웹플랫폼개발랩(송기선)에서 낸 "Java HashMap"은 어떻게 동작하는가?"라는 블로그 포스팅을 읽은 감상 및 Java가 아닌 우리 플랫폼에 내재화하기 위한 아이디어를 기술한다.

Java의 특징 중 하나가 강력한 라이브러리의 제공인 것은 주지의 사실이다. JDK가 지속적으로 버전업 하면서 라이브러리의 성능, 기능 개선도 이루어지는 점은 C를 주력 개발 언어로 사용하는 사람에게는 부러운 일이자 아쉬운 일이기도 하다.

이번에 블로그로 접한 HashMap은 기존에는 HashTable로 불린 자료구조로 Linux 커널에서 주로 사용하는 HashTable과 일견 통하는 측면이 있다. 물론 Linux 커널은 라이브러리의 도움을 받지 못하기 때문에 직접 HashTable을 구현하였고, 특히 Lock 문제가 성능 뿐 아니라  안정성에도 심각한 영향을 끼칠 가능성이 있으므로 변경 적용이 쉽지 않은 편이다. 그럼에도 불구하고 JDK의 버전업에 따라 HashTable이 HashMap으로 변경되고 그 안에서도 개선되는 과정은 많은 Insight를 준다.

블로그의 내용은 그다지 길지 않고 요약을 잘 할 자신도 없기 때문에 이 부분은 원본을 참고하도록 제안하며, 내용 중 a) 잘 모르거나 대충 알던 것을 정리하게 된 부분과 b) Linux 커널에도 적용하면 좋을 부분을 위주로 글을 써 보련다.

1. collision 회피 방법

1-1. associative array에서는 hash function을 결과값 범위(N)보다 작은 M개의 원소가 있는 배열을 사용

1-2. 따라서, 서로 다른 hash value를 가지는 객체가 1/M의 확률로 같은 hash bucket을 사용하게 됨

1-3. 이를 collision이라고 하며 이를 회피하기 위한 방법으로 open addressing과 separate chaining을 사용하게 됨

1-4. 리눅스는 separate chaining을 기본으로 사용하고 있고, JDK도 마찬가지.

1-5. 둘 다 worst case O(M).

1-6. open addressing은 연속된 공간에 데이터를 저장하기 때문에 separate chaining에 비해 캐시 효율이 높다.

1-7. open addressing은 데이터의 개수가 적은 경우 적합. 데이터가 많아지면 캐시 효율이 떨어져 open addressing의 장점이 사라지고, collision 가능성이 훨씬 커지기 때문(다른 hash value에 의해서도 내 hash bucket이 잠식될 가능성)에 단점이 부각

1-8. 또한, remove 작업이 빈번하면, open addressing은 비효율적.

2. HashMap(Table)의 collision 대처법

2-1. collision 개수가 일정 횟수(8)를 넘어서면 링크드 리스트를 트리로 변경

2-2. Linux의 CT hash는 collision이 일어날 가능성이 큰 데, 이를 경우에 따라 트리로 변경하면 collision시 적절한 대응이 가능할 듯. (테스트 필요) !!

2-3. collision 개수가 일정 횟수(6) 이하로 떨어지면 트리에서 링크드리스트로 변경

2-4. 상호 변환 횟수가 다른 이유는 경계값에서 증감하는 worst cast에서 drastic한 성능 하락을 막기 위한 tip!

2-5. 트리 구조체는 Red-Black Tree 사용.

3. hash bucket 동적 확장

3-1. 해시 버킷의 사이즈에 따라 메모리와 성능상 trade-off 발생

3-2. 해시를 동적으로 확장해서 데이터 사이즈에 따라 절충 가능

3-3. 데이터 사이즈를 미리 알고 있는 경우에는 고정하는 것도 가능

3-4. CT 개수에 따라 미리 hash bucket을 지정하는 기능이 이미 Linux에는 반영되어 있음. 동적 할당이 추가로 필요한지는 의문 !!

4. 보조 해시 함수

4-1. 해시값을 메모리 효율성을 위해 전부 사용하지 하고 특정값(M)으로 나눈 나머지를 사용

4-2. M은 소수가 되는 것이 좋으나, 계산이 복잡해지는 측면이 있기 때문에 2^a로 나누는(1<<a - 1 값으로 &) 연산을 주로 활용

4-3. 이 때, 상위 비트 (a 이상)는 버려져 collision 가능성이 증가하므로 보조 해시 함수를 둠

4-4. JDK 8부터는 해시값의 상위 16비트를 XOR하는 보조함수 사용

4-5. 보조 함수가 단순해진 이유는 해시 함수 자체가 잘 분산되는 함수로 변경되었거니와, collision 발생이 빈번하면 트리 구조로 바꾸어 collision시 탐색 부담을 줄였기 때문

4-6. CT 해시에는 이미 보조 함수를 사용하고 있음

4-7. hash LB 알고리듬 등에서 IP 해시에 의한 collision이 발생할 가능성이 큰데 이를 활용하면 좋겠다!!

5. 스트링에 대한 해시 함수

5-1. 스트링에 대한 해시는 잘 하지 않음. (속도 문제)

5-2. 또는 해시에 참여하는 스트링의 길이를 대폭 줄임 (2바이트)

5-3. 요즘은 CPU 파워가 좋아졌기 때문에 전체 스트링에 대해 hash를 해도 무방

5-4. 대신 hash function은 대체로 h = 31 * h + str[i] 로 구현

5-5. 31을 승수로 쓰는 이유는 이 값이 소수이기도 하고, 31N = 32N - N 인데, 32 = 2^5 이므로 (N << 5) - N과 같이 계산하기 쉽고 빠르므로.

5-6. HTTP 프로토콜 헤더 분석시 이용하면 좋겠다.

이상 정리 끝.

원문 사이트 : http://helloworld.naver.com/helloworld/831311