해시테이블 시각화
체이닝과 오픈 어드레싱으로 해시 충돌을 해결하는 과정을 단계별로 관찰하세요
⚙️ 테이블 설정
충돌 해결 전략
연산
키를 입력하고 삽입 또는 탐색을 눌러 시작하세요.
해시테이블이란?
해시테이블(Hash Table)은 키-값 쌍을 O(1) 평균 시간에 삽입·탐색·삭제할 수 있는 자료구조입니다. 해시 함수로 키를 버킷 인덱스로 변환하고, 충돌(다른 키가 같은 인덱스를 가리킴)을 체이닝 또는 오픈 어드레싱으로 해결합니다. JavaScript의 Object, Map; Python의 dict; Java의 HashMap이 모두 해시테이블 기반입니다.
사용 방법
- 1충돌 해결 전략(체이닝/선형/이차 프로빙)을 선택하세요
- 2테이블 크기를 조절해 충돌 빈도를 바꿔보세요 (작을수록 충돌 많음)
- 3키를 입력하고 삽입을 눌러 해시 계산 → 버킷 배정 과정을 관찰하세요
- 4랜덤 데이터 삽입으로 여러 키를 한 번에 넣어보세요
- 5같은 버킷에 여러 키가 배정될 때 충돌 해결 과정을 비교하세요
동작 원리
- 1키(key)를 해시 함수에 입력하여 해시값(정수) 생성
- 2해시값을 배열 크기로 나머지 연산(mod)하여 인덱스(슬롯) 결정
- 3충돌 해결 — 체이닝: 같은 인덱스에 연결 리스트로 여러 항목 저장. 개방 주소법: 빈 슬롯을 찾을 때까지 탐사(선형, 이차, 이중 해싱)
- 4적재율(load factor)이 높아지면 리해싱(배열 확장 + 재배치)
- 5평균 O(1) 삽입/탐색/삭제
실무 활용
- •JavaScript의 Object/Map, Python의 dict, Java의 HashMap — 모든 현대 언어의 핵심 자료구조
- •데이터베이스의 해시 인덱스(정확 일치 검색 최적화)
- •캐시 시스템(Redis, Memcached)의 키-값 저장
- •블록체인의 해시 체인 및 머클 트리
- •DNS 캐시 — 도메인 이름 → IP 주소 매핑
비슷한 알고리즘
- •BST(이진탐색트리) — 순서 보장(정렬 순회 가능)하나 평균 O(log n). 해시테이블은 O(1)이나 순서 없음
- •트라이(Trie) — 문자열 키에 특화. 접두사 검색이 O(m)(m=키 길이). 자동 완성에 유리
- •블룸 필터(Bloom Filter) — 확률적 해시 구조. '없음'은 확실하지만 '있음'은 오탐 가능. 대규모 중복 검사에 사용
학습 팁
- •적재율(Load Factor) 0.7 이상이면 성능이 급격히 저하됩니다 (리사이징 필요)
- •체이닝은 적재율 > 1도 허용하지만, 오픈 어드레싱은 < 1이어야 합니다
- •선형 프로빙은 구현이 단순하지만 클러스터링(연속 점유) 문제가 있습니다
- •이차 프로빙은 클러스터링을 줄이지만, 테이블 크기가 소수일 때 효과적입니다
- •현실적으로 Java HashMap은 적재율 0.75에서 자동으로 2배 리사이징합니다
자주 묻는 질문
Q. 해시 함수가 나쁘면 어떻게 되나요?
A. 충돌이 많아져 O(1) 평균이 O(n) 최악으로 악화됩니다. 좋은 해시 함수는 키를 버킷에 고르게 분산시킵니다. 암호화용 해시(SHA-256 등)와 자료구조용 해시(MurmurHash 등)는 다른 목적으로 설계됩니다.
Q. 체이닝 vs 오픈 어드레싱, 언제 어떤 것을 쓰나요?
A. 체이닝: 삭제가 많거나 적재율이 높을 때 유리. 각 버킷이 동적 리스트라 메모리 오버헤드 있음. 오픈 어드레싱: 캐시 친화적(연속 메모리), 메모리 효율 높음. 적재율 낮게 유지해야 성능 보장. 일반적으로 Java는 체이닝, Python은 오픈 어드레싱 변형을 사용합니다.
Q. 해시테이블과 트리 맵(BST)의 차이점은?
A. 해시테이블: 평균 O(1) 탐색, 순서 없음. 트리 맵(BST): O(log n) 탐색, 키 순서 유지. 순서가 필요 없고 빠른 탐색이 목적이라면 해시테이블, 범위 쿼리·정렬 순서가 필요하면 트리 맵을 선택합니다.