1. 해싱 (Hashing) 이란?
ㅇ 해싱 탐색 (Hashing Search)
- 통상적인 반복 비교를 통하지 않고,
- 특정 계산 만으로 바로 자료 저장 주소를 알아내는 탐색 방법
ㅇ 해싱 탐색이 아닌 암호학적 응용으로는, ☞ 해시 알고리즘 참조
2. 해싱 탐색 특징
ㅇ 주로, 빨리 자료를 삽입,저장,가져올 때에 유용
- 주어진 키 값을 갖는 레코드를 반복적인 비교를 통해 찾는 것이 아니라,
- 해시함수로 산출한 주소로 저장위치에 곧바로 접근하는 점이 다름
ㅇ 따라서, 모든 원소에 대한 접근이 동일 시간 내에 이루어짐
ㅇ 검색 효율은 낮음
3. 저장 및 검색
ㅇ 해쉬 표(Hash Table)라는 기억 공간이 필요함
- 해시 표는, 고정된 크기의 자료구조로써, 처음에 그 크기가 정해짐
ㅇ 키를 값에 매핑할 수 있는 구조
- 주어진 키(Key)로 산출된 해쉬값으로, 레코드 저장 주소의 결정 및 저장을 함
- 같은 방법으로 필요한 레코드의 주소를 산출함으로써, 바로 검색 작업 수행
ㅇ 해쉬 함수라는 특정 규칙에 의해 해쉬값을 산출
4. 해싱 관련 용어들
ㅇ 해쉬 함수 (Hash Function)
- 임의 길이의 메세지를 일정 고정 길이의 해쉬 값으로 변환시켜주는 단방향성 함수
ㅇ 해쉬 값 (Hash Value)
- 단방향성 해쉬 함수의 출력 값
. `Fingerprint`,`메세지 다이제스트(Message Digest)` 이라고도 함
ㅇ 해쉬/해쉬값 충돌 (Hash Collision)
- 2개의 다른 메세지가 같은 해시값(해시함수 수행 결과)을 갖는 경우
- 해싱 탐색에서, 해쉬값 충돌 방지 방법
. 해결 방법 중 하나로는, 이미 할당된 해쉬값 위치 다음의 빈 위치에 할당하는 등
ㅇ 해쉬 내성 (Hash Collision Resistance)
- 해시 충돌을 발견해내는 것이 어려운 성질
. 약한 충돌 내성
.. 주어진 해시값을 갖는 다른 메시지를 발견해내기 어려운 성질
. 강한 충돌 내성
.. 동일 해시값을 갖는 다른 2개 메시지를 발견해내기 어려운 성질
ㅇ 해싱표/해쉬표 (Hash Table)
- 해싱에 이용되는, 일정 크기의 자료구조(기억공간)
. 고정된 크기의 자료구조로써, 처음에 그 크기가 정해짐
- 키(Key) 값(Value) 쌍을 기반으로 저장되고, 탐색되어 짐
. 키와 값이 하나의 쌍을 이루며 데이터가 저장되고 검색되어짐
- 주로, 배열을 활용하여 구현됨
- 키를 값에 매핑할 수 있는 자료구조
- 연관배열 추상자료형(ADT)을 구현할 수 있는 자료구조