[CS] 자료 구조의 분류 - 비선형 자료 구조 #3 (맵, 셋, 해시 테이블)

Janet·2023년 9월 22일

CS 자료 구조

CS

목록 보기

17/17

비선형 자료 구조 (Non-Linear Data Structures)

비선형 자료 구조: 그래프, 트리, 해시 테이블, 힙, 맵, 셋, 우선순위 큐 등.

▼ 비선형 자료 구조 - 그래프와 트리에 대한 내용
[CS] 자료 구조의 분류 - 비선형 자료 구조 #1 (그래프, 트리)

▼ 비선형 자료 구조 - 힙, 우선순위 큐에 대한 내용
[CS] 자료 구조의 분류 - 비선형 자료 구조 #2 (힙, 우선순위 큐)

1. 맵 (Map)

맵은 특정 순서에 따라 키(key)와 매핑된 값(value)의 조합으로 형성된 자료 구조, 즉 Key와 Value를 쌍으로 데이터를 저장하는 자료 구조이다.
'key' : 1과 같이 string : int 형태로 값을 할당해야 할 때, 해시 테이블(Hash Table)을 구현할 때 등 사용한다.
레드 블랙 트리(Red Black Tree) 자료 구조를 기반으로 형성된다.
Map은 Key를 사용하여 데이터를 검색, 추가, 삭제, 수정할 수 있으며, 각 Key는 고유해야 한다.
일반적으로 Map은 동적 크기를 갖는다. 데이터가 추가되거나 삭제될 때 자동으로 크기를 조절 및 정렬한다.
Map은 데이터를 효율적으로 저장하고 검색하기 위해 해시 함수(hash function)를 사용한다.
JavaScript의 Map은 ECMAScript 6 (ES6) 스펙부터 공식적으로 추가되었다.

1-1. 맵 - 프로그래밍 언어별 구분

해시 맵 (Hash Map 또는 Hash Table)
- 가장 일반적으로 "Map"이라고 불리는 자료 구조는 해시 맵 또는 해시 테이블이다. 이 자료 구조는 키-값(key-value) 쌍을 저장하고 검색하는 데 사용된다. 키를 해시 함수를 통해 해싱하고, 그 결과를 배열의 인덱스로 사용하여 값을 저장하거나 검색한다. JavaScript에서는 Map 객체가 이러한 해시 맵을 구현하는 데 사용된다. 삽입, 삭제, 검색 연산의 평균 시간 복잡도가 O(1)에 가깝다.
- Map에서 key로 사용 가능한 데이터 타입: 문자열, 숫자, 객체, 함수 등 다양한 데이터 타입을 키로 사용 가능하다. (cf. 자바스크립트에서 Object의 Key는 문자열과 Symbol(ES6부터 지원)만 사용할 수 있다.)
C++ STL의 Map
- C++ 언어에서 "Map"은 키-값 쌍을 저장하는 자료 구조로, 레드-블랙 트리(Red-Black Tree) 기반의 자료 구조이다. 이는 키 값이 정렬되어 있으며, 검색, 삽입 및 삭제 연산의 시간 복잡도가 O(log N)이다. C++ 표준 라이브러리(STL)에서 std::map으로 구현되어 있다.
Java의 Map 인터페이스
- Java에서 "Map"은 키-값 쌍을 저장하고 검색하는 인터페이스를 나타낸다. Java에서는 HashMap, TreeMap, LinkedHashMap 등과 같은 구체적인 구현체를 제공한다. HashMap은 해시 맵, TreeMap은 레드-블랙 트리를 기반으로 한 맵, LinkedHashMap은 링크드 리스트를 사용하여 순서를 유지하는 맵이다.
Python의 딕셔너리(Dictionary)
- Python에서 "Map"은 딕셔너리(dictionary)로 구현되며, 키와 값의 쌍을 저장하고 검색하는 데 사용된다. 딕셔너리는 중괄호 {}를 사용하여 정의하며, 키와 값을 콜론(:)으로 구분한다.

1-2. 맵의 활용

