[바미] - 자료구조 정리(JS)

자료구조

자료구조(data structure)는 데이터를 어떤 형식으로 조직해 저장할 것인지와 관련되어 있음.

알고리즘은 각각의 자료구조로 표현된 데이터를 이용해 문제를 해결하는 과정.

배열

배열(Array)은 정수형이면 정수형, 문자형이면 문자형처럼 동일한 데이터 타입의 여러 데이터를 저장하는 자료구조.

데이터 하나하나의 크기가 모두 같고, 메모리상의 연속된 공간에 데이터가 저장.

• 배열에서 각 요소를 탐색하는 시간은 시간 복잡도O(1), 삽입 또는 삭제하는 맨 마지막의 요소의 경우 O(1)
• 가운데 요소의 경우 O(n)소요 → O(n)은 요소의 수(n)에 비례해 요소의 수가 많을수록 더 많은 시간이 걸린다.

O(1) - 상수 시간 복잡도 : 입력되는 요소 수에 상관없이 항상 동일한 시간이 걸린다.
O(n) - 선형 시간 복잡도 : 입력되는 요소 수의 비례해 시간이 걸린다.
O(log n) - 로그 시간 복잡도 : 로그는 지수적으로 증가하는 값인데 입력되는 요소 수가 많아져도 비교적 시간 상승폭이 완만하다.
O(n^2) - 제곱 시간 복잡도 : 입력되는 요소 수의 제곱에 비례해 시간이 걸린다.

https://codesk.tistory.com/561

배열에서 마지막 요소를 삽입하거나 삭제할 때는 다른 요소에 영향을 주지 않지만, 가운데 요소를 삽입하거나 삭제할 때는 남은 요소를 하나씩 이동해야 함.

1	2	3	4	22	5	6	7

// 배열 출력
function printArray(arr) {
    console.log(arr.join(" "));
}

// 요소 삽입
function insertElement(arr, element, index) {
    let newArr = new Array(arr.length + 1);

    for (let i = 0, j = 0; i < arr.length; i++) {
        if (i === index) {
            newArr[i] = element;
        } else {
            newArr[i] = arr[j++];
        }
    }
    return newArr;
}

// 요소 삭제
function deleteElement(arr, index) {
    if (index < 0 || index >= arr.length) {
        console.log("인덱스 범위를 벗어났습니다.");
        return arr;
    }

    let newArr = new Array(arr.length - 1);

    for (let i = 0, j = 0; i < arr.length; i++) {
        if (i === index) {
            continue;
        }
        newArr[j++] = arr[i];
    }
    return newArr;
}

let arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200];

console.log("초기 배열 :", printArray(arr));

// 삽입
arr = insertElement(arr, 105, 10);
console.log("10번 째 인덱스에 105를 삽입 :", printArray(arr));

// 삭제
arr = deleteElement(arr, 15);
console.log("15번 째 인덱스에 있는 요소를 삭제 :", printArray(arr));

연결리스트

연결리스트(linked-list)는 포인터를 통해 여러 노드(node)가 연결돼 있는 자료구조.

각 노드는 데이터를 저장하는 공간과 다음 노드를 가리키는 포인터 공간으로 구성된다.

이러한 구조덕에 연결 리스트는 삽입이나 삭제에 걸리는 시간이 O(1)로 빠른편

노드를 삽입하려면 새 노드를 만들어 노드 사이에 포인터로 연결하고, 노드를 삭제하려면 바로 앞의 포인터만 바꾸면 되기 때문에 가능함.

특정 데이터가 몇 번째 노드에 위치하는 지 직접적으로 알 수 없음. 그래서 탐색 시 노드를 순회하여 데이터를 찾아야 함. 그래서 탐색시간이 O(n) 소요되는 단점

노드
데이터 구조에서 데이터를 저장하는 기본 단위

