[Data_Structure] Map

먹보·2023년 3월 28일

Map data structure

MUK_BO's Data_Structure & Algorithm

목록 보기

10/15

✍️ Map이란..

"Map"은 키와 값이 쌍으로 이루어진 데이터를 저장하고 관리하는 자료구조입니다.

📝 Map 자료 구조의 특징

키(key)와 값(value)으로 이루어진 쌍(pair) 데이터를 저장하는 자료구조입니다.
중복되지 않는 유일한 키(key)를 사용하여 값(value)에 접근할 수 있습니다.
순서를 보장하지 않으며, 삽입 순서와 관계없이 접근 시간이 일정합니다.
해시 테이블(hash table)을 이용하여 구현됩니다.
대용량 데이터를 빠르게 탐색할 수 있으며, 검색 연산의 시간 복잡도가 O(1)입니다.
키와 값이 모두 객체(object)일 수 있으며, 다양한 자료형을 저장할 수 있습니다.

📝 Map 구현 방식 및 작동 원리

Map은 해시 테이블(hash table)을 이용하여 구현됩니다. 해시 테이블은 각 키(key)에 대한 해시 함수(hash function)를 적용하여 고유한 버킷(bucket)에 저장하는 방식으로 동작합니다. 이를 통해 빠르게 값을 찾을 수 있습니다.
Map에서 값을 추가하거나 삭제할 때는 해당 값을 가지고 있는 버킷(bucket)을 찾아서 연산을 수행합니다. 이 때, 버킷 내부에는 연결 리스트(linked list) 형태로 값(value)을 저장하게 되며, 동일한 버킷에 여러 개의 값이 저장될 수 있습니다.
값에 접근할 때는 해당 키(key)를 해시 함수를 통해 버킷(bucket)의 인덱스로 변환한 후, 버킷 내부의 연결 리스트(linked list)를 순회하며 값을 찾아내는 방식으로 동작합니다. 이 때, 해시 함수의 품질이 중요한 역할을 수행하며, 최악의 경우 모든 값이 하나의 버킷에 모이는 충돌(collision)이 발생할 수 있습니다.

✍️ Map의 장단점 및 예시

📝 장점

대용량 데이터를 빠르게 탐색할 수 있습니다.
검색 연산의 시간 복잡도가 O(1)로 매우 빠릅니다.
키와 값이 모두 객체(object)일 수 있으며, 다양한 자료형을 저장할 수 있습니다.
키의 중복을 허용하지 않으며, 유일한 값을 저장할 수 있습니다.

📝 단점

순서를 보장하지 않습니다. 삽입 순서와 상관없이 값에 접근할 수 있습니다.
해시 함수의 품질에 따라 충돌(collision)이 발생할 수 있습니다. 이 경우 검색 성능이 저하될 수 있습니다.
자료구조의 크기가 커질수록 해시 테이블(hash table)의 크기를 늘려야 하므로 메모리 사용량이 높아질 수 있습니다.
값에 대한 순회(traversal)가 어렵습니다. 값을 가져오기 위해서는 키(key)를 알아야 하며, 키(key)를 모를 경우 모든 요소를 순회해야 합니다.

📝 예시

사용자 정보 관리 - 사용자 ID를 키(key)로, 사용자 정보 객체를 값(value)으로 저장하여, 검색 연산에서 O(1) 시간 복잡도를 보장합니다.
상품 검색 기능 - 상품명을 키(key)로, 상품 정보 객체를 값(value)으로 저장하여, 검색 연산에서 빠른 속도를 보장합니다.
실시간 데이터 갱신 - 데이터를 매초마다 갱신하여, 최신 데이터를 Map에 저장합니다. 검색 시 최신 데이터를 제공할 수 있습니다.
캐시(Cache) 구현 - Map을 사용하여 최근 검색한 데이터를 캐시에 저장하여, 검색 속도를 높일 수 있습니다. 캐시가 가득차면 가장 오래된 데이터를 삭제하여 공간을 확보할 수 있습니다.

✍️ JavaScript 내에서의 Map

자바스크립트에서는 Map을 쉽게 이용 가능하며 기능을 원활하게 도와주는 메서드들도 다양하다.

const myMap = new Map();

myMap.set('apple', 1); //set('key','value')
myMap.set('banana', 2);
myMap.set('cherry', 3);

const value = myMap.get('banana');
console.log(value); // Output: 2

const hasKey = myMap.has('banana');
console.log(hasKey); // Output: true

myMap.delete('banana');

const size = myMap.size;
console.log(size); // Output: 2 (after deleting 'banana')

for (const [key, value] of myMap) {
  console.log(`${key} = ${value}`);
}