ArrayList vs HashMap

알고리즘을 풀면서, 특정 값을 찾아 처리하려고 할 때 둘의 효율성 차이가 존재한다는 것을 알 수 있었다.

 

 

우선, 둘을 비교해보자.

 

ArrayList와 HashMap 모두 Java의 컬렉션 프레임워크의 클래스들을 사용하지만, 자료를 저장하고 처리하는 방법이 다르다.

 

ArrayList는 배열을 이용한 index 기반의 자료 구조인 반면에,

HashMap은 해싱을 통해 저장된 값들을 찾아오는 자료 구조이다.

해싱이란 산술적인 연산을 이용하여, 키가 있는 위치를 계산해서 찾아가는 검색 방식이다.

 

둘 다 저장된 객체들을 이용한다지만, 구현하고 사용하는 과정이 좀 다르다고 할 수 있다.

 

 

다음 표를 통해, 차이점을 알아보자.

 

ArrayList	HashMap
List 인터페이스를 구현	Map 인터페이스를 구현
요소의 값을 저장하고 각 요소에 맞는 index를 유지	key와 value를 쌍으로 저장하고, 각 value는 key가 무조건 존재
index를 통해 해당 요소를 가져옴	일치하는 key를 통해 value 값을 가져옴
중복된 요소를 허용	중복된 key는 불허용
항상 O(1)의 효율을 가짐	좋은 케이스에는 O(1), 최악의 케이스에는 O(n)까지 시간복잡도가 증가할 수 있음
여러 요소에 null을 넣을 수 있음	오직 하나의 null key와 여러 null values를 가질 수 있음

 

둘의 차이점은 이러하고, 그렇다면 알고리즘 문제를 풀면서 효율성 측면에서 차이가 난다는 건 무엇일까?

 

 

for문을 통해서, 특정 데이터 값을 찾아 없애는 로직을 구현해야 한다고 치자.

 

그렇다면, 일단 for문으로 인해 둘 다 시간복잡도는 O(n)일 것이다.

 

그리고 ArrayList의 경우는 remove 메서드를 사용하게 될텐데, 이 또한 시간 복잡도는 O(n)으로 총 O(n^2)이라는 시간복잡도가 된다.

 

반면에, HashMap의 remove 메서드는 시간복잡도가 O(1)으로, 총 시간 복잡도는 O(n)이 될 것이다.

 

 

상황에 따라서, ArrayList로 구현하는 것이 대개 좋은 효율을 가질테지만, 위와 같이 특정 값을 찾아 처리해야하는 경우라면, HashMap이 더 좋을 것 같다는 개인적인 의견이다.

 

 

 

 

아주 간단하고 기본적일 수 있는 내용들이지만, 개인적인 정리가 필요할 것 같아 작성하였습니다.

틀린 부분이나 내용이 있다면, 댓글 남겨주시면 감사하겠습니다 :)

 

 

Ref)

https://www.javatpoint.com/arraylist-vs-hashmap-in-java