Map은 데이터를 저장하고 검색하는 데 빠르고 효율적이다. 예를 들어, 프로그래밍에서는 변수의 이름과 값을 연결하는 데 Map을 사용하거나, 데이터베이스 캐싱, 웹 애플리케이션에서 사용자 세션 관리, 빅데이터 처리, 그래프 알고리즘 등 다양한 분야에서 활용된다.
여러 프로그래밍 언어와 라이브러리에서 Map을 제공하며, 각각의 언어나 라이브러리에서 구현 및 활용 방법이 다를 수 있다.

1-3. 기본 Method (JavaScript 기준)

📌 삽입 (Insertion)

set(key, value): 새로운 키-값 쌍을 Map에 추가한다. 만약 이미 동일한 키가 존재하면 해당 키의 값을 갱신한다.

const myMap = new Map();
myMap.set('name', 'John');
myMap.set('age', 30);

📌 검색 (Lookup)

get(key): 특정 키에 연결된 값을 검색한다.

const name = myMap.get('name'); // 'John'

📌 삭제 (Deletion)

delete(key): 특정 키-값 쌍을 삭제한다.

myMap.delete('age'); // 삭제

📌 크기 (Size)

size: Map에 저장된 키-값 쌍의 개수를 반환한다.

const size = myMap.size; // 1 (age 키가 삭제되었으므로 1개의 키-값 쌍만 남음)

📌 존재 여부 확인 (Existence Check)

has(key): 특정 키가 Map 내에 존재하는지 확인한다.

const hasName = myMap.has('name'); // true
const hasAge = myMap.has('age');   // false

📌 키 목록 및 값 목록 검색 (Key and Value Retrieval)

keys(): Map 내의 모든 키의 목록을 반환한다.
values(): Map 내의 모든 값을 반환한다.
entries(): Map 내의 모든 키-값 쌍을 [key, value] 형태의 배열로 반환한다.

const keys = Array.from(myMap.keys());     // ['name']
const values = Array.from(myMap.values()); // ['John']
const entries = Array.from(myMap.entries()); // [['name', 'John']]

📌 모든 요소 제거 (Clear)

clear(): Map 내의 모든 키-값 쌍을 제거한다.

myMap.clear(); // 모든 키-값 쌍 제거

📌 반복 (Iteration)

for...of와 forEach 메서드를 활용하여 Set 순회

const myMap = new Map();
myMap.set('name', 'John');
myMap.set('age', 30);
myMap.set('city', 'New York');

// for...of 반복문을 사용하여 Map 순회
for (const [key, value] of myMap) {
  console.log(`${key}: ${value}`);
}

// forEach 메서드를 사용하여 Map 순회
myMap.forEach((value, key) => {
  console.log(`${key}: ${value}`);
});

2. 셋 (Set)

셋은 중복 요소가 없이 유일한 값을 저장하는 자료 구조이다.
Map과 마찬가지로 JavaScript의 Set은 ECMAScript 6 (ES6) 스펙부터 공식적으로 추가되었다.
Set은 순서를 보장하지 않으므로 요소가 추가된 순서대로 나열되지 않는다. Set은 중복 요소를 허용하지 않으므로 동일한 값을 여러 번 추가하더라도 하나의 값만 유지된다. 따라서 중복 요소를 효과적으로 관리할 때 사용된다.
셋에 추가된 데이터는 내부적으로 항상 객체로 저장된다. 셋은 원시 데이터 유형과 객체를 모두 저장할 수 있는 자료 구조이다. 셋은 각 요소를 구분하기 위해 데이터를 내부적으로 객체로 변환한다. 그러므로 원시 데이터 값이 Set에 저장되면 내부적으로 객체 형태로 변환된다.

2-1. 기본 Method (JavaScript 기준)

📌 삽입 (Insertion)

add(value): Set에 새로운 값을 추가합니다. 이미 Set에 존재하는 값을 추가하더라도 중복 값은 저장되지 않습니다.

const mySet = new Set();
mySet.add(1);
mySet.add(2);
mySet.add(3);

