배열(Array)에서 원하는 데이터를 찾으려면 처음부터 끝까지 뒤져야 해서 $O(N)$의 시간이 걸립니다. 데이터가 10억 개라면 끔찍하죠. 그런데 우리가 도서관에서 책을 찾을 때는 100만 권이 있어도 '청구 기호'만 알면 곧바로 해당 서가로 직행합니다. 프로그래밍 세계에도 이처럼 "검색할 내용(Key)만 알면 저장된 위치(Address)를 즉시 알려주는" 마법 같은 자료구조가 있습니다. 바로 해시 테이블(Hash Table)입니다. 파이썬의 딕셔너리(Dictionary), 자바의 맵(HashMap)이 바로 이것인데요, 오늘은 그 초고속 검색의 비밀을 파헤쳐 봅니다.
1. 해시 테이블의 핵심: Key-Value 쌍
해시 테이블은 데이터를 저장할 때 단순한 값이 아니라 키(Key)와 값(Value)을 한 쌍으로 묶어서 저장합니다.
- Key (이름표): 데이터를 찾기 위한 고유한 식별자입니다. (예: "apple", "회원ID")
- Value (내용물): 실제 저장하려는 데이터입니다. (예: "사과", "회원정보")
배열은 인덱스(숫자 0, 1, 2...)로만 접근해야 하지만, 해시 테이블은 우리가 이해하기 쉬운 문자열이나 객체를 키로 사용할 수 있어 직관적입니다.
2. 마법의 번역기: 해시 함수 (Hash Function)
어떻게 문자열인 "apple"을 넣었는데 메모리 주소를 바로 알 수 있을까요? 중간에 해시 함수라는 번역기가 있기 때문입니다.
Input: "apple" ---> [해시 함수] ---> Output: 3 (메모리 3번 방)
Input: "banana" ---> [해시 함수] ---> Output: 10 (메모리 10번 방)
해시 함수는 임의의 데이터를 받아서 고정된 길이의 숫자(해시값)로 바꿔줍니다. 우리는 이 숫자를 인덱스로 삼아 배열(버킷)에 데이터를 저장합니다. 나중에 "apple"을 찾을 때도 다시 해시 함수에 넣으면 똑같이 '3'이 나오므로, 루프를 돌릴 필요 없이 단 한 번(O(1))만에 데이터를 찾을 수 있습니다.
3. 해시 충돌(Collision): 겹치면 어떡하지?
하지만 완벽해 보이는 이 방식에도 약점이 있습니다. 만약 "melon"을 넣었는데 해시 함수가 우연히 "apple"과 같은 '3'을 내뱉으면 어떻게 될까요? 이를 해시 충돌이라고 합니다. 방은 하나인데 손님이 두 명이 온 셈이죠.
3-1. 해결책
- 체이닝 (Chaining): 3번 방에 연결 리스트(Linked List)를 달아서 데이터를 줄줄이 엮어 놓습니다. 충돌이 나면 뒤에 계속 매답니다. 구현이 쉽지만 데이터가 몰리면 느려집니다.
- 개방 주소법 (Open Addressing): 3번 방이 찼으면 옆방(4번)을 봅니다. 비었으면 거기에 넣습니다. "빈방 찾기" 방식입니다. 메모리를 효율적으로 쓰지만 데이터 삭제가 까다롭습니다.
4. 해시 테이블은 언제 쓸까?
해시 테이블은 속도가 생명인 곳에 무조건 쓰입니다.
- 데이터베이스 인덱싱: 수많은 데이터 중 특정 ID를 가진 회원을 0.001초 만에 찾을 때.
- 캐시(Cache) 시스템: 한 번 계산한 복잡한 결과를 저장해두고, 다음에 똑같은 요청이 오면 계산 없이 바로 꺼내 줄 때.
- 중복 제거: 배열에 있는 데이터 중 중복을 없애고 싶을 때, 해시 테이블에 다 넣으면 키의 유일성 때문에 자동으로 중복이 사라집니다.
1. 해시 테이블은 Key를 통해 Value에 O(1) 속도로 즉시 접근하는 초고속 자료구조입니다.
2. 해시 함수가 Key를 메모리 주소로 변환해주며, 주소가 겹치는 충돌(Collision)을 잘 처리해야 합니다.
3. 검색 엔진, 캐싱, 블록체인 등 빠른 데이터 조회가 필요한 현대 기술의 필수 요소입니다.