해시맵 (HashMap)
한마디 요약: 키(Key)를 주면 값(Value)을 즉시 꺼내주는 “번호표 달린 사물함”. AI Agent 개발에서는 캐시, 세션 저장, 툴 레지스트리의 기본 뼈대다.
1. 해시맵이 뭔가
HashMap(해시맵, Key-Value 저장소): “키 하나에 값 하나”를 짝지어 저장하는 자료구조. Python에서는 dict, JavaScript에서는 Object/Map, Java에서는 HashMap이라고 부른다. 이름이 달라도 속은 거의 같다.
일상 비유: 학교 사물함을 떠올려보자. 사물함 번호(키)만 알면 그 안의 책(값)을 바로 꺼낼 수 있다. 1번부터 1000번까지 전부 열어볼 필요가 없다. 해시맵이 빠른 이유가 바로 이거다.
포함 관계: 해시맵은 “연관 배열(Associative Array)“이라는 더 큰 개념의 한 구현체. 연관 배열을 구현하는 방법은 여러 개인데(해시맵, 트리맵 등), 그중 해시 함수를 쓰는 버전이 해시맵이다. 다른 구현으로는 트리 기반의 TreeMap이 있다.
2. 리스트·배열과 어떻게 다른가
| 관점 | List(리스트) | HashMap(해시맵) |
|---|---|---|
| 무엇으로 찾나 | 위치 번호(index, 0부터 시작하는 순서) | 키(Key, 임의의 문자열·숫자) |
| 찾는 속도 | O(n) (값으로 찾을 때 앞에서부터 훑음) | O(1) (평균적으로 한 방에) |
| 순서 보장 | 순서대로 저장 | 순서 없음(Python 3.7+는 삽입 순서 유지) |
| 중복 키 | 중복 허용 | 같은 키는 덮어씀 |
| 예시 접근 | arr[3] | d["user_id"] |
| 용도 | 순서 있는 데이터 | 이름표로 찾는 데이터 |
리스트는 “3번째 학생 누구야?”에 강하고, 해시맵은 “김철수라는 학생 정보 뭐야?”에 강하다.
3. 안에서 뭐가 일어나는가 (단계 분해)
Python 코드 d["apple"] = 100 한 줄이 실행되는 흐름:
1단계: 해시 함수(Hash Function, 문자열을 숫자로 바꿔주는 계산기) 가 "apple"을 받아 거대한 숫자로 변환. 예: hash("apple") → 8327493021.
2단계: 그 숫자를 저장소 크기로 나눈 나머지(mod) 를 구해 실제 저장 위치(버킷 번호)를 결정. 저장소 크기가 8이면 8327493021 % 8 = 5. 즉 5번 칸.
3단계: 5번 칸에 ("apple", 100) 을 넣는다.
꺼낼 때(d["apple"])도 똑같이 5번 칸으로 바로 점프. 중간 칸들을 뒤지지 않는다. 이게 O(1)의 정체.
4. 충돌(Collision)이라는 현실
문제: 서로 다른 키가 우연히 같은 칸(버킷)으로 배정되는 상황. 예: hash("apple") % 8 == 5이고 hash("grape") % 8 == 5.
해결 방식 두 가지:
- Chaining(체이닝, 한 칸에 연결 리스트 달기): 5번 칸 안에 여러 항목을 줄줄이 매다는 방식. Python dict이 쓰는 방식의 변형.
- Open Addressing(개방 주소법, 다음 빈 칸으로 밀어넣기): 5번이 찼으면 6번, 7번 순으로 빈 자리를 찾아 넣음.
충돌이 많아지면 O(1)이 무너져 최악의 경우 O(n)까지 느려진다. 그래서 저장소가 꽉 차면 자동으로 크기를 두 배로 늘리는 Rehashing(리해싱, 더 큰 집으로 이사) 이 일어난다.
자세한 성능 분석은 시간복잡도_기초 참고.
5. Python에서 직접 확인
# 생성
cache = {}
# 저장 (O(1))
cache["user:42"] = {"name": "철수", "tokens_used": 1500}
cache["user:77"] = {"name": "영희", "tokens_used": 800}
# 조회 (O(1))
print(cache["user:42"]) # {'name': '철수', 'tokens_used': 1500}
# 존재 여부 확인 (O(1))
print("user:42" in cache) # True
# 삭제 (O(1))
del cache["user:77"]
# 안전한 조회 (키가 없어도 에러 안 남)
print(cache.get("user:999", "없는 유저")) # '없는 유저'터미널에서 바로 실행해보면 cache[키] 접근이 데이터가 100만 개여도 체감상 즉시 끝나는 걸 볼 수 있다.
6. AI Agent 개발에서 어디에 쓰이나
LLM 응답 캐시: 같은 프롬프트에 같은 답변을 내놓을 때, {프롬프트_해시: 응답} 으로 저장해두면 두 번째 호출부터 API 비용이 0원. Anthropic의 Prompt Caching도 개념적으로는 같은 원리.
툴 레지스트리(Tool Registry): Agent가 쓸 수 있는 도구 목록을 {"web_search": search_func, "calculator": calc_func} 식으로 보관. LLM이 "tool_name": "web_search"를 뱉으면 그 키로 즉시 함수를 찾아 실행.
세션 상태 저장: {session_id: 대화_기록} 구조로 여러 유저의 대화 맥락을 병렬 관리. Redis가 이걸 서버 규모로 확장한 것.
Embedding 메모리: 벡터 DB에 넣기 전 단계에서 {doc_id: embedding_vector} 매핑에 해시맵이 깔려 있다.
7. 왜 이렇게 만들었나 (설계 의도)
대안 1: 리스트로 다 해결하기 → 값 하나 찾을 때마다 전체를 훑어야 함. 1000만 개면 평균 500만 번 비교.
대안 2: 정렬된 트리 쓰기 → O(log n)으로 빠르긴 하지만 해시맵의 O(1)보다 느림. 대신 “키 순서대로 순회”가 필요하면 트리가 유리.
해시맵의 트레이드오프:
- 장점: 조회·삽입·삭제 모두 평균 O(1)
- 단점: 순서가 없음, 메모리를 좀 더 먹음(빈 버킷 포함), 해시 충돌 시 최악 O(n)
- 키는 불변(immutable) 이어야 함. 리스트를 키로 못 쓰는 이유.
8. 관련 문서
- 시간복잡도_기초: O(1), O(n) 같은 표기 해석법
- 트리: 순서가 필요할 때 대안 자료구조
- 큐: 다른 자주 쓰는 자료구조
- 직렬화_JSON_YAML: 해시맵을 파일로 저장할 때 쓰는 포맷