java의 HashMap은 키-값(key-value) 쌍을 저장하기 위해 해시 테이블(Hash Table)을 사용하며 일반적으로 매우 효율적인 기능입니다. 특히 값을 찾을 때 빠른 속도로 찾을 수 있다는 장점이 있습니다(시간복잡도 O(1)) 그러나 해시 충돌(Hash Collision)이 발생하면 성능에 영향을 미칠 수 있습니다. 아래에서 HashMap의 시간 복잡도, 충돌문제, 그리고 이를 해결하는 방법을 자세하게 설명하겠습니다.
1. HashMap이 빠른 이유
HashMap은 데이터를 저장 할 때 해시함수를 이용해 키를 숫자로 바꿉니다. 이 숫자를 버킷이라는 배열의 위치로 사용해 데이터를 저장하거나 찾는데 이용합니다.
예시를 들어보겠습니다. 만약 키값 Runs가 해시함수를 거쳐서 버킷배열에 46이라는 위치에 데이터가 저장됩니다.
키 Runs로 데이터를 검색할 때, 다시 해시 함수를 적용하여 해시 코드 46을 얻습니다. 버킷 배열의 인덱스 46에 접근하여 데이터를 빠르게 찾습니다.
2. HashMap의 시간 복잡도
평균적인 경우: O(1) 키에 대해 hashCode()를 호출하여 해시값을 계산하고 해당값을 배열 인덱스(버킷)으로 변환합니다. 이후 적절한 버킷에서 값을 검색, 추가 또는 삭제합니다. 충돌이 없으면 대부분의 작업은 단일 버킷 접근으로 완료 되므로 상수 시간 복잡도를 가집니다.
최악의 경우 O(n) 모든 키가 동일한 해시값을 가지면 충돌로 인해 하나의 버킷에 모든 요소가 저장됩니다. 이경우 검색,추가,삭제 작업은 해당 버킷의 모든 요소를 순차적으로 탐색해야 하므로 O(n)의 시간 복잡도가 발생하게 됩니다.
3. HashMap에서 생기는 문제: 해시 충돌
HashMap이 항상 완벽하게 작동되는것은 아닙니다. 같은 버킷(위치)에 여러 데이터가 들어가는 경우가 있습니다. 이를 해시충돌이라고 합니다.
예를 들어 apple과 orage라는 키값이 있다 했을 때 둘다 해시함수를 통해 해시값 12345로 계산이 될 수 도 있습니다.
이때 서로 다른 값이 같은 버킷에 저장되면서 값을 찾을 때 해시충돌이 일어 날 수 있습니다.
해시 충돌은 위에 예시처럼 두개 이상의 키가 동일한 해시값을 가질 때 발생합니다. 이는 다음과 같은 이유로 일어 날 수 있습니다.
해시함수가 불안전해 고유한 해시값을 생성하지 못하고 많은 키가 동일한 해시값으로 매핑이 됩니다.
키 값이 특정 범위에 치우쳐 있다면 몇몇 버킷에 데이터가 몰리게 됩니다.
해시 테이블의 크기가 작거나 초기 용량 설정이 부적절한 경우 충돌이 증가합니다.
충돌이 많아지면 하나의 버킷에 많은 요소들이 저장되어 있기 때문에 이를 검색하는데 시간이 더 오래 걸립니다.
4. java HashMap에서 충돌 처리 방식
hashmap이 충돌이 되었을 때 java의 hashmap은 chaining(체이닝)과 treeify(트리화) 전략을 사용합니다.
체이닝(Chaining) 동일한 해시값을 가진 요소들은 LinkedList로 연결됩니다. 각 버킷은 단일 값 대신에 LinkedList를 저장하고 충돌이 발생했을 때 해당 버킷의 LinkedList에 새 요소를 추가합니다. 검색 시 해당 버킷의 LinkedList를 순차적으로 탐색하여 키를 비교합니다.
위 그림처럼 같은 버킷에 저장되어 있는 값들이 연결 리스트를 통해 한줄로 연결이 되므로 충돌이 일어났을 때 연결된 값들을 순차적으로 탐색하여 값을 찾게 됩니다.
트리화(Treeify) 해시 충돌이 특정 임계치(기본적으로 8개)를 초과하면 LinkedList가 Red-Black Tree로 변환 됩니다.
Red-Black Tree는 이진 탐색 트리로, 최악의 경우 시간 복잡도가 O(log n)입니다.
기존 HashMap의 최악의 경우 시간복잡도가 O(n)인걸 고려해보면 트리화를 이용했을 때 해시 충돌시 시간복잡도가 줄어 들어 데이터에 더 빨리 접근 할 수 있는 걸 알 수 있습니다.
5. 해결방법
HashMap의 충돌 문제를 최소화하려면 다음과 같은 방법들을 고려할 수 있습니다.
해시 함수 개선 사용자 정의 클래스 에서 hashCode()와 equals()를 올바르게 구현해야 합니다. 해시 함수를 통해 충돌을 최소화 해야 하며 다양한 키에 대해서 해시값이 고르게 분포되도록 해야 합니다.
초기 용량 설정 HashMap의 초기 용량을 충분히 크게 설정하여 충돌 가능성을 줄일 수 있습니다. 만약 키의 개수가 많다면 hashMap생성 시 초기 용량을 키 개수보다 약간 큰 값으로 설정할 수 있습니다.
부하율 조정 기본 부하율은 0.75로 설정되어 있습니다. 만약 부하율이 0.75이면 버킷배열이 75%가 찰 때 크기를 두배로 늘리게 됩니다. hashMap의 충돌이 잦다면 부하율을 낮게 설정하여 충돌을 줄일 수 있습니다.
버킷 크기 조정 해시 테이블 크기는 항상 2의 제곱수로 설정됩니다. 테이블의 크리를 조정하여 충돌을 완화 할 수 있습니다.
Java의 HashMap은 기본적으로 효율적인 자료구조지만, 해시 충돌이 발생하면 성능 저하가 생길 수 있습니다. 이를 해결하기 위해 HashMap은 체이닝과 트리화를 사용하며, 사용자도 적절한 해시 함수 구현과 초기 설정을 통해 충돌 가능성을 줄일 수 있습니다.
