너무 어려워서 공부가 더 필요할 것 같다. 간단한 개념만 써봄..
해싱이란?
정보를 가능한한 빠르게 저장하고 검색하는데 사용되는 기법 중 하나
최적의 검색이 필요한 분야에서 사용됨
키의 값과 키가 저장된 위치를 찾아주는 처리과정을 해싱이라고 함.
해싱을 왜 사용하는가?
일반적인 해싱의 연산시간은 O(1)로 매우 빠르다. 단 최악의 겅우 O(n)이 될 수도 있다.
해싱 구성요소
1) 해시테이블(Hash Table) : 데이터가 처리되는 장소
키와 값 쌍으로 저장할 때 사용하는 자료구조.
해시함수를 이용해 키와 관련된 값을 매핑한다
2) 해시함수 (Hash Functions) : 키 위치 변환 함수
주어진 키를 특정 인덱스로 변환하는데 사용된다.
특정 인덱스에 이미 다른 키가 있는 경우를 충돌이라 하며 다른 저장위치를 계산하는 것을 충돌해결 이라고 한다.
3) 충돌 (collisions) : 해시함수의 값이 같은 경우 위치 중복으로 충돌 발생
4) 충돌 해결기법(Collisions Resolution Techniques)
이상적인 해시함수의 조건
: 충돌 최소화, 쉽고 빠른 연산, 테이블 전체에 값이 균일하게 분포, 사용할 키의 모든 정보를 이용하여 해싱, 해시 테이블 사용 효율이 높은 것
반응형