포인터
다음 노드의 ‘주소’를 저장하고 있는 변수

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }

    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            return;
        }
        this.tail.next = newNode;
        this.tail = newNode;
    }

    deleteWithValue(data) {
        console.log(`삭제 시도: ${data}`);
        if (!this.head) return;

        // head 삭제
        if (this.head.data === data) {
            console.log(`head 노드 삭제: ${data}`);
            this.head = this.head.next;
            if (!this.head) this.tail = null;
            return;
        }

        let current = this.head;
        while (current.next) {
            console.log(`현재 노드: ${current.data}, 다음 노드: ${current.next.data}`);
            if (current.next.data === data) {
                console.log(`삭제 성공: ${current.next.data}`);
                if (current.next === this.tail) {
                    this.tail = current;
                    console.log('tail 갱신됨');
                }
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }

        console.log('삭제 대상이 없음');
    }

    printList() {
        let current = this.head;
        let output = '';
        while (current) {
            output += current.data + ' -> ';
            current = current.next;
        }
        output += 'null';
        console.log(output);
    }
}

// 테스트
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);

console.log('초기 상태:');
list.printList();

list.deleteWithValue(2);

console.log('삭제 후 상태:');
list.printList();

console.log('현재 tail:', list.tail?.data);

스택

스택(Stack) 찬장에 쌓인 접시 더미 같은 더미를 의미함.

스택의 가장 큰 특징은 후입선출(LIFO, Last In First Out) → 가장 먼저 들어온 데이터가 가장 나중에 나가고,
가장 나중에 들어온 데이터가 가장 먼저 나간다.

스택에 데이터를 삽입하는 것을 푸시(push), 데이터를 삭제하는 것을 팝(pop), 스택의 최상단을 탑(top)이라고 부름

class Stack {
    constructor(size) {
        this.arr = new Array(size);
        this.capacity = size;
        this.top = -1;
    }

    // push
    push(item) {
        if(this.isFull()) {
            console.log("Stack is full");
            return;
        }
        this.arr[++this.top] = item;
    }

    // pop
    pop() {
        if(this.isEmpty()) {
            console.log("Stack is empty");
            return;
        }
        return this.arr[this.top--];
    }

    // 현재 top 요소 반환
    peek() {
        if(this.isEmpty()) {
            console.log("Stack is empty");
            return -1;
        }
        return this.arr[this.top];
    }

    // 스택 비어있는지 확인
    isEmpty() {
        return this.top === -1;
    }

    // 스택 가득 차있는지 확인
    isFull() {
        return this.top === this.capacity - 1;
    }

    // 스택 크기 반환
    size() {
        return this.top + 1;
    }
}

const size = 5;
const stack = new Stack(size);

for(let i = 1; i <= size; i++) {
    stack.push(i);
}

// 현재 top 요소 확인 
console.log("현재 top 요소: ", stack.peek());

// pop
stack.pop();
console.log("현재 top 요소: ", stack.peek());

console.log("스택의 크기: ", stack.size());

while(!stack.isEmpty()) {
    stack.pop();
}

// 스택 비어있는지 확인
if (stack.isEmpty()) {
    console.log("스택이 비어있습니다.");
}

큐

큐(Queue)는 자료 구조 중 하나로 데이터가 FIFO(First In First Out)방식으로 관리되는 구조.

주로 운영체제의 작업 스케쥴링, 프린터 작업 관리, 데이터 스트리밍 등 다양한 분야에서 사용된다.

큐는 용도에 따라 종류가 다양하니 큐의 종류에 대해 추가로 살펴보는 것을 추천.

큐의 주요 연산

큐는 선형 자료 구조로 불리고, 두 개의 주요 연산을 제공함.

• Enqueue - 큐의 끝에 데이터를 삽입하는 연산.
• Dequeue - 큐의 앞에서 데이터를 제거하고 반환하는 연산.

class Queue {
    constructor(size) {
        this.arr = new Array(size);
        this.capacity = size;
        this.front = 0;
        this.rear = -1;
        this.count = 0;
    }

    // 요소 추가(enqueue)
    enqueue(item) {
        if(this.isFull()) {
            console.log("Queue is full");
            return;
        }

        this.rear = (this.rear + 1) % this.capacity;
        this.arr[this.rear] = item;
        this.count++;   
    }

