✅ 구조
- 키에 데이터를 매핑할 수 있는 데이터 구조
- 해쉬 함수를 통해 배열에 키에 대한 데이터를 저장할 수 있는 주소를 계산
- Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로 저장 및 탐색 속도가 획기적으로 빨라짐
✅ 용어
- Key : 검색 시 사용되는 문자열
- Value : Key와 쌍을 이룬 데이터 (Value)
- 해쉬 (Hash), 해쉬값 (Hash value) : 해싱 함수를 통해 리턴된 고정된 길이의 값
- 해쉬 함수 (Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
- 해쉬 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
- 슬롯 (Slot) : 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간
* 초 간단 해쉬 함수 예시 : Division 기법
(나누기를 통해 나머지 값을 사용하여 KEY 주소 계산)✅ 장점
- 데이터 저장/읽기 속도 빠름
- 해쉬는 키에 대한 데이터가 있는지 확인이 쉬움
- 동적인 메모리 크기
- 대량의 정보를 저장하고 특정 요소를 효율적으로 검색 가능
✅ 단점
- 일반적으로 저장공간이 좀 더 많이 필요
- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요
✅ 사용
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인이 쉽기 때문)
- 데이터베이스 (주소, 이름, 번호 찾기)
- 사용자 로그인 인증
✅ 해시충돌
1) Chainging 기법
- 개방 해슁, Open Hashing 기법 중 하나
- 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
- 충돌이 일어나면 링크드 리스트라는 자료구조를 사용해서 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법
2) Liner Probling 기법
- 폐쇄 해슁, Close Hashing 기법 중 하나
- 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
- 충돌이 일어나면 해당 Hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
- 저장공간 활용도를 높이기 위한 기법
✅ 시간 복잡도
- 일반적인 경우 : O(1)
- 최악의 경우 : O(n)
- Linear Probling, Chaining 기법 둘 다 동일
👩💻 IT Engineering