console.log(mySet); // Set { 1, 2, 3 }

📌 삭제 (Deletion)

delete(value): Set에서 지정된 값을 삭제합니다. 삭제가 성공하면 true를 반환하고, 삭제할 요소가 없으면 false를 반환합니다.

const mySet = new Set([1, 2, 3]);
mySet.delete(2); // 삭제 성공, true 반환
mySet.delete(4); // 삭제 실패 (요소가 없음), false 반환

console.log(mySet); // Set { 1, 3 }

📌 크기 (Size)

size 또는 length 프로퍼티: Set의 요소 개수를 반환합니다.

const mySet = new Set([1, 2, 3]);
console.log(mySet.size); // 3

📌 존재 여부 확인 (Existence Check)

has(value): Set에 지정된 값을 가지고 있는지 확인합니다. 존재하면 true를, 존재하지 않으면 false를 반환합니다.

const mySet = new Set([1, 2, 3]);
console.log(mySet.has(2)); // true
console.log(mySet.has(4)); // false

📌 모든 요소 제거 (Clear)

clear(): Set의 모든 요소를 삭제하여 빈 Set으로 만듭니다.

const mySet = new Set([1, 2, 3]);
mySet.clear();

console.log(mySet); // Set {}

📌 반복 (Iteration)

for...of와 forEach를 활용하여 Map 순회

// for...of 반복문을 사용하여 Map 순회
const mySet1 = new Set(['apple', 'banana', 'cherry']);

for (const item of mySet1) {
  console.log(item);
}
// 출력:
// 'apple'
// 'banana'
// 'cherry'

// forEach 메서드를 사용하여 Map 순회
const mySet2 = new Set([1, 2, 3]);

mySet2.forEach((value) => {
  console.log(value);
});
// 출력:
// 1
// 2
// 3

2-2. 셋(Set)과 배열(Array)의 차이

Set과 배열(Array)은 모두 값(데이터)의 컬렉션을 저장하는 자료 구조이지만, 몇 가지 중요한 차이점이 있다.

중복 요소의 처리
- Set: Set은 중복 요소를 허용하지 않는다. 즉, Set에 동일한 값을 여러 번 추가해도 중복 요소가 저장되지 않는다. Set은 값의 유일성을 보장한다.
- 배열: 배열은 중복 요소를 허용한다. 동일한 값을 배열에 여러 번 추가할 수 있다.
요소 순서
- Set: Set은 요소를 저장할 때 순서를 보장하지 않는다. Set에 추가한 순서대로 요소가 저장되지 않으며, 순서가 정해져 있지 않다.
- 배열: 배열은 요소를 저장한 순서를 유지한다. 즉, 배열에 요소를 추가한 순서대로 요소가 저장되며, 순서가 중요하다.
인덱싱
- Set: Set은 인덱싱(indexing)을 지원하지 않는다. 즉, Set에서 특정 위치의 요소에 직접 접근할 수 없다.
- 배열: 배열은 요소에 대한 인덱스를 사용하여 특정 위치의 요소에 직접 접근할 수 있다.
반복
- Set: Set은 forEach 메서드 또는 for...of 반복문을 사용하여 요소를 순회할 수 있다.
- 배열: 배열은 forEach 메서드, for...of 반복문, 또는 일반 for 반복문을 사용하여 요소를 순회할 수 있다.
메서드 및 기능
- Set: Set은 값의 유일성과 집합 연산을 지원하는 메서드(예: add, delete, has, clear)를 제공한다.
- 배열: 배열은 요소의 추가, 삭제, 검색, 정렬 등 다양한 메서드와 기능(예: push, pop, shift, unshift, sort, filter, map)을 지원한다.

2-3. 셋(Set)과 배열(Array)의 평균 시간 복잡도 비교