    // 요소 제거(dequeue)
    dequeue() {
        if(this.isEmpty()) {
            console.log("Queue is empty");
            return -1;
        }

        const item = this.arr[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.count--;
        return item;
    }

    // 첫 번째 요소 확인
    peek() {
        if(this.isEmpty()) {
            console.log("Queue is empty");
            return -1;
        }
        return this.arr[this.front];
    }

    // 큐 비어있는지 확인
    isEmpty() {
        return this.count === 0;
    }

    // 큐가 가득 차있는지 확인
    isFull() {
        return this.count === this.capacity;
    }

    // 큐 크기 반환
    size() {
        return this.count;
    }
}

const size = 20;
const queue = new Queue(size);

// for(let i = 1; i <= size; i++) {
//     queue.enqueue(i);
// }

while(!queue.isFull()) {
    queue.enqueue(Math.floor(Math.random() * 100));
}

console.log("큐의 크기: ", queue.size());
console.log("첫 번째 요소: ", queue.peek());

queue.dequeue();
console.log("첫 번째 요소: ", queue.peek());

while(!queue.isEmpty()) {
    queue.dequeue();
}

if(queue.isEmpty()) {
    console.log("큐가 비어있습니다.");
}

그래프

[바미] 자료구조 - 그래프(Graph)

정점과 간선으로 이뤄진 자료구조.

❓ 정점
정점은 그래프에서 데이터를 저장하는 기본 단위.
노드(Node)라고 부르기도 하고, 다양한 데이터를 저장할 수 있음.

❓ 간선
정점을 연결하는 선으로 링크(link) 또는 브랜치(branch)라고도 함.

간선에는 방향이 존재하는 그래프와 방향이 없는 그래프가 존재함

그래프 탐색 방법 중 가장 기본적인 두가지 방법이 있는데 하나는 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Bredth-First Search)이 존재함.

깊이 우선 탐색(DFS, Depth-First Search)

그래프의 한 정점에서 시작하여 가능한 멀리까지 탐색한 다음, 다시 돌아와서 다른 경로를 탐색하는 방식.

이 때 DFS는 스택(Stack) 자료 구조를 사용하거나 재귀(Recursion)을 통해 구현

깊이 우선 탐색 동작 순서

1. 시작 정점을 방문, 이를 방문했다고 표시.
2. 인접한 정점들 중 아직 방문하지 않은 정점으로 이동.
3. 더 이상 방문할 인접 정점이 없으면 이전 정점으로 돌아감.
4. 모든 정점을 방문할 때까지 1~3번을 반복.

너비 우선 탐색(BFS, Bredth-First Search)

그래프의 한 정점에서 시작하여 인접한 정점들을 먼저 모두 탐색한 후에 다음 레벨의 정점들을 탐색하는 방식.

큐를 주로 사용하여 구현.

너비 우선 탐색 동작 순서

1. 시작 정점을 큐에 넣고, 이를 방문 했다고 표시.
2. 큐에서 정점을 꺼내 해당 정점에 인접한 정점들을 모두 큐에 넣고 방문했다고 표시.
3. 큐가 빌 때까지 2번을 반복.

//  그래프 클래스 정의
class Graph {
    constructor(numVertices) {
        this.numVertices = numVertices; // 정점(노드)의 개수
        // 각 정점마다 연결된 인접 정점들을 저장할 배열 초기화
        // ex) adjacencyList[0] = [1, 4] 0번 정점은 1번과 4번 정점과 연결되어 있다.
        this.adjacencyList = new Array(numVertices).fill(null).map(() => []);
    }

    // 무방향 간선 추가
    addEdge(source, destination) {
        // 소스 정점에 대한 인접 리스트에 목적지 정점 추가
        this.adjacencyList[source].push(destination);
        // 목적지 정점에 대한 인접 리스트에 소스 정점 추가
        this.adjacencyList[destination].push(source);
    }

    // 인접 리스트 형식으로 그래프 출력
    printGraph() {
        for (let i = 0; i < this.numVertices; i++) {
            // 정점 i에 연결된 모든 노드를 문자열로 연결
            let neighbors = this.adjacencyList[i].join(", ");
            // 예: Vertex 1: -> 0 -> 2 -> 3
            console.log(`Vertex ${i}: -> ${neighbors}`);
        }
    }

    // 깊이 우선 탐색(DFS) 구현
    dfs(startVertex) {
        // 방문한 노드를 추적하는 배열 (모두 false로 초기화)
        const visited = new Array(this.numVertices).fill(false);
        // 재귀적으로 방문하는 함수 호출
        this.dfsUtil(startVertex, visited);
    }

