해시 테이블은 데이터를 빠르게 찾는 마법 같은 구조가 아니다

About this offer

해시 테이블을 처음 배우면 키와 값을 한 쌍으로 저장하고, 키를 사용해 데이터를 빠르게 찾는 자료구조라고 설명한다. const productsById = new Map<string, Product>(); productsById.set("product-101", { id: "product-101", name: "Wireless Keyboard", price: 89 }); const product = productsById.get("product-101"); 배열에서 상품을 하나씩 확인하는 대신 상품 ID로 바로 조회할 수 있다. 해시 테이블의 평균 조회 시간은 O(1) 이므로 빠르다는 설명도 입문 단계에서는 충분히 유용하다. 하지만 쇼핑몰의 장바구니 가격을 계산한다고 생각해보자. 상품을 한 번만 찾는다면 배열을 순회해도 큰 문제가 없다. 반면 장바구니의 모든 항목에 대해 상품 이름, 현재 가격과 판매 상태를 반복해서 찾아야 한다면 같은 배열을 여러 번 탐색하게 된다. 이때 해시 테이블을 선택해야 하는 이유는 O(1) 이라는 기호 자체가 아니라, 조회할 데이터를 미리 정리해 반복 탐색을 없앨 수 있기 때문이다. 상품이 몇 개나 있는가? 조회는 몇 번 발생하는가? 키로 사용할 값은 안정적인가? 빠른 조회를 위해 추가 메모리를 사용해도 되는가? 실제 서비스에서 해시 테이블을 사용한다는 것은 데이터를 미리 키 중심으로 정리하고, 추가 메모리를 사용하는 대신 반복되는 검색 비용을 줄이겠다는 판단이다. 장바구니가 커질수록 같은 상품 목록을 반복해서 읽게 된다 크리스의 장바구니에는 여러 상품이 들어 있고, 서버는 현재 상품 정보와 수량을 결합해 결제 금액을 계산해야 한다. type CartItem = { productId: string; quantity: number; }; type Product = { id: string; name: string; price: number; isAvailable: boolean; }; 처음에는 각 장바구니 항목마다 find() 로 상품을 찾아도 된다. function calculateTotal( cartItems: CartItem[], products: Product[] ) { return cartItems.reduce((total, item) => { const product = products.find( product => product.id === item.productId ); if (!product || !product.isAvailable) { return total; } return total + product.price * item.quantity; }, 0); } 장바구니 항목이 c 개이고 상품이 p 개라면, 최악의 경우 상품 비교가 c × p 번 발생한다. 장바구니에 상품이 3개이고 조회 대상도 20개라면 신경 쓸 필요가 없다. 그러나 주문 수백 건을 한 번에 처리하거나 같은 상품 목록으로 가격, 재고, 배송 가능 여부를 차례로 검사한다면 탐색이 계속 반복된다. 여기서 문제는 배열이 느리다는 데 있지 않다. 이미 확인한 상품 목록을 다음 조회에서도 처음부터 다시 읽는 구조에 있다. 한 번 정리한 조회 구조를 반복해서 사용한다 상품 목록을 ID 기준의 Map 으로 변환하면 각 장바구니 항목이 필요한 상품을 직접 조회할 수 있다. function calculateTotal( cartItems: CartItem[], products: Product[] ) { const productsById = new Map( products.map(product => [product.id, product]) ); return cartItems.reduce((total, item) => { const product = productsById.get(item.productId); if (!product || !product.isAvailable) { return total; } return total + product.price * item.quantity; }, 0); } 처음 Map 을 만드는 데는 상품 수만큼 순회해야 하므로 O(p) 가 필요하다. 이후 장바구니 항목의 조회는 평균적으로 한 번씩 처리되므로 전체 비용은 O(p + c) 가 된다. 대신 같은 상품 데이터를 배열과 Map 에서 함께 참조하기 위한 메모리가 추가된다. 조회 구조를 만드는 시간도 공짜가 아니다. 상품 하나만 한 번 찾고 끝난다면 Map 을 만드는 것보다 find() 가 더 단순하고 충분히 빠를 수 있다. 내가 일반적인 서비스 코드에서 해시 테이블을 선택하는 기준도 여기에 있다. 데이터가 많다는 이유만으로 먼저 만들지 않는다. 동일한 데이터에서 키 기반 조회가 반복되고, 구조를 준비하는 비용보다 제거할 탐색 비용이 클 때 사용한다. 빠른 조회는 안정적인 키에서 시작한다 해시 테이블은 키를 받아 내부 저장 위치를 결정한다. 이때 서로 다른 키가 같은 위치를 가리키는 충돌이 발생할 수 있고, 자료구조는 이를 별도로 처리해야 한다. 그래서 조회는 항상 한 단계 만에 끝난다고 보장되지 않으며 일반적으로 평균 O(1) 이라고 표현한다. 애플리케이션 코드에서 직접 충돌 처리 알고리즘을 구현할 일은 많지 않다. Map 과 같은 표준 자료구조가 그 책임을 맡는다. 개발자가 더 자주 판단해야 하는 문제는 어떤 값을 키로 사용할지다. 다음 코드는 상품명을 키로 사용한다. const productsByName = new Map( products.map(product => [product.name, product]) ); 상품명은 중복될 수 있고 운영자가 변경할 수도 있다. 같은 이름을 가진 상품이 들어오면 이전 값이 덮어써질 수 있다. 장바구니가 저장된 뒤 상품명이 바뀌면 기존 항목을 찾지 못하는 문제도 생긴다. 상품 조회에는 이름보다 변경되지 않는 상품 ID를 사용하는 편이 안전하다. const productsById = new Map( products.map(product => [product.id, product]) ); 현실의 상품은 이름, 가격, 이미지처럼 여러 속성을 가진다. 그중 상품 ID가 코드의 입력에서 조회 키가 되고, Map 에는 상품의 현재 상태가 저장되며, 조회 결과는 가격 계산과 판매 가능 여부 검증에 사용된다. 빠른 검색보다 먼저 필요한 것은 현실의 대상을 안정적으로 식별하는 키다. 조회 구조와 원본 데이터의 책임을 구분한다 productsById 를 만들었다고 해서 이 Map 이 상품 가격의 원본이 되는 것은 아니다. 이 구조는 데이터베이스나 상품 서비스에서 읽은 정보를 현재 계산에서 빠르게 사용하기 위한 조회용 표현이다. 특히 결제 요청에서 클라이언트가 다음과 같이 가격을 보내더라도 그대로 사용해서는 안 된다. { "productId": "product-101", "quantity": 2, "price": 10 } 사용자가 화면에서 본 가격은 오래된 값일 수 있고 직접 변경된 값일 수도 있다. 서버는 productId 와 quantity 를 입력으로 받은 뒤 신뢰할 수 있는 상품 데이터에서 현재 가격을 조회해야 한다. 이 과정에서 만든 Map 은 계산을 돕지만 가격의 Source of Truth를 대신하지 않는다. const cartItems = validateCartItems(request.body); const products = await productRepository.findByIds( cartItems.map(item => item.productId) ); const productsById = new Map( products.map(product => [product.id, product]) ); 또한 상품마다 데이터베이스를 한 번씩 호출한 뒤 결과를 Map 에 넣는다면 메모리 조회만 빨라졌을 뿐 전체 처리 시간은 여전히 느릴 수 있다. 필요한 상품을 한 번에 가져오고, 그 결과를 현재 작업에서 반복 조회할 때 Map 의 장점이 분명해진다. 해시 테이블을 사용하기 전에 확인할 질문 같은 데이터에서 키 기반 조회가 반복되는가? 배열을 순회하는 비용이 실제 데이터 규모에서 문제가 되는가? 조회 구조를 만드는 시간과 추가 메모리를 감당할 가치가 있는가? 키는 중복되지 않으며 시간이 지나도 안정적으로 유지되는가? 동일한 키가 두 번 들어왔을 때 덮어쓰기를 허용할 것인가? Map 에 담긴 값은 원본인가, 현재 작업을 위한 조회용 데이터인가? 데이터베이스 요청부터 계산까지 전체 흐름을 줄였는가, 메모리 안의 조회만 개선했는가? 반복되는 탐색이 있을 때 메모리와 시간을 교환한다 해시 테이블은 데이터를 넣는 순간 모든 조회를 빠르게 만들어주는 장치가 아니다. 먼저 데이터를 키 기준으로 정리해야 하고, 이를 유지할 메모리가 필요하며, 충돌과 데이터 중복도 자료구조 내부에서 처리해야 한다. 쇼핑몰의 장바구니처럼 같은 상품 집합에서 ID 조회를 반복한다면 Map 을 한 번 만들어 재사용하는 선택이 잘 맞는다. 반대로 데이터가 작고 조회가 한 번뿐이라면 배열의 find() 가 더 읽기 쉽고 충분히 안전하다. 결국 판단 기준은 자료구조의 이름이 아니라 조회 횟수다. 반복 탐색이 실제 비용이 되는 순간, 해시 테이블은 추가 메모리를 사용해 그 비용을 한 번의 사전 처리로 바꾸는 방법이 된다. 다음 글에서는 스택이 최근 상태를 되돌리는 흐름을 어떻게 표현하는지 살펴본다.