구현

Python으로 스택, 원형 버퍼 큐, 분리 연결법 해시 맵을 만들고, 해시 맵의 핵심(put, get, 크기 늘리기)을 C++, Java, TypeScript로 옮깁니다. 실제 코드에서는 list, deque, dict 를 쓰면 되지만, 한 번 직접 짜 보면 이 타입들이 대신 해 주는 일이 눈에 보입니다.

Python 스택과 큐

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        return self._items[-1]


class Queue:
    def __init__(self, capacity=4):
        self._slots = [None] * capacity
        self._head = 0          # 가장 오래된 항목의 위치
        self._size = 0

    def enqueue(self, item):
        if self._size == len(self._slots):
            self._grow()
        tail = (self._head + self._size) % len(self._slots)
        self._slots[tail] = item
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("dequeue from empty queue")
        item = self._slots[self._head]
        self._slots[self._head] = None          # 참조를 놓아 줌
        self._head = (self._head + 1) % len(self._slots)
        self._size -= 1
        return item

    def _grow(self):
        n = len(self._slots)
        ordered = [self._slots[(self._head + i) % n] for i in range(self._size)]
        self._slots = ordered + [None] * n      # 두 배로, 오래된 것부터
        self._head = 0

    def __len__(self):
        return self._size


s, q = Stack(), Queue()
for x in range(6):
    s.push(x)
    q.enqueue(x)
print(s.pop(), q.dequeue(), len(q))  # 5 0 5

한 줄씩 보면 다음과 같습니다.

• Stack 은 리스트의 끝만 건드리므로 push 와 pop 이 분할 상환 O(1)입니다.
• Queue 는 가장 오래된 항목의 위치를 _head 에 두고, 꼬리 위치는 (_head + _size) % capacity 로 계산합니다. 크기를 따로 저장하면 head == tail 이 비었다는 뜻인지 가득 찼다는 뜻인지 헷갈릴 일이 없습니다.
• dequeue 는 칸을 비워 큐가 객체를 계속 붙잡고 있지 않게 합니다.
• _grow 는 큐 순서대로 항목을 두 배 크기 배열에 옮기고 _head 를 0으로 되돌립니다.

Python 분리 연결법 해시 맵

