자료구조 최적화: 해시맵과 배열

 

알고리즘 해답 중에 해시맵을 배열로 속도가 빨라지는 경우가 있어서, 그 부분을 기록으로 남길까 합니다.

 

왜 배열로 바꿨을 때 빨라질까?

---

배열이나 해시맵이나 원소(Element)에 접근할 때의 시간 복잡도는 O(1)로 같습니다. 하지만 해시맵은 내부적으로 해시 함수를 거쳐야 하는 등 여러 오버헤드가 발생하기 때문에, 실제 연산 속도는 배열이 훨씬 빠릅니다.

두 구조의 내부 접근 순서를 비교해 보면 다음과 같습니다.

• 배열: Arr[Index] => 인덱스를 통한 메모리 주소 접근 => 원소 반환
• 해시맵: Map.get(key) => 해시 함수(Hash Function) 연산 => 해시 값을 버킷 인덱스로 변환 => 해당 버킷 접근 => Collision 있을 시 연결 리스트나 트리 탐색 및 Key 동등성 비교 => 원소 반환

위 순서만 봐도 해시맵이 훨씬 복잡하기는 하네요.

 

배열로 대체할 수 있는 조건

---

해시맵을 배열로 대체할 수 있는 조건은 너무 다양할것 같지만, 경험적으로 느낀 대표적인 유형이 몇 가지 있는 것 같다.

 

주어진 인덱스의 범위가 작을 때

인덱스의 범위가 long 급으로 크다면, Memory에 부담을 주게 되서 Memory Limit Exceeded라는 결과를 받게 되지만, 10^5 정도의 크기는 부담 없이 배열로 교체가 가능합니다.

 

키를 배열의 인덱스로 매핑할 수 있을 때

해시맵이 가지고 있는 Key가 인덱스로 단순하게 치환을 할 수 있다면 배열을 안 쓸 이유가 없는 것 같다.

TreeNode[] nodeArr = new TreeNode[100001];
Map<Integer, TreeNode> nodeMap = new HashMap<>();

 

위 코드처럼 단순하게 정수와 TreeNode를 사용하는 해시맵이라면 nodeArr라는 배열로 바꿈으로서 속도를 더 향상 시킬 수 있게된다.

 

 

추천 문제

---

Create Binary Tree From Descriptions

Create Binary Tree From Descriptions - LeetCode