서론
해쉬맵에 있는 값을 검색하는 속도는 무조건 배열에서 원소를 찾는 속도보다 빠르다. 근데 왜 빠를까? 그저 어디선가 본 책에 그렇게 적혀있어서 당연하게 생각해왔지만, 위 질문을 받았을 때 깔끔하게 대답할 수 없었다.
머릿속으로 먼저 든 생각은 해쉬맵은 key 값이 있어서 빠르다. 해당 키를 찾으면 그 키와 쌍을 이루는 value가 검색하려는 값이니 복잡도는 자연스럽게 O(1)이 될 것이다.
배열은 값을 찾기 위해 인덱스 0부터 N까지 쭉 탐색할 것이고 배열의 검색 복잡도는 O(N)일 것이다. (N 배열의 크기)
그렇다면 해쉬맵에서 key는 또 어떻게 찾을까? key를 찾기 위해 순회를 할까? 아니면 key에 index를 입혀서 검색할까?당연하지 해쉬맵에 그렇다면 key를 무한정으로 집어넣을 수 있는걸까?
처음 질문도 잘 대답할 수 없었고, 머릿속에서 소용돌이치는 내 자신의 질문 아무것도 대답할 수 없었다. 이게 개발자인가? 빨리 해쉬맵에 대해 간단히 알아보기로 했다.
해쉬맵은
Bucket이라는 구조를 가지고 키를 찾는다. Bucket에는 key로 생성한 Object와 해쉬코드를 쌍으로 들어있다. 해쉬코드에는 순서가 있고 그 순서를 기반으로 값을 검색하기 때문에 키를 빠르게 찾을 수 있다.
| 해쉬코드 | 키 |
|---|---|
| 000 | 이지금 |
| 001 | 이지은 |
| 002 | 이지동 |
그리고 Entry라는 구조를 가지고 값을 찾게 된다. Entry는
| 키 | 값 |
|---|---|
| 이지금 | 가수 |
| 이지은 | 래퍼 |
| 이지동 | 기타리스트 |
위의 형태로 검색을 하므로 배열보다 빠르게 값을 찾을 수 있다.
해쉬맵은 그럼 무적인가
처음 질문을 받았을 때 머릿속에서 해쉬맵의 단점을 찾으려고 노력했던것 같고 그 단점이 배열의 장점과 상쇄되면 어느순간 배열이 유리한 부분이 있겠지! 라고 생각을 했다. 결론은 검색에 있어서는 없었고 다른 부분에서 단점을 찾을 수 있었다.
Bucket에 해쉬코드를 넣기 때문에 이 해쉬코드가 단점을 만들어 낸다.
먼저 Java를 기준으로 설명을 하자면 Key에 해쉬코드를 입힐 때 내부적으로 .hashCode() 메소드를 사용하게 된다. Java에서 이 hashCode는 int를 반환한다.
여기서 이 int로 인해 해쉬맵의 한계가 발생한다. 해쉬코드는 int의 범위인 2^32를 넘을 수 없다. 결국 같은 해쉬코드를 갖는 해쉬코드, 키 쌍이 Bucket에 들어가고 중복이 발생한다.
이런 문제를 해결 하는 방법은 2가지가 있는데, 하나는 Open Addressing이라는 방법이 있고, Seperate Chaining이라는 방법이 있다.
Java에서는 후자를 택했는데, 중복되는 Bucket에서는 연결 리스트를 통해 다음 값을 같은 해쉬코드의 다음 값으로 매핑을 한다.
이외에도
키, 값을 모두 저장해야하며 추가로 Bucket까지 생성해야하니 공간복잡도가 커지는 단점이 있다. 해쉬코드를 생성하는 과정 자체도 문제가 있을 수 있고 찾는 값이 배열의 첫 원소라면 상황에 따라 배열의 검색속도가 더 빠른 경우도 있을 것이다.
또 검색하려는 값을 가진 데이터가 순서를 가지고 있는 데이터라면 오히려 해쉬맵이 어울리지 않을 수도 있다.데이터를 삽입할 때 가장 마지막 값이면 배열의 마지막에 추가만 하면 되지만 해쉬맵의 경우는 해쉬코드를 만들고 적절한 곳에 배치하며 충돌 전략에 의한 삽입도 계산이 될 것으로 보이기 때문이다.
해쉬코드를 생성하는 전략도 중요하며 Seperate Chaning 방식으로 한 해쉬코드에 여러 키가 연결 리스트로 연결되어 있다면 이를 조회하는 시간도 생각보다 오래 걸릴 수가 있다.
하지만 실제로 개발을 하면서 이정도까지 신경을 쓸 필요는 없는 것 같다. Java 기준으로 Java를 개발하는 엔지니어들이 버전업을 하면서 꾸준히 Java의 성능을 신경 써준다.
예를 들면 한 해쉬코드에 붙은 키들이 많아지면 자동으로 내부 검색 방식을 스위칭하고, 해쉬맵에서 메모리 할당이 잘못되지 않도록 초기용량 설정 및 용량 증대의 타이밍 등을 적절히 계산해서 실행해준다.