class HashMap:
    def __init__(self, capacity=8, max_load=0.75):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0
        self._max_load = max_load

    def _bucket(self, key):
        return self._buckets[hash(key) % len(self._buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:                    # 이미 있는 키: 값만 바꿈
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self._size += 1
        if self._size / len(self._buckets) > self._max_load:
            self._resize(2 * len(self._buckets))

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def remove(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._size -= 1
                return True
        return False

    def _resize(self, capacity):
        old = self._buckets
        self._buckets = [[] for _ in range(capacity)]
        for bucket in old:
            for key, value in bucket:
                self._bucket(key).append((key, value))

    def __len__(self):
        return self._size


m = HashMap()
for word in "the quick brown fox jumps over the lazy dog the end".split():
    m.put(word, m.get(word, 0) + 1)
print(m.get("the"), m.get("cat"), len(m), len(m._buckets))  # 3 None 9 16

• _bucket 은 키를 hash(key) % capacity 로 버킷 번호에 대응시킵니다. Python의 % 는 나누는 수가 양수면 결과가 음수가 아니므로 해시값이 음수여도 안전합니다.
• put 은 먼저 사슬을 훑습니다. 이미 있는 키를 갱신할 때 _size 가 늘어나면 안 됩니다.
• 적재율이 0.75를 넘으면 버킷 배열을 두 배로 늘립니다. 버킷 번호가 용량에 따라 달라지므로 _resize 는 모든 쌍을 다시 넣습니다.
• get 과 remove 는 해시를 한 번 계산하고 짧은 사슬 하나만 훑으므로 평균 O(1)입니다.

C++로 옮긴 해시 맵 핵심

#include <functional>
#include <iostream>
#include <list>
#include <string>
#include <utility>
#include <vector>

template <typename K, typename V>
class HashMap {
    std::vector<std::list<std::pair<K, V>>> buckets_;
    std::size_t size_ = 0;

    std::size_t index(const K& key, std::size_t n) const { return std::hash<K>{}(key) % n; }

    void resize(std::size_t capacity) {
        std::vector<std::list<std::pair<K, V>>> next(capacity);
        for (auto& bucket : buckets_)
            for (auto& kv : bucket) next[index(kv.first, capacity)].push_back(std::move(kv));
        buckets_.swap(next);
    }

public:
    explicit HashMap(std::size_t capacity = 8) : buckets_(capacity) {}

    void put(const K& key, const V& value) {
        auto& bucket = buckets_[index(key, buckets_.size())];
        for (auto& kv : bucket)
            if (kv.first == key) { kv.second = value; return; }
        bucket.emplace_back(key, value);
        if (++size_ * 4 > buckets_.size() * 3) resize(buckets_.size() * 2);  // 적재율 0.75
    }

    const V* get(const K& key) const {
        for (const auto& kv : buckets_[index(key, buckets_.size())])
            if (kv.first == key) return &kv.second;
        return nullptr;
    }

    std::size_t size() const { return size_; }
};

int main() {
    HashMap<std::string, int> ages;
    ages.put("ada", 36);
    ages.put("ada", 37);
    ages.put("alan", 41);
    std::cout << *ages.get("ada") << ' ' << ages.size() << ' ' << (ages.get("bob") == nullptr) << '\n';  // 37 2 1
}

get 은 없는 키에 널 포인터를 돌려주고, 적재율 검사 size * 4 > capacity * 3 은 정수 연산으로 끝냅니다. remove 는 같은 방식으로 훑은 뒤 erase 하면 됩니다.

Java로 옮긴 해시 맵 핵심

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class ChainedHashMap<K, V> {
    private record Entry<K, V>(K key, V value) {}

    private List<LinkedList<Entry<K, V>>> buckets = newBuckets(8);
    private int size = 0;

    private static <K, V> List<LinkedList<Entry<K, V>>> newBuckets(int n) {
        List<LinkedList<Entry<K, V>>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) list.add(new LinkedList<>());
        return list;
    }

    private LinkedList<Entry<K, V>> bucket(K key) {
        return buckets.get(Math.floorMod(Objects.hashCode(key), buckets.size()));
    }

    public void put(K key, V value) {
        var bucket = bucket(key);
        for (var it = bucket.listIterator(); it.hasNext(); ) {
            if (Objects.equals(it.next().key(), key)) { it.set(new Entry<>(key, value)); return; }
        }
        bucket.add(new Entry<>(key, value));
        if (++size * 4 > buckets.size() * 3) resize(buckets.size() * 2);
    }

    public V get(K key) {
        for (var e : bucket(key)) if (Objects.equals(e.key(), key)) return e.value();
        return null;
    }

    private void resize(int capacity) {
        var old = buckets;
        buckets = newBuckets(capacity);
        for (var b : old) for (var e : b) bucket(e.key()).add(e);
    }

    public int size() { return size; }

    public static void main(String[] args) {
        var m = new ChainedHashMap<String, Integer>();
        for (var w : "to be or not to be".split(" ")) m.put(w, m.get(w) == null ? 1 : m.get(w) + 1);
        System.out.println(m.get("be") + " " + m.size());  // 2 4
    }
}

Math.floorMod 가 중요합니다. hashCode() 는 음수일 수 있고, 그때 Java의 % 는 음수 인덱스를 만듭니다.

TypeScript로 옮긴 해시 맵 핵심

class ChainedHashMap<V> {
  private buckets: [string, V][][] = Array.from({ length: 8 }, () => []);
  private count = 0;

  private hash(key: string): number {
    let h = 2166136261; // FNV-1a, 32비트
    for (let i = 0; i < key.length; i++) {
      h ^= key.charCodeAt(i);
      h = Math.imul(h, 16777619);
    }
    return h >>> 0; // 부호 없는 정수로
  }

  private bucket(key: string): [string, V][] {
    return this.buckets[this.hash(key) % this.buckets.length];
  }

  put(key: string, value: V): void {
    const bucket = this.bucket(key);
    const entry = bucket.find(([k]) => k === key);
    if (entry) { entry[1] = value; return; }
    bucket.push([key, value]);
    if (++this.count > this.buckets.length * 0.75) this.resize(this.buckets.length * 2);
  }

  get(key: string): V | undefined {
    return this.bucket(key).find(([k]) => k === key)?.[1];
  }

  private resize(capacity: number): void {
    const old = this.buckets;
    this.buckets = Array.from({ length: capacity }, () => []);
    for (const bucket of old) for (const [k, v] of bucket) this.bucket(k).push([k, v]);
  }

  get size(): number { return this.count; }
}

const m = new ChainedHashMap<number>();
for (const w of "a b a c b a".split(" ")) m.put(w, (m.get(w) ?? 0) + 1);
console.log(m.get("a"), m.size); // 3 3

JavaScript에는 임의의 값에 대한 해시 함수가 공개되어 있지 않으므로, 이 버전은 문자열 키만 받고 FNV-1a로 해시합니다. Math.imul 은 곱셈을 32비트 안에서 하고, >>> 0 은 결과를 부호 없는 수로 바꿉니다.

정리

스택은 동적 배열을 얇게 감싼 것이고, 큐는 원형 버퍼로 양 끝 연산을 O(1)로 만들며, 해시 맵은 짧은 사슬의 배열로서 적재율이 기준을 넘으면 두 배로 늘어납니다. 네 언어의 구현은 같은 세 단계를 따릅니다. 키를 해시하고, 버킷 번호로 줄이고, 사슬 하나를 훑습니다.