    // DFS 재귀 함수
    dfsUtil(vertex, visited) {
        // 현재 노드를 방문 처리
        visited[vertex] = true;
        console.log(`${vertex} `); // 현재 정점 출력 (공백으로 구분)

        // 현재 정점에 연결된 이웃들에 대해 반복
        for(const neighbor of this.adjacencyList[vertex]) {
            // 이웃 노드가 방문되지 않았다면 재귀 호출
            if(!visited[neighbor]) {
                this.dfsUtil(neighbor, visited);
            }
        }
    }

    // 너비 우선 탐색(BFS) 구현
    bfs(startVertex) {
        // 방문 여부 배열 초기화
        const visited = new Array(this.numVertices).fill(false);
        // 큐 초기화
        const queue = [];
        // 시작 정점 방문
        visited[startVertex] = true;
        // 시작 정점을 큐에 추가
        queue.push(startVertex);

        while(queue.length > 0) {
            // 큐에서 정점 추출
            const currentVertex = queue.shift();
            // 현재 정점 출력
            console.log(`${currentVertex} `);

            // 현재 정점에 연결된 모든 이웃 확인
            for (const neighbor of this.adjacencyList[currentVertex]) {
                // 이웃 노드가 방문되지 않았다면 방문 처리 후 큐에 추가
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }
    }
}

// 정점 5개로 구성된 그래프가 생성
const graph = new Graph(5);

// 간선을 추가
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);

// 그래프 구조 출력
graph.printGraph();

// DFS 탐색 결과 출력
console.log("\nDFS 탐색을 0번 vertex부터 시작:");
graph.dfs(0);

// BFS 탐색 결과 출력
console.log("\nBFS 탐색을 0번 vertex부터 시작:");
graph.bfs(0);  

트리(Tree)

[바미] 자료구조 - 트리(Tree)

계층적인 구조를 나타내는 자료구조.

트리는 루트 노드(root node)에서 시작하여 각 노드가 0개 이상의 자식 노드를 가지며, 자식 노드들도 다시 트리구조를 형성하는 형태로 이루어져 있음.

트리의 구조

• 루트 노드(root node): 부모가 없는 최상위 노드. 트리는 하나의 루트 노드만을 가집니다.
• 단말 노드(leaf node): 자식 노드가 없는 노드. '말단 노드' 또는 '잎 노드'라고도 부릅니다.
• 내부 노드(internal node): 단말 노드가 아닌 노드를 의미합니다.
• 간선(edge): 노드 간을 연결하는 선으로, 링크(link) 또는 브랜치(branch)라고도 부릅니다.
• 형제 노드(sibling): 같은 부모를 가지는 노드들을 의미합니다.
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수를 의미합니다.
• 노드의 깊이(depth): 루트 노드에서 특정 노드에 도달하기 위해 거쳐야 하는 간선의 수를 의미합니다.
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드들의 집합을 의미합니다.
• 노드의 차수(degree): 각 노드가 지닌 자식 노드(하위 트리)의 개수를 의미합니다.
• 트리의 차수(degree of tree): 트리 내에서 가장 큰 노드의 차수를 의미합니다.
• 트리의 높이(height): 루트 노드에서 가장 깊숙한 노드의 깊이를 의미합니다.

트리의 종류

일반 트리와 이진 트리로 나뉨.

일반 트리(General Tree)는 각 노드가 임의의 수의 자식 노드를 가질수 있는 트리.

