> For the complete documentation index, see [llms.txt](https://byulseop-til.gitbook.io/sinheeseop_til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://byulseop-til.gitbook.io/sinheeseop_til/cs-computer-science/datastructure/03_structure/hashtable.md). # HashTable > **"Key를 숫자로 바꿔서, 배열 인덱스로 바로 접근하는 설계"** ## 이 문서의 위치 이 문서는 **03\_Structure 폴더**에 있다. 즉, **Hash Table은 3단계 "자료구조(논리적 설계)"** 에 해당한다. | 단계 | 명칭 | 역할 | 이 문서에서 | | ---------------- | ---------------- | ------------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------- | | **1\~2단계 (ADT)** | Map, Set | "Key로 Value를 찾아라" - 기능 명세 | [Map](/sinheeseop_til/cs-computer-science/datastructure/02_adt/map.md), [Set](/sinheeseop_til/cs-computer-science/datastructure/02_adt/set.md) | | **3단계 (자료구조)** | **Hash Table** | "어떻게 저장할까?" - 논리적 설계 | **← 이 문서** | | **4단계 (구현체)** | HashMap, HashSet | 실제 코드로 구현한 클래스 | [Java\_HashMap](/sinheeseop_til/cs-computer-science/datastructure/04_implementation/java_hashmap.md) | ## Hash Table 이란? **해시 테이블(Hash Table)** 은 [**해시(Hash)**](/sinheeseop_til/cs-computer-science/algorithm/hash/hash.md)**라는 변환 규칙을 써서 Key를 '숫자 인덱스'로 바꾼 뒤, 그 위치(배열의 칸)에 Value를 저장하는 자료구조** 다.\ 여기서 '테이블'은 실제론 **배열(Array)** 이고, Key가 곧 '배열의 주소' 역할을 하게 만드는 게 핵심이다. ``` Key("apple") → Hash Function → 42 → table[42] = Value ``` * **핵심 원리:** `Index = HashFunction(Key) % ArraySize` * **목표:** 검색, 삽입, 삭제를 평균 **O(1)** 에 수행. * **물리적 기반:** 내부는 **배열(Array)** 이다. ## 언제 해시 테이블을 선택하는가? (2단계 가치 판단의 결과) > **"이 섹션은 해시 테이블이 2단계라는 뜻이 아니다."**\ > 2단계 가치 판단에서 **"ADT(1단계 기능)에 어떤 제약조건을 더하면 해시 테이블(3단계)을 선택하게 되는가?"** 를 설명하는 것이다. ### 예시: Map ADT를 구현한다고 하자 **1단계 (ADT 기능 정의):**\ "Key로 Value를 저장하고 찾고 싶어." → [Map ADT](/sinheeseop_til/cs-computer-science/datastructure/02_adt/map.md) **2단계 (가치 판단 - 제약조건 추가):**\ "근데 **엄청 빨리** 찾아야 해. O(1)이면 좋겠어." | 방식 | 검색 속도 | 한계 | | -------------- | -------- | ------------------------- | | **배열(인덱스)** | O(1) | "apple"이라는 문자열로는 인덱스를 모른다 | | **리스트(순차 탐색)** | O(n) | 100만 개 다 뒤져야 한다 | | **트리(이진 탐색)** | O(log n) | 괜찮지만 더 빠르면 좋겠다 | | **해시 테이블** | **O(1)** | Key를 숫자로 바꾸면 된다! | **결론:** "Key를 숫자(인덱스)로 바꿔버리자!" → **해시 테이블(3단계 자료구조)** 선택. ### 해시 테이블로 구현되는 ADT들 | ADT | 해시 테이블 기반 구현체 | 핵심 기능 | | -------------------------------------------------------------------------- | ----------------- | -------------------- | | [**Map**](/sinheeseop_til/cs-computer-science/datastructure/02_adt/map.md) | `HashMap`, `dict` | Key로 Value를 O(1)에 찾기 | | [**Set**](/sinheeseop_til/cs-computer-science/datastructure/02_adt/set.md) | `HashSet` | 중복 검사를 O(1)에 하기 | | **Cache** | `LRU Cache` | 최근 데이터를 O(1)에 조회 | | **Symbol Table** | 컴파일러 내부 | 변수/함수 이름을 O(1)에 찾기 | ## 3단계 : 설계도를 짠다 (Logical Design) * **질문:** "Key를 어떻게 숫자로 바꿀 것인가?" * **설계:** [**해시 함수(Hash Function)**](/sinheeseop_til/cs-computer-science/algorithm/hash/hash.md) 를 사용하여 Key를 정수로 변환하고, 그 값을 배열의 인덱스로 사용한다. ### 구조 (Anatomy) | 구성 요소 | 역할 | | ------------------------------------------------------------------------------- | ------------------------------ | | **Key (키)** | 데이터를 식별하는 고유 값 (예: "apple") | | [**Hash Function**](/sinheeseop_til/cs-computer-science/algorithm/hash/hash.md) | Key를 정수로 바꾸는 함수 (상세 내용은 링크 참조) | | **Bucket (버킷)** | 배열의 각 칸. 실제 데이터가 저장되는 공간 | | **Value (값)** | Key에 매핑된 실제 데이터 | ### 시간 복잡도 | 연산 | 평균 | 최악 (충돌 심할 때) | | ----------- | ---- | ------------ | | 삽입 (put) | O(1) | O(n) | | 검색 (get) | O(1) | O(n) | | 삭제 (remove) | O(1) | O(n) | ## 3.5단계 : 고오급 설계도 (충돌 해결) > **"서로 다른 Key가 같은 인덱스를 가리키면 어떡하지?"** 이것이 **충돌(Collision)** 이다. 해시 테이블의 숙명적인 문제이며, 해결 방식에 따라 성능과 구현이 갈린다. ### A. 체이닝 (Chaining) - "같은 자리에 줄 세우기" * **규칙:** 충돌 발생 시, 해당 버킷에 **연결 리스트** 를 매달아 데이터를 줄줄이 저장한다. * **장점:** 구현이 단순하고, 삭제가 깔끔하다. * **단점:** 최악의 경우 한 버킷에 모든 데이터가 몰리면 O(n). ### B. 개방 주소법 (Open Addressing) - "빈자리 찾아 떠나기" * **규칙:** 충돌 발생 시, 원래 자리가 아닌 **다른 빈 버킷** 을 찾아 저장한다. * **장점:** 메모리 효율이 좋고, CPU 캐시 적중률이 높아 빠르다. * **단점:** 삭제 시 "Tombstone(묘비)" 관리가 복잡하다. > **상세 내용:** 충돌 해결 알고리즘은 [**Open Addressing**](/sinheeseop_til/cs-computer-science/algorithm/hash/openaddressing.md) 및 [**Hash**](/sinheeseop_til/cs-computer-science/algorithm/hash/hash.md) 문서를 참조. ### 언어별 선택 | 언어 | 충돌 해결 방식 | 이유 (철학) | | ---------- | -------- | ---------------------------- | | **Java** | 체이닝 | 삭제가 빈번해도 안정적. 트리 변환으로 최악 방어. | | **Python** | 개방 주소법 | 메모리 효율, CPU 캐시 적중률 중시. | | **C++** | 개방 주소법 | 위와 동일. | ## 4단계로의 연결 : 구현체들 3단계와 3.5단계에서 설계한 "해시 테이블"을 실제 언어로 구현한 것이 **구현체** 다. | 언어 | 구현체 | 내부 설계 | 비고 | | -------------- | -------------------- | -------------- | -------------------------------------------------------------------------------------------- | | **Java** | `HashMap` | 체이닝 (리스트 → 트리) | [상세 문서](/sinheeseop_til/cs-computer-science/datastructure/04_implementation/java_hashmap.md) | | **Java** | `Hashtable` | 체이닝 | [레거시](/sinheeseop_til/cs-computer-science/datastructure/04_implementation/java_hashtable.md) | | **Python** | `dict` | 개방 주소법 | - | | **C++** | `std::unordered_map` | 개방 주소법 | - | | **JavaScript** | `Map`, `Object` | (엔진마다 다름) | - | ## 관련 문서 * **ADT:** [Map](/sinheeseop_til/cs-computer-science/datastructure/02_adt/map.md), [Set](/sinheeseop_til/cs-computer-science/datastructure/02_adt/set.md) * **해시 알고리즘:** [Hash 알고리즘](/sinheeseop_til/cs-computer-science/algorithm/hash/hash.md) * **개념서:** [자료구조 개념서](/sinheeseop_til/cs-computer-science/datastructure/_.md)