셋(Set)
- add(value): O(1) (해시 함수를 사용하므로 해시 충돌이 적으면 O(1)이다.)
- delete(value): O(1)
- has(value): O(1)
- size 또는 length: O(1)
배열(Array)
- push(value): O(1) (배열의 크기가 동적으로 조정되면 O(N)의 복잡도가 발생할 수 있다.)
- pop(): O(1)
- shift(): O(N) (모든 요소를 앞으로 이동해야 하므로)
- unshift(value): O(N) (모든 요소를 뒤로 밀어야 하므로)
- splice(): O(N) (삭제 또는 삽입하는 요소의 수에 따라 다르다.)

👉🏻 따라서 Set은 요소 추가, 삭제 및 확인 연산에서 일반적으로 상수 시간 복잡도 O(1)을 가지므로, 중복 요소를 허용하지 않고 요소 존재 여부를 빠르게 확인하는 데 적합하다.

👉🏻 배열은 요소의 순서가 중요하거나 동적 크기 조정이 필요한 경우에 유용하다. 예를 들어, 인덱스를 사용하여 특정 요소에 직접 접근하거나 요소를 정렬하거나 필터링하는 경우 배열이 유용하다.

3. 해시 테이블 (Hash Table)

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료 구조로 빠르게 데이터를 검색할 수 있는 자료구조이다. 매우 큰 숫자 데이터나 문자열과 같은 임의의 길이를 가진 Key값을 고정된 유한한 크기의 값으로 매핑한 테이블로, O(1)의 빠른 속도로 데이터를 찾을 수 있다.
해시 테이블은 해시 함수를 사용해서 변환한 값을 배열(버킷)의 index로 정하고 값을 저장한다.
해시 함수는 Key값을 받아 해시 함수를 사용하여 고정 크기의 해시 코드(해시 값)를 반환한다. 이 해시 코드는 배열의 index로 사용되어 값을 저장하거나 검색하는 데 사용된다. 여기서 실제 값이 저장되는 장소를 Bucket 또는 Slot이라고 한다.
- 해시 함수는 여러 종류가 있고, Key를 해시 코드로 변환하고 충돌을 최소화하기 위한 목적으로 설계 된다.

3-1. 해시 함수(Hash Function)의 종류

Division Method (나눗셈 방법): 이 방법은 키를 테이블 크기로 나눈 나머지를 해시 코드로 사용한다. 즉, hash(key) = key % table_size와 같은 형태로 표현된다. 이 방법은 간단하고 빠르지만, 특정 키 패턴에 대해서는 충돌이 발생할 수 있다.
Multiplication Method (곱셈 방법): 이 방법은 키를 0과 1 사이의 실수로 변환한 다음 테이블 크기를 곱한 후 정수 부분을 취한다. hash(key) = floor(table_size * (key * A - floor(key * A)))와 같은 형태로 표현된다. 상수 A는 일반적으로 0보다 크고 1보다 작은 값을 사용한다. 이 방법은 좋은 분포를 제공하는데, 충돌을 최소화하는 데 도움이 된다.
Folding Method (접기 방법): 이 방법은 키를 일정한 크기의 부분 키로 나누고 이를 합하여 해시 코드를 생성한다. 예를 들어, 123456789을 12, 34, 56, 78, 9로 나누고 합쳐서 해시 코드를 생성할 수 있다.
Mid-Square Method (중앙제곱 방법): 이 방법은 키를 제곱한 다음 중간 일부 자리를 선택하여 해시 코드로 사용한다. 예를 들어, 1234를 제곱하면 1522756이고, 여기서 중간의 3자리인 227을 해시 코드로 사용할 수 있다.
SHA-1, SHA-256 등 암호학적 해시 함수: 보안이 중요한 경우, 암호학적 해시 함수를 사용할 수 있다. 이러한 함수는 충돌을 최소화하고, 무작위성과 안전성을 제공합니다. 하지만 일반적인 해시 테이블에 비해 계산 비용이 높을 수 있다.

3-2. 시간 복잡도

평균: O(1), 최악: O(N)
각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다.
하지만 데이터의 충돌이 발생한 경우 연결 리스트 또는 다른 자료 구조를 순회하여 검색해야 하므로 최악의 경우에는 O(N)까지 시간복잡도가 증가할 수 있다.

Reference.