[Java] 문제 풀이를 통해 배운 HashMap

0. 들어가며

반복문 안에 배열의 특정 값 탐색을 위해 새로운 반복문이 삽입 되는 구조에서 배열로 구현 하게 시간 복잡도가 n^2이 됩니다.
배열 순회를 통한 풀이를 제출하니 시간 초과가 나오더군요.
값의 탐색 시간을 줄이는 것이 관건 이었고, HashMap을 이용하여 직면한 문제를 해결 할 수 있었습니다.

1. 배열 순회

		 for(int i = 0; i< callings.length; i++){
         	called_players = callings[i];
            for(int j=0; j< players.length; j++){
            	if(players[j] == called_players){
                	called_idx = j;
                }
            }
         }       	

palyers 배열에서 called_players 의 값이 있는 인덱스를 찾을때
배열의 인덱스를 하나씩 증가 시켜 가며 해당 인덱스 위치에 저장된 값이 called_players인지 확인합니다. callings 의 배열에 있는 모든 값을 같은 방식으로 탐색 할 시 (최악의 경우 callings 배열의 크기) X (players 배열의 크기) 만큼 연산하게 됩니다.

        for(int i = 0; i< callings.length; i++){
            called_players = callings[i];
            called_idx = mappedByName.get(called_players);

2. Hash Map 을 이용한 탐색

mappedByName은 기존의 players 배열의 인덱스와 해당 인덱스의 값을 매핑한 HashMap 인스턴스 입니다.
예를 들어 players = {"Tom","Jerry"......"Been"} 라면
mappedByName={[Tom:0],[Jerry:1],....[Been:99]} 가 되는 것이죠.
참고로 mappedByName.get(Been)의 반환 값은 99 가 됩니다.

반복문을 통해서는 최악의 경우 배열의 끝(위의 예제로는 100번)까지 반복해야 하지만 HashMap을 이용하면 상수의 시간복잡도(O(1))로 동일 결과를 얻을 수 있습니다.

3. HashMap의 탐색 속도가 빠른 이유

players 배열을 HashMap으로 매핑하게 되는 과정을 간단하게 알아봅시다.
players의 100번째 인덱스인"Been"을 Key로 정하고
Value에 Been"의 인덱스인 99를 매핑 합니다.
HashMap은 Key 값에 여러 비트연산 등을 통하여 정수값을 얻습니다.
지금은 3을 얻었다고 가정합니다.

Value를 버킷(HashMap이 생성한 배열이라고 보면 될 듯 합니다.)의 3번째 인덱스에 저장하게 된다.
Been > 3 > 버킷의 3번째 인덱스 > Value인 99를 저장
위의 순서대로 연산이 이루어지기 때문에 탐색 속도가 빠르다는 것을 알 수 있습니다.

4. 마무리 및 다음 포스팅 예고(HashMap의 충돌)

이번 포스팅에서는 HashMap의 간단한 개념 설명과 HashMap을 통해 문제를 해결하는 과정을 살펴 보았습니다.
하지만 Key값은 무한하고,버킷의 크기는 정해져 있을 수 밖에 없는 구조적 한계 때문에 충돌을 피할 수 없죠. 다음 포스팅에서는 HashMap.class 파일을 살펴보며 HashMap의 보다 깊은 이해와 HashMap 충돌에 관하여 알아보도록 합시다.