해시 자료구조는 키-값 쌍을 저장하고 검색할 때 효율적인 데이터 구조이다.
키를 이용해 빠르게 값에 접근할 수 있다. 딕셔너리, Map, HashMap과 동일한 개념이다.
해시 자료구조의 주요 개념
1. 해시 함수(Hash Function)
데이터를 고정된 크기의 해시 값(보통 정수)으로 매핑하는 함수.
이 해시 값은 해시 테이블의 인덱스로 사용됨.
이상적인 해시 함수는 입력에 따라 균일하게 분포된 해시 값을 반환하며, 해시 값이 중복되는 경우를 최소화함.
2. 해시 테이블(Hash Table)
키를 해시 함수에 입력해 얻은 해시 값을 배열의 인덱스로 삼아 값을 저장하는 배열.
이렇게 하면 원하는 키를 통해 바로 인덱스로 접근하여 값을 빠르게 검색할 수 있음.
해시 자료구조의 특징
• 빠른 검색: 해시 자료구조는 평균적으로 O(1) 시간 복잡도로 검색, 삽입, 삭제가 가능함. -> 대부분의 경우 상수 시간에 데이터에 접근할 수 있음
• 키-값 쌍의 저장: 해시 자료구조는 고유한 키를 통해 값을 저장하며, 키를 사용하여 값을 조회, 삽입, 삭제할 수 있음
해시의 충돌(Collision)
해시 함수가 서로 다른 키에 대해 동일한 해시 값을 반환하는 경우 충돌이 발생.
충돌을 해결하기 위한 여러 가지 기법:
1. 체이닝(Chaining)
같은 해시 값을 가진 키-값 쌍을 연결 리스트로 저장하는 방식입. 충돌이 발생하면 해당 인덱스에 여러 값을 연결하는 식으로 해결
2. 개방 주소법(Open Addressing)
충돌이 발생하면 다른 빈 공간을 찾아 값을 저장하는 방식. 이 과정에서 선형 탐사, 제곱 탐사, 이중 해싱 등 다양한 방법을 사용
해시 자료구조의 사용 예
• 데이터베이스 인덱싱
• 캐싱 시스템: 예를 들어 웹 브라우저의 캐시
• 집합(Set)과 맵(Map) 구현: 파이썬의 set과 dict는 해시 자료구조를 기반으로 구현
• 빠른 데이터 검색: 검색엔진, 데이터베이스, 라우팅 테이블 등에서 사용
장점과 단점
• 장점: 빠른 데이터 접근 및 관리가 가능하며, 특정 키를 통해 데이터를 효율적으로 저장하고 찾을 수 있음
• 단점: 해시 충돌이 발생하면 성능이 저하될 수 있으며, 저장 공간이 많이 필요할 수도 있음
* 파이썬에서의 Hash
dict, set