[자료구조] 해싱
공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다.
해싱 (Hashing) 이란?
각각의 데이터를 고유한 숫자 값으로 표현하고, 이를 통하여 기억저장소에 저장하거나 검색 작업을 수행하는 방식을 말한다.
- Hash Function을 통하여 Hash Table에 인덱스를 계산한다.
- 다른 방식에 비해 검색속도가 가장 빠르다.
- 삽입, 삭제의 빈도가 많을 때 유리하다.
- Key-Value 변환 방법 사용 : Hash Table은 (Key,Value) 구조로 데이터를 저장함
- 데이터 검색과 저장 뿐만 아니라 데이터 무결성 검사, 암호화에도 활용된다.
데이터 무결성 검사 : 데이터가 손상되거나 변경되지 않았는지 확인하는 과정이다
해시 함수(Hash Function) : 임의의 길이를 가진 데이터를 입력 받아 고정된 해시 값을 출력하는 함수
.
해시 함수(Hash Function)
임의의 길이를 가진 데이터를 입력 받아 고정된 해시 값을 출력하는 함수이다. 해시 함수는 세 가지 큰 특징을 가지고 있다.
(1) 단방향성
해시함수는 임의의 값을 입력받아서 어떤 값을 출력받을지는 알 수 있으나 출력된 값을 함수에 넣어서 입력을 알 수는 없다.
(2) 고정 길이 매핑
길이가 다른 입력값이 입력되더라 고정된 길이로 출력된다.
(3) 충돌 저항성
서로 다른 두 입력값이 동일한 해시 값을 가지는 경우를 찾는 것이 계산적으로 어려워야 한다는 성질이다.
해시 테이블(Hash Table)
데이터가 저장되는 곳으로, 해시 함수를 통해 산출된 해시 값 (Hash Value)을 인덱스로 데이터를 저장한다.
예시에서는 해시 함수를 통해 산출된 해시 값(주소 값)에 따라 해시 테이블에 데이터를 입력해주고 있다.
해시 충돌(Hash Collision)
해시 함수가 서로 다른 Key에 대하여 같은 값을 반환하여 같은 위치에 두 개 이상 데이터가 저장되는 현상
해결 방법에는 크게 두 가지가 있다.
(1) Open Hashing
해시 테이블 저장공간 이외의 공간을 활용하여 해결하는 방식. Chaining이나 Close Addressing 기법이라고도 부른다.
(2) Close Hashing
해시 테이블 공간 안에서 순차적으로 다음 빈 공간에 저장하는 방식. Linear Probing이나 Open Addressing 기법이라고도 부른다.
결국 어떤 점에서 빠르다는건가?
공부만으로는 감이 잘 오지 않아서 예시를 찾아보았다.
menu "pizza" # price :10
해시 테이블을 기반으로 한다면, 여기서 "pizza"가 Key 값, price가 value 값이 된다.
menu Hash Table을 체크해보면 이렇게 구성되어있다.
pizza의 가격을 알기 위해서
즉, pizza의 가격을 알기 위해서 순차적 탐색(Linear)을 할 필요 없이 바로 10이라는 값을 제공할 수 있게 된다.
이렇게 Key만 알면 바로 원하는 Value를 찾을 수 있기 때문에 소요 시간이 O(1)이 된다!
참고자료
https://youtu.be/HraOg7W3VAM?si=PjTYzNs8gj5yMfGS