이진 트리(Binanary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리.

B-Tree → 이진 트리(Binanary Tree)

         → 균형 이진 트리(Balanced Binary Tree)

균형 이진 트리(Balanced Binary Tree) 모든 리프 노드가 루트로부터 동일한 거리에 있거나 거리가 1만큼 차이나는 트리 대표적으로 AVL 트리와 레드-블랙 트리가 있음

• 일반 트리

• 균형 이진 트리(Balanced Binary Tree) 구조

• 이진 트리(Binanary Tree)

트리의 탐색 방법

트리의 깊이 우선탐색(DFS)에는 전위 순회, 중위 순회, 후위 순회 방법이 있음.

전위 순회

현재 노드를 먼저 방문한 후, 왼쪽 자식노드와 오른쪽 자식노드를 순서대로 방문하는 방법

현재 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드

A→B→D→E→C→F→G

중위 순회

왼쪽 자식 노드를 먼저 방문한 후, 현재 노드를 방문하고, 마지막으로 오른쪽 자식 노드를 방문하는 방법.

왼쪽 자식 노드 → 현재 노드 → 오른쪽 자식 노드

D → B → E → A → F → C → G

후위 순회

왼쪽 자식 노드와 오른쪽 자식 노드를 먼저 방문한 후, 현재 노드를 방문하는 방법

왼쪽 자식 노드 → 오른쪽 자식 노드 → 현재 노드

D → E → B → F → G → C → A

리프 노드를 가장 먼저 방문하는 게 특징, 트리의 구조를 삭제하거나, 후위 표기법을 계산하는데 사용

// 이진 탐색 트리 노드
class BinaryTreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

//  이진 탐색 트리
class BinaryTree {
    constructor() {
        this.root = null;
    }

    // 트리에 키 삽입
    insert(key) {
        this.root = this._insertRec(this.root, key); // 재귀적 삽입
    }

    // 재귀적으로 노드를 삽입
    _insertRec(node, key) {
        // 비어있으면 새 노드를 생성
        if (node === null) {
            return new BinaryTreeNode(key);
        }

        if (key < node.data) {
            node.left = this._insertRec(node.left, key);
        } else if (key > node.data) {
            node.right = this._insertRec(node.right, key);
        }

        return node; // 현재 노드 반환
    }

    inorder() {
        this._inorderRec(this.root);
        console.log();
    }

    // 중위 순회 재귀 함수
    _inorderRec(node) {
        if (node !== null) {
            this._inorderRec(node.left);
            console.log(node.data + " ");
            this._inorderRec(node.right);
        }
    }
}

// B-tree Node 클래스 (다차원 B-트리의 노드)
class BTreeNode {
    constructor(t, leaf) {
        this.t = t; // 최소 차수 (자식 수 /키 수 기준)
        this.leaf = leaf; // 리프 노드 여부
        this.keys = new Array(2 * t - 1); // 키 배열
        this.children = new Array(2 * t); // 자식 노드 배열
        this.n = 0; // 현재 키 수
    }

    // B-트리 순회 (inorder)
    traverse() {
        let i;
        for(i = 0; i < this.n; i++) {
            if(!this.leaf) {
                this.children[i].traverse();
            }
            console.log(this.keys[i] + " ");
        }

        // 마지막 자식도 순회
        if(!this.leaf) {
            this.children[i].traverse();
        }
    }

    // 키 검색
    search(key) {
        let i = 0;
        // 현재 노드에서 k보다 작거나 같은 위치를 찾는다
        while(i < this.n && key > this.keys[i]) {
            i++;
        }

        if (this.keys[i] === key) {
            return this;
        }
        if(this.leaf) {
            return null;
        }

        return this.children[i].search(key);
    }

    // 현재 노드가 가득 차지 않은 상태에서 삽입
    insertNonFull(key) {
        let i = this.n - 1; // 맨 오른쪽 키부터 비교

        if (this.leaf) {
            // 리프이면 키 삽입 위치를 찾아 오른쪽으로 밀어라
            while(i >= 0 && key < this.keys[i]) {
                this.keys[i + 1] = this.keys[i];
                i--;
            }
            this.keys[i + 1] = key;
            this.n++;
        } else {
            // 리프가 아니면 키 삽입 위치를 찾아 자식 노드로 이동
            while(i >= 0 && key < this.keys[i]) {
                i--;
            }

            i = i + 1;

            // 해당 자식이 가득 찬 경우 분할
            if (this.children[i].n === 2 * this.t - 1) {

                // 분할 후 위치 조정
                if (this.keys[i + 1] < key) {
                    i++;
                }
            }
            // 자식 노드에 삽입 계속
            this.children[i].insertNonFull(key);
        }
    }

    // 자식 노드 분할
    splitChild(i, y) {
        // 새로운 노드 z 생성
        let z = new BTreeNode(y.t, y.leaf);
        // z는 t - 1개의 키를 가짐
        z.n = this.t - 1;

        // 기존 자식 노드 y의 키를 z로 이동
        for(let j = 0; j < this.t - 1; j++) {
            z.keys[j] = y.keys[j + this.t];
        }

        // y가 리프가 아니면 자식들도 z로 이동
        if (!y.leaf) {
            for (let j = 0; j < this.t; j++) {
                z.children[j] = y.children[j + this.t];
            }
        }

        // y의 키 수를 t - 1로 조정
        y.n = this.t - 1;

        // 새로운 자식 노드 z를 현재 노드에 삽입
        for (let j = this.n; j >= i + 1; j--) {
            this.children[j + 1] = this.children[j];
        }
        this.children[i + 1] = z;

        // 부모 키들도 밀어서 y의 중간 키 삽입
        for (let j = this.n - 1; j >= i; j--) {
            this.keys[j + 1] = this.keys[j];
        }
        this.keys[i] = y.keys[this.t - 1];

        // 부모의 키 개수 증가
        this.n++;
    }
}

// B-tree 클래스
class BTree {
    constructor(t) {
        this.root = null;
        this.t = t;
    }

    // 전체 트리 순회
    traverse() {
        if(this.root !== null) { 
            this.root.traverse();
        }
        console.log();
    }

    // 검색 -> 루트부터 검색 시작
    search(key) {
        return this.root === null ? null : this.root.search(key);
    }

    // 키 삽입
    insert(key) {
        // 루트가 없으면 새로운 노드 생성
        if(this.root === null) {
            this.root = new BTreeNode(this.t, true);
            this.root.keys[0] = key;
            this.root.n = 1;
        } else {
            // 루트가 가득 차있으면 분할
            if(this.root.n === 2 * this.t - 1) {
                // 새 루트 생성
                let s = new BTreeNode(this.t, false);
                s.children[0] = this.root; // 기존루트를 자식으로 삽입
                s.splitChild(0, this.root);

                let i = 0;
                if (s.keys[0] < key) {
                    i++;
                }
                s.children[i].insertNonFull(key);
                this.root = s;
            } else {
                this.root.insertNonFull(key);
            }
        }
    }
}

// 이진 탐색 트리 생성 및 데이터 삽입
const binaryTree = new BinaryTree();
binaryTree.insert(10);
binaryTree.insert(20);
binaryTree.insert(5);
binaryTree.insert(6);
binaryTree.insert(12);
binaryTree.insert(30);
binaryTree.insert(7);
binaryTree.insert(17);

// 이진 탐색 트리 출력
console.log("이진 탐색 트리 중위 순회:");
binaryTree.inorder();

// B-트리 생성 (차수 t = 3)
const t = 3;
const bTree = new BTree(t);

// 키 삽입
bTree.insert(10);
bTree.insert(20);
bTree.insert(5);
bTree.insert(6);
bTree.insert(12);
bTree.insert(30);
bTree.insert(7);
bTree.insert(17);

// B-트리 출력
console.log("B-트리 중위 순회:");
bTree.traverse(

맵

Map 은 ECMAScript 2015(ES6)에서 도입된 표준 빌트‑인 객체로, 키‑값 쌍을 효율적으로 저장하고 다룰 수 있도록 설계된 컬렉션임.

Map은 언제 쓰면 좋은가?

문제	전통적인 해결책 ({} 객체)	Map 사용 시 장점
모든 값을 키로 쓰고 싶다	문자열/심벌만 가능	객체·함수·NaN 까지 아무 값이나 키 가능
삽입 순서를 유지하고 싶다	명세적으로는 보장 X(엔진마다 우연히 맞을 수 있음)	항상 순서 보장
빠르게 크기(size)를 알고 싶다	Object.keys(obj).length 처럼 매번 계산	map.size 프로퍼티 → O(1)
잦은 추가/삭제가 필요	해시테이블 최적화는 엔진마다 다름	Map 은 내부적으로 해시 구조로 최적화

Map vs Object

구분	{} (Plain Object)	Map
키 타입	문자열·심벌	모든 값
순서	공식적 보장 X (ES 사양: 일부 규칙만)	삽입 순서 고정
크기 구하기	Object.keys(o).length (O(n))	.size (O(1))
직관적 JSON 직렬화	JSON.stringify(obj) 지원	수동 변환 필요
주요 용도	정적 데이터, JSON, 단순 구조체	빈번한 추가/삭제, 고성능 Lookup 테이블

주요 메소드

메서드	설명
set(key, value)	새 쌍 추가 or 기존 값 업데이트
get(key)	값 조회 (없으면 undefined)
has(key)	키 존재 여부 Boolean
delete(key)	쌍 제거, 성공 여부 반환
clear()	전체 초기화
keys() / values() / entries()	각각 키, 값, [키, 값] 이터레이터
[Symbol.iterator]	for...of 직접 순회 가능 (entries와 동일)

// 해시맵 구현
function HashMap(initialCapacity = 16) {
    this.buckets = new Array(initialCapacity).fill(null).map(() => []); // 버킷 배열
    this.count = 0; // 저장된 데이터 개수
    this.loadFactor = 0.75; // 로드 팩터
}

// 해시 함수 - 문자열로 변환한 후 아스키 코드로 간단히 해싱
HashMap.prototype.hash = function(key) {
    // 객체나 배열도 문자열로 변환
    let str = typeof key === 'string' ? key : typeof key === 'number' ? key.toString() : JSON.stringify(key);

    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        // 32비트 양수
        hsah = (hash * 31 + str.charCodeAt(i) >>> 0);
    }
    // 버킷 인덱스로 변환
    return hash % this.buckets.length;
}

// 버킷 수를 2배로 늘리고 기존 데이터 재배치
HashMap.prototype.resize = function() {
    const oldBuckets = this.buckets;
    this.buckets = new Array(oldBuckets.length * 2).fill(null).map(() => []);
    this.count = 0;

    // 기존 키-값을 새 배열에 다시 넣기
    for (let bucket of oldBuckets) {
        for (const [key, value] of bucket) {
            this.set(key, value);
        }
    }
};

// 키-값 쌍 추가 (중복 키가 들어오면 값을 업데이트)
HashMap.prototype.set = function(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    // 같은 키가 있으면 값만 업데이트
    for (let pair of bucket) {
        if (Object.is(pair[0], key)) {
            pair[1] = value;
            return this;
        }
    }

    // 새로운 키 추가
    bucket.push([key, value]);
    this.count++;

    // 로드 팩터 초과 시 버킷 수 늘리기
    if (this.count / this.buckets.length > this.loadFactor) {
        this.resize();
    }

    return this;
}

// 키로 값을 조회
HashMap.prototype.get = function(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    for (const [k, v] of bucket) {
        if (Object.is(k, key)) {
            return v;
        }
    }
    return undefined;
}

// 키 존재 여부 확인
HashMap.prototype.has = function(key) {
    return this.get(key) !== undefined;
}

// 키 삭제
HashMap.prototype.delete = function(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    for (let i = 0; i < bucket.length; i++) {
        if (Object.is(bucket[i][0], key)) {
            bucket.splice(i, 1); // 키 삭제
            this.count--;
            return true;
        }
    }

    return false;
}

// 모든 데이터 삭제
HashMap.prototype.clear = function() {
    this.buckets = new Array(16).fill(null).map(() => []); // 버킷 배열
    this.count = 0;
}

// 현재 저장된 키-값 쌍의 개수 반환
HashMap.prototype.size = function() {
    return this.count;
};

// 키 목록 반환
HashMap.prototype.keys = function() {
    const result = [];
    for (const bucket of this.buckets) {
        for (const [key] of bucket) {
            result.push(key);
        }
    }
    return result;
}

// 값 목록 반환
HashMap.prototype.values = function() {
    const result = [];
    for (const bucket of this.buckets) {
        for (const [, value] of bucket) {
            result.push(value);
        }
    }
    return result;
}

// 키 - 값 쌍 목록 반환
HashMap.prototype.entries = function() {
    const result = [];
    for (const bucket of this.buckets) {
        for (const pair of bucket) {
            result.push(pair);
        }
    }
    return result;
}

// forEach(callback) 지원
HashMap.prototype.forEach = function(callback, thisArg = undefined) {
    for (const [key, value] of this.entries()) {
        callback.call(thisArg, value, key, this);
    }
}

// 예제 사용
const map = new HashMap();
map.set('name', 'Alice');
map.set(42, 'my favorite number');
map.set({id:  1}, 'object key');

console.log(map.get('name'));
console.log(map.get(42));
console.log(map.size());

map.delete('name');

map.set('name', 'Bob');
console.log(map.get('name'));
map.set('name', 'Charlie');
console.log(map.get('name'));

map.set(42, 'my age number');
console.log(map.get(42));

map.forEach((value, key) => {
    console.log(`${key}: ${value}`);
});