큐(Queue)와 해시(Hash)

taeyul_de·2025년 2월 25일

큐(Queue)

JS 엔진은 큐를 가지고있다.
JS 동작원리 중 스택을 실행 하기 위해 큐를 사용한다.(Callback Queue)

데이터를 순차적으로 처리함.
사용 예로는 티켓예매 사이트를 예로 들수있다
티켓을 예매하기 위해 우선적으로 예매 버튼을 클릭한 사람에게 판매할수있는..?
선입선출 (FIFO)!!

1️⃣ shift() 메서드 사용하기

shift() 메서드는 배열의 첫 번째 요소를 제거하고 반환한다.
큐의 dequeue 동작과 동일한 원리.

const queue = [1, 2, 3, 4];
console.log(queue.shift()); // 1 (제거된 값)
console.log(queue); // [2, 3, 4]

✅ 장점: 간단하고 코드가 직관적임
⚠️ 단점: 배열 요소 이동으로 시간 복잡도 O(n)

2️⃣ 배열을 이용하는 방식

큐를 배열로 구현할 때 push() 와 shift() 를 사용한다.
삽입: push() – O(1)
삭제: shift() – O(n) (앞의 요소들이 한 칸씩 이동해야 함)

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

✅ 장점: 코드가 간단하고 이해하기 쉬움
⚠️ 단점: 대규모 데이터 처리 시 비효율적

3️⃣ 연결 리스트를 이용하는 방식

연결 리스트(Linked List) 를 사용하면 shift() 시 발생하는 문제를 해결할 수 있다.
삽입과 삭제 모두 O(1)의 시간 복잡도를 가진다.

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

class LinkedListQueue {
  constructor() {
    this.front = null;
    this.rear = null;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.front) this.front = newNode;
    else this.rear.next = newNode;
    this.rear = newNode;
  }

  dequeue() {
    if (!this.front) return null;
    const value = this.front.value;
    this.front = this.front.next;
    if (!this.front) this.rear = null;
    return value;
  }
}

✅ 장점: 삽입과 삭제 시 빠름
⚠️ 단점: 메모리 사용량 증가

🔑 해시(Hash)

1️⃣ 해시의 개념

해시(Hash) 란 데이터를 고정된 크기의 해시 값으로 변환하여 저장하고 빠르게 검색할 수 있는 방법이다.
"사물함 번호로 물건 찾기"와 유사한 개념이다.

2️⃣ 해시의 특징

빠른 검색: 평균 O(1)의 시간 복잡도
효율적인 데이터 관리: 큰 데이터 집합에서 유용
충돌 발생 가능성: 서로 다른 키가 같은 해시 값을 가질 수 있음

3️⃣ 해시 함수

입력 데이터를 고정된 크기의 해시 값으로 변환하는 함수.
좋은 해시 함수의 조건:
- 빠른 계산 속도
- 균등한 값 분포
- 충돌 최소화

function simpleHash(key, size) {
  let hashValue = 0;
  for (let char of key) {
    hashValue += char.charCodeAt(0);
  }
  return hashValue % size;
}

4️⃣ 해시 함수를 구현할 때 고려할 내용

해시 충돌 가능성 최소화
계산 속도와 해시 테이블 크기 균형
해시 값의 균등한 분포

5️⃣ 자주 사용하는 해시 함수 알아보기

Division Method: hash = key % tableSize
Multiplication Method: hash = floor((key * A) % 1 * tableSize)
JavaScript 내장 함수: 객체의 속성 접근 시 내부적으로 해시 사용

6️⃣ 충돌 처리

충돌(Collision): 서로 다른 두 입력이 같은 해시 값을 가질 때 발생한다.
해결 방법:
- 체이닝(Chaining)
- 개방 주소법(Open Addressing)

7️⃣ 체이닝으로 처리하기

같은 인덱스에 여러 값을 연결 리스트로 저장한다.
간단하고 구현이 쉬움

class HashTable {
  constructor(size = 50) {
    this.table = new Array(size);
  }

  hash(key) {
    let hashValue = 0;
    for (let char of key) {
      hashValue += char.charCodeAt(0);
    }
    return hashValue % this.table.length;
  }

  set(key, value) {
    const index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    this.table[index].push([key, value]);
  }

  get(key) {
    const index = this.hash(key);
    if (this.table[index]) {
      for (let [storedKey, value] of this.table[index]) {
        if (storedKey === key) return value;
      }
    }
    return undefined;
  }
}

✅ 장점: 충돌 처리 시 연결 리스트 사용으로 유연함
⚠️ 단점: 추가 메모리 사용

8️⃣ 개방 주소 법으로 처리하기

충돌 발생 시 빈 인덱스를 찾아 데이터를 저장.
방식 종류:
- 선형 탐사(Linear Probing): 한 칸씩 이동하며 탐색
- 이차 탐사(Quadratic Probing): 일정한 간격으로 탐색
- 더블 해싱(Double Hashing): 두 번째 해시 함수를 사용

class OpenAddressHashTable {
  constructor(size = 50) {
    this.table = new Array(size).fill(null);
  }

  hash(key) {
    let hashValue = 0;
    for (let char of key) {
      hashValue += char.charCodeAt(0);
    }
    return hashValue % this.table.length;
  }

  set(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index + 1) % this.table.length; // 선형 탐사
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) return this.table[index][1];
      index = (index + 1) % this.table.length;
    }
    return undefined;
  }
}