해시테이블(Hash Table)

2025년 12월 29일

해시테이블

key, value 쌍으로 데이터를 저장하는 자료구조
해시 함수를 통해 데이터를 저장할 위치(인덱스)를 추출해 저장함
Swift의 Dictionary, Set이 해당됨
- Dictionary는 key를 통해 해시값을 추출하기 때문에, key만 Hashable 해도 됨
- Set은 element를 통해 해시값을 추출하기 때문에, element 자체가 Hashable 해야 됨
장점
- 빠른 속도 : 평균 시간 복잡도 O(1)
- key만 알면 해시 함수를 통해 데이터 저장 위치를 알 수 있음
- 인덱스를 모른다면, 배열보다 빠른 탐색 가능
약점
- 충돌 : 서로 다른 key임에도 해시 함수가 우연히 같은 주소를 반환하는 경우 발생
- 해결 방법
  - 체이닝 : 해당 인덱스에 연결리스트로 구성하여 저장하는 방식
  - 개방 주소법 : 충돌 발생 시 다른 빈 공간을 찾아 저장하는 방식
    - 다음 칸을 확인하는 대표적인 방법 : 선형 탐색
    - 선형탐색 : 한칸씩 이동하며 순차적으로 탐색하는 방법

체이닝(Chaining) : index에 연결리스트로 데이터를 연결하여 저장하는 방식
- 장점 : 데이터가 많아져도 성능저하가 덜함
- 단점 : 추가 메모리가 필요하고, 연결리스트라서 캐시 효율이 나쁨
개방 주소법(선형탐색) : 다음 비어있는 index를 찾아 저장하는 방식
- 장점 : 캐시 효율이 좋고, 메모리 할당 오버헤드가 없음
- 단점 : 데이터가 찰수록 급격하게 느려지고, 삭제 로직이 복잡함

Swift는 내부적으로 개방주소법과 선형탐색을 통해 해시 충돌을 해결합니다.

메모리 할당 오버헤드 : 연결 리스트는 각 데이터마다 Node 객체를 생성(malloc)하고 Reference Counting을 해야 하는 비용이 큽니다.
메모리 구조의 차이 : 연결 리스트는 데이터가 메모리에 비연속적으로 흩어져 있지만, 배열은 연속적으로 저장됩니다.

현대 CPU는 RAM에서 데이터를 가져올 때, 요청한 데이터뿐만 아니라 인접한 64바이트(캐시 라인)를 한 번에 가져옵니다.
Swift는 배열(연속 메모리)을 사용하므로, 하나의 데이터를 읽을 때 인접한 데이터들도 이미 캐시에 들어와 있을 확률(Cache Hit)이 매우 높아 탐색 속도가 빠릅니다.