[자료구조] HashMap vs LinkedHashMap

역시나 코딩테스트 문제를 풀다 HashMap이랑 LinkedHashMap이 약간 헷갈려 정리할려고 글을 쓴다.

HashMap의 경우 단점이 하나 있다. 그 단점은 put을 통해 데이터나 객체를 넣을 때 key의 순서가 지켜지지 않는다는 것이다. 코드상으로 순차적으로 key, value를 넣어도, 실제 HashMap에서는 해당 순서가 지켜지지 않는다.

HashMap<String, String> = new HashMap<>();

map.put("강아지", "참새");
map.put("고양이", "토끼");
map.put("호랑이", "사자");

이렇게 key와 value를 해시맵에 넣는다고 가정하면, 다음과 같이 저장된다는 것이다

key	value
고양이	토끼
호랑이	사자
강아지	참새

그래서 입력된 key의 순서가 보장되어야 한다면 LinkedHashMap 을 사용하면 된다.

LinkedHashMap 은 put을 통해 입력된 순서대로 key가 보장되므로 해당 문제를 해결할 수 있다. 사용법은 다음과 같다.

LinkedHashMap<String, String> = new LinkedHashMap<>();

map.put("강아지", "참새");
map.put("고양이", "토끼");
map.put("호랑이", "사자");

key	value
강아지	참새
고양이	토끼
호랑이	사자

그러면 HashMap이랑 비교했을 때 LinkedHashMap이 어떤 특성을 가지고 있는지 알아보자.

공통점

• 데이터를 key-value 쌍으로 저장한다.
• 비동기로 처리된다.

Key

• 중복을 허용하지 않는다.
• 하나의 null값을 저장할 수 있다.

Value

• 중복을 허용한다.
• 여러 개의 null값을 저장할 수 있다.

차이점

HashMap

• 데이터의 삽입 순서를 보장하지 않는다.
• AbstractMap 클래스를 상속하고, Map 인터페이스를 구현한다.

LinkedHashMap

• 데이터의 삽입 순서를 보장한다.
• HashMap 클래스를 상속하고, Map 인터페이스를 구현한다.

성능

Create

• HashMap < LinkedHashMap (오래 걸림)

Iterate

• (오래 걸림) HashMap > LinkedHashMap

Access

• (오래 걸림) HashMap > LinkedHashMap

결론

• HashMap보다 LinkedHashMap의 성능이 약간 더 우세하지만, 전체적인 성능에는 큰 차이가 없다.
• HashMap은 순서를 보장하지 않아도 될 때, LinkedHashMap은 순서를 보장해야 될 떄 사용한다.

참고

https://fruitdev.tistory.com/141
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
https://da-nyee.github.io/posts/java-hashmap-vs-likedhashmap/