[자료구조] 해시 vs 스택, 언제 어떤 구조 쓸까?

 

 자료구조는 문제 해결의 핵심 도구입니다. 특히 해시와 스택은 많은 개발자들이 실무와 코딩 테스트에서 자주 마주치는 구조이지만, 각각의 쓰임새와 동작 원리를 혼동하는 경우가 많습니다.

 

 이 글에서는 해시(Hash)와 스택(Stack)의 구조적 차이, 주요 특징, 그리고 실전에서 어떤 상황에 어떤 구조를 선택해야 하는지 명확하게 비교하여 정리합니다.

해시(Hash): 빠른 검색의 최적화 도구

해시(Hash)는 키(key)와 값(value)을 한 쌍으로 저장하는 자료구조로, 대부분 해시 테이블(Hash Table)로 구현됩니다. 해시 함수(Hash Function)를 통해 키를 특정 인덱스로 매핑하여, 매우 빠른 검색 속도를 제공합니다. 일반적인 탐색 시간 복잡도가 O(n)인 경우도 많지만, 해시는 평균적으로 O(1)의 검색, 삽입, 삭제 성능을 자랑합니다.

 

 대표적인 언어별 해시 구조는 다음과 같습니다

• Python: dict
• JavaScript: Object, Map
• Java: HashMap
• C++: unordered_map

 

해시의 주요 특징

• 키를 이용해 데이터를 저장하고 검색
• 중복 키를 허용하지 않음
• 내부적으로 배열 기반 구조 + 해시 함수 사용
• 충돌(Collision)을 처리하기 위한 체이닝 또는 오픈 어드레싱 필요

 

사용 예시

• 로그인 시 유저 ID → 유저 정보 매핑
• 단어 빈도수 계산
• 캐시(Cache) 시스템 구현
• 중복 값 탐색 문제 해결

해시는 특히 검색이 잦고 대량의 데이터 속에서도 빠르게 결과를 도출해야 하는 상황에서 최적입니다. 단, 순서가 보장되지 않으며, 해시 함수 설계나 충돌 처리 방식에 따라 성능이 크게 좌우될 수 있습니다.

스택(Stack): 후입선출의 명확한 흐름

 마지막에 넣은 데이터를 가장 먼저 꺼낸다

 스택(Stack)은 LIFO(Last-In, First-Out) 구조로, 가장 마지막에 삽입된 요소가 가장 먼저 삭제되는 방식의 선형 자료구조입니다.

 스택은 삽입(Push)과 삭제(Pop)가 항상 한 쪽(Top)에서 이루어지며, 매우 직관적이고 구조가 단순해 다양한 알고리즘에서 보조적인 용도로 활용됩니다.

 

스택의 주요 특징

• 한쪽에서만 삽입/삭제
• 후입선출 방식으로 작동
• 시간 복잡도: 삽입/삭제 O(1)
• 순차 처리, 상태 기억 등에 유리

사용 예시

• 웹 브라우저의 뒤로 가기 기능 (방문 기록)
• 재귀 호출 시 함수 호출 기록 저장
• 수식 계산(괄호 검사, 후위 표기법 등)
• DFS(깊이 우선 탐색) 알고리즘 구현

스택은 데이터를 쌓고 꺼내는 순서가 중요한 문제에 적합합니다. 예를 들어 함수 호출이 중첩되거나, 어떤 상태를 되돌아가야 할 때 스택을 이용하면 깔끔하고 효과적인 흐름 제어가 가능합니다. 단, 모든 접근이 Top 기준이기 때문에 임의 접근(random access)은 불가능합니다.

해시 vs 스택, 어떤 상황에 어떤 걸 쓸까?

용도와 목적에 따른 구조 선택 가이드

해시와 스택은 구조부터 사용 목적까지 완전히 다릅니다. 따라서 둘을 비교하고 선택할 때는 다음 3가지 기준을 명확히 해야 합니다.

1. 접근 방식
   • 해시: 키를 통해 원하는 값에 직접 접근 → 빠른 검색
   • 스택: 순차적으로 데이터를 쌓고 꺼냄 → 순서 제어
2. 데이터 흐름
   • 해시: 무작위적 접근(random access)
   • 스택: 직선적 흐름(linear flow), 최근 데이터를 우선 처리
3. 문제 유형별 추천
   • 해시 적합한 문제:
     • 주어진 배열에서 중복 숫자 찾기
     • 특정 키에 대응하는 값을 빠르게 찾을 때
     • 문자열 빈도 수 계산
     • 캐시 구현
   • 스택 적합한 문제:
     • 괄호 짝 검사
     • 웹페이지 탐색 히스토리
     • 재귀 처리 및 백트래킹
     • 깊이 우선 탐색(DFS)

요약 비교표

항목	해시(Hash)	스택(Stack)
구조 유형	키-값 기반 테이블	후입선출 리스트
접근 방식	키를 통한 직접 접근	마지막 삽입 요소부터 순차 접근
주요 성능	O(1) 검색/삽입/삭제	O(1) 삽입/삭제
주요 용도	빠른 조회, 매핑	상태 저장, 순서 관리
순서 보장	없음	있음

 

해시와 스택은 각각의 목적과 상황에 따라 선택해야 할 자료구조입니다. 빠른 검색과 매핑이 필요하다면 해시, 순차적 흐름이나 상태 복원이 필요하다면 스택이 더 적합합니다. 코딩 테스트와 실무 모두에서 자료구조의 올바른 선택은 성능과 코드 품질에 결정적인 영향을 줍니다. 지금부터 해시와 스택의 개념을 다시 복습하고, 상황에 맞는 적용을 연습해 보세요.