CS - Data Structure - Hashing(해싱)

Hashing

 

 

키(Key)값을 해시 함수(Hash Function)에 대입하여 나온 결과를 주소로 사용하여 값(value)에 접근하는 방법

 

 

Hash Function

 

 

키(Key)값을 값(Value)이 저장된 주소로 바꾸어주는 함수. 

 

키(Key)값을 값(Value)이 저장된 주소로 바꾸는 일을 매핑(Mapping)이라고 한다.

 

 

장점

 

 

데이터의 탐색을 O(1)만에 가능하다.

 

데이터의 빠른 저장과 탐색이 필요할때 유용한 방법

 

해싱은 주로 '사전(dictionary)' 자료 구조를 구현할 때 사용

 

 

 

단점

 

단점으로는 메모리에 데이터가 순차적으로 저장되지 않아 메모리상에 빈 공간이 많이 생기는 메모리 낭비가 발생한다.

 

해시 함수는 중복이 발생 가능하다.

 

다른 키값을 입력했는데 같은 해시 값이 도출될 수 있다. 그래서 연산이 빠르고, 충돌이 적고, 고르게 분포되는 해시 함수가 좋은 함수로 평가받는다.