[Java] LinkedHashMap — 순서를 유지하는 해시맵
LinkedHashMap은 Java의 HashMap을 확장하는 클래스입니다. J2SE 1.4 버전부터 추가된 유용한 자료구조이지요. LinkedHashMap의 가장 큰 특징은 자료가 입력된 순서를 기억한다는 것입니다. 그렇다면, Java의 ArrayList, LinkedList와 같은 자료구조는 순서를 유지하는데 왜 LinkedHashMap이라는 특별히 HashMap의 순서를 유지하기 위한 자료구조가 소개되는 것일까요? 이유를 알기 위해선 왜 HashMap이 입력된 데이터의 순서를 유지하지 않는지 먼저 살펴봐야 겠죠.
HashMap이 데이터의 순서를 유지하지 않는 이유
HashMap이 순서를 보장하지 않는 이유를 알기위해선 HashMap이 등장하게 된 목적부터 알아야합니다. HashMap은 연관 배열을 저장하기 위한 자료구조입니다. 여기선 연관 배열(Associative Array)은 키와 값의 쌍을 저장하기 위한 구조입니다. 키를 통해 쉽게 값을 저장하거나 얻기 위한 목적이죠.
연관 배열은 맵(Map) 혹은 딕셔너리(Dictionary)라는 이름으로도 불립니다. 연관 배열의 자료를 효율적으로 저장하기 위해 키를 해시 펑션(Hash Function)을 통해 변환(매핑)합니다. 이렇게 나온 해시 값을 통해서 우리는 자료를 상수 시간, O(1)에 검색할 수 있는 것이죠. (해시 펑션에 대해 자세히 알아보려면 Java HashMap은 어떻게 동작하는가? 외부 링크를 확인해보세요. 해시 펑션 이외에도 Java HashMap의 동작 방식에 대한 자세한 설명이 담겨있습니다).
Java 8 부터는 HashMap의 동작 방식이 조금은 다르지만 기본적으로 해시 펑션을 통해 나온 해시 값을 가지는 버킷에 데이터를 저장합니다.
해시 펑션에 따라 해시 값(index)은 달라 질 수 있지만 그림 1의 ‘itemType’, ‘subtype’, ‘make’ 등의 키의 해시 값이 모두 다르다고 가정하면 한 버킷에 각기 다른 해시 값으로 데이터가 들어가게 되죠. 하지만, 해시 값은 순서를 보장하지 않기 때문에 정확히 ‘itemType’이 index 0 에, ‘subtype’이 index 1에 들어가지 않습니다 (그렇게 되면 해싱의 의미가 없겠죠). 우리는 HashMap의 모든 데이터를 꺼내기 위해 다음과 같은 코드를 사용할 수 있습니다.
HashMap.keySet() 을 통하여 Set을 꺼내게 되는데, 이 반환되는 Set의 동작에서 HashMap의 데이터 입력의 순서가 정확히 보장되지 않습니다. 이 순서는 Java 버전에 따라 달라질 수 있고, 환경에 따라 달라질 수도 있죠. Java API 문서에서 이 순서는 일정하지 않다고 명시하고 있습니다. 그럴 수 밖에 없는게, HashMap은 해시 펑션을 통해 순서를 보장하지 못하고, 따로 순서를 가지는 추가적인 자료구조를 가지고 있지 않기 때문이죠.
LinkedHashMap을 통한 순서 유지
우리는 HashMap이 순서대로 자료를 유지하기 위한 자료구조가 아님을 알았습니다. 하지만 다음과 같은 요구사항이 존재한다면 어떨까요?
- 키-값 쌍이 필요하다 (사진을 찍은 시간과 같은).
- 전체 크기는 알지 못한다 (실시간 동영상을 찍으므로 전체 프레임 크기가 변할 가능성이 있다).
- 순서를 알아야 한다 (사진을 찍은 순서대로 동영상으로 변환해야 한다).
이러한 필요가 있을 때, 간편하게 쓸 수 있는 자료구조가 바로 LinkedHashMap입니다. Hash를 통해 자료를 보관할 필요가 있지만, 원할 때 순서대로 가져와야 하는 경우이죠.
LinkedHashMap은 HashMap을 확장합니다. HashMap의 모든 기능을 사용하되, Doubly-Linked List를 내부에 유지함으로써 입력된 자료의 순서를 보관하죠. 물론 자료의 크기가 커지면 메모리 사용량이 늘어나겠지만, 순서를 간편하게 유지하기 위해서 이만한게 없지요.
다음 Android Developer의 API 문서를 참조하면 좋습니다. 더 자세한 설명을 볼 수 있을 것입니다.
HashMap : https://developer.android.com/reference/java/util/HashMap.html
LinkedHashMap : https://developer.android.com/reference/java/util/LinkedHashMap.html
