해시 테이블

키(Key)를 해시 함수(Hash Function)에 입력해 얻은 값(Hash)을 주소로 사용하여 데이터를 즉시 찾아내는 자료구조다.
배열의 빠른 접근 속도와 연결 리스트의 유연한 삽입/삭제 장점을 결합하여, 평균적으로 O(1)이라는 경이로운 시간 복잡도를 가진다.
서로 다른 키가 같은 주소를 할당받는 ‘충돌’ 현상이 발생할 수 있으며, 이를 해결하기 위한 체이닝, 개방 주소법 등 다양한 전략이 존재한다.
메모리 공간을 조금 더 사용하는 대신, 시간적인 효율성을 극대화하는 대표적인 ‘공간-시간 트레이드 오프(Space-Time Tradeoff)’ 사례

해시 함수는 임의의 길이를 가진 키를 입력받아, 고정된 길이의 값, 즉 해시(Hash) 또는 **해시 값(Hash Value)**을 만들어내는 함수.
이 해시 값을 배열의 ‘인덱스’로 사용하는 것이 해시 테이블의 핵심 아이디어입니다.
서로 다른 키를 해시 함수에 넣었더니 우연히 같은 해시 값(인덱스)이 나오는 경우 → 충돌
버킷(Bucket): 해시 테이블을 구성하는 내부 배열의 각 칸을 의미. 해시 함수가 계산한 해시 값이 바로 이 버킷의 인덱스가 됩니다.
슬롯(Slot): 하나의 버킷에 저장되는 실제 데이터(Key-Value 쌍)를 의미합니다.
키의 개수가 버킷의 개수보다 많아지면 충돌은 비둘기집 원리에 의해 필연적으로 발생

충돌 해결 전략	장점	단점
분리 연결법	구현 용이, 데이터 수 제한 없음	추가 메모리 사용, 최악의 경우 O(n)
개방 주소법	추가 메모리 없음, 캐시 효율 좋음	군집화 문제, 테이블 크기에 민감, 삭제 복잡

시스매