[Dart] Map 구현체: HashMap, SplayTreeMap, LinkedHashMap

Flutter 개발을 하다가 key를 기준으로 정렬되는 map 자료형이 필요하여 공부를 찾아보다가 생각보다 여러 가지 구현체가 있다는 것을 알게 됐다. Dart 언어를 접한 지 벌써 3년이 다 되어가는데 이런 요구사항이 있었던 적이 한 번도 없었어서 이제야 알게 됐다는 것이 놀라웠다.

그래서 오늘은 세 가지 Dart Map 구현체 HashMap, SplayTreeMap, LinkedHashMap에 대해서 살펴보고 각 구현체를 언제 사용해야 하는지에 대해서 정리를 해보려고 한다.

Map 자료 구조

Map은 연관된 키를 사용하여 값을 검색하는 키/값 쌍의 컬렉션이다. 여러 프로그래밍 언어에서 기본적으로 제공하는 자료형으로 파이썬에서는 사전(dictionary)이라는 자료형으로 제공하고 있다.

Map.entries 속성을 통해서 Map안의 키/값 쌍을 반복할 수 있는데 이때 반복의 순서는 맵의 세부 구현에 따라서 달라지게 된다. 현재 Dart 3.2.5 버전의 Map 구현체는 HashMap, SplayTreeMap, LinkedHashMap 세 가지가 있다.

1. HashMap

HashMap은 Dart의 기본 Map 구현체로 해시 테이블을 활용하여 조회, 추가, 삭제가 빠르지만 요소의 순서를 유지하지 않는다는 특징이 있다.

HashMap이 적합한 상황

• 성능: 빠른 조회, 추가, 삭제가 중요할 때

• 순서가 없는 데이터: 요소들의 순서가 중요하지 않은 상황

예제 시나리오: 앱 설정 저장, 검색

import 'dart:collection';

void main() {
  final userPreferences = HashMap<String, dynamic>();

  // 사용자 선호도 설정
  userPreferences['theme'] = 'Dark';
  userPreferences['fontSize'] = 14;
  userPreferences['notificationsEnabled'] = true;

  // 특정 선호도 접근
  final theme = userPreferences['theme'];
  print('사용자가 선택한 테마: $theme');

  // 더 많은 선호도 추가
  userPreferences['language'] = 'English';
}

// Output:
// 사용자가 선택한 테마: Dart

2. SplayTreeMap

SplayTreeMap은 self-balancing binary search tree를 기반으로 하는 Map 구현체로 키를 기준으로 값을 정렬한다. 자주 사용하는 값은 트리의 루트에 가까운 위치로 이동되어 이후에 접근할 때 더 빠르게 접근할 수 있게 만든다는 특징이 있다.

SplayTreeMap이 적합한 상황

• 정렬: 키를 기준으로 요소들을 정렬된 상태로 유지해야 할 때 (순서가 중요한 데이터)

• 효율적인 접근: 데이터별로 접근 빈도가 크게 차이나는 상황

예시 시나리오: 리더보드

점수 순으로 정렬된 상태를 유지하면서 Top3와 같이 자주 접근하는 데이터가 있을 경우가 있을 때 SplayTreeMap이 유용하게 사용될 수 있다.

import 'dart:collection';

void main() {
  final scores = <String, int>{};
  final leaderboard = SplayTreeMap<int, Set<String>>();

  // 플레이어 점수 추가/업데이트하는 함수
  void updateScore(String playerId, int score) {
    leaderboard[scores[playerId]]?.remove(playerId);
    leaderboard.putIfAbsent(score, () => {}).add(playerId);
    scores[playerId] = score;
  }

  // 점수 추가/업데이트
  updateScore('player1', 100);
  updateScore('player2', 150);
  updateScore('player3', 100);

  // 리더보드를 내림차순으로 표시 (가장 높은 점수가 먼저)
  for (var score in leaderboard.keys.toList().reversed) {
    print('점수: $score, 플레이어들: ${leaderboard[score]}');
  }

  // 점수 추가/업데이트
  updateScore('player1', 120);
  updateScore('player2', 200);
  updateScore('player3', 150);

  // 리더보드를 내림차순으로 표시 (가장 높은 점수가 먼저)
  print("\n업데이트 후");
  for (var score in leaderboard.keys.toList().reversed) {
    if(leaderboard[score] != null && leaderboard[score]!.isNotEmpty) {
      print('점수: $score, 플레이어들: ${leaderboard[score]}');
    }
  }
}

// Output:
// 점수: 150, 플레이어들: {player2}
// 점수: 100, 플레이어들: {player1, player3}
// 
// 업데이트 후
// 점수: 200, 플레이어들: {player2}
// 점수: 150, 플레이어들: {player3}
// 점수: 120, 플레이어들: {player1}

3. LinkedHashMap

LinkedHashMap은 항목이 추가된 순서를 유지한다. 즉, 맵을 순회할 때 항목이 추가된 순서대로 반환된다. 항목의 삽입 순서가 중요할 때 특히 유용하다.

LinkedHashMap이 적합한 상황

• 순서 유지: 데이터의 순서가 중요한 애플리케이션

예시 시나리오: 쇼핑 카트

쇼핑카트에는 담은 순서대로 표시가 되며 쇼핑카트의 수량이 변경되더라도 그 순서는 변경되지 않는다. 쇼핑카트는 LinkedHashMap이 동작하는 방식과 유사하다.

import 'dart:collection';

void main() {
  var shoppingCart = LinkedHashMap<String, int>();

  // 상품을 쇼핑 카트에 추가
  shoppingCart['Apple'] = 1;
  shoppingCart['Banana'] = 2;
  shoppingCart['Orange'] = 2;

  // 카트 내용 확인
  print("쇼핑 카트:");
  shoppingCart.forEach((itemNumber, itemName) {
    print("$itemNumber: $itemName개");
  });

  // 수량 변경
  shoppingCart['Apple'] = 6;

  print("\n수량 변경 후 쇼핑 카트:");
  shoppingCart.forEach((itemNumber, itemName) {
    print("$itemNumber: $itemName개");
  });
}

// Output:
// 쇼핑 카트:
// Apple: 1개
// Banana: 2개
// Orange: 2개
// 
// 수량 변경 후 쇼핑 카트:
// Apple: 6개
// Banana: 2개
// Orange: 2개

결론 - 무엇을 사용해야 할까?

• 순서가 중요하지 않고 빠른 검색, 삽입, 삭제가 필요한 경우 HashMap

• 정렬과 자주 접근하는 요소에 대한 효율적인 접근이 필요할 때 SplayTreeMap

• 삽입 순서가 유지되어야 하는 경우 LinkedHashMap

추가 자료 및 참고 자료:

• Dart Collection - HashMap

• Dart Collection - SplayTreeMap

• Dart Collection - LinkedHashMap