[Data Structure]해싱(Hashing)

해싱(Hashing)이란? 해시 함수(Hash Function)는 임의의 크기를 갖는 값에 대해 고정된 크기를 갖는 해시값을 매핑하는 것을 의미합니다.

이러한 해시 함수를 이용해서 O(1)의 시간복잡도로 원소를 찾는 데 사용할 수 있습니다. 예를 들면 해시 함수를 "h(x) = x mod 10"이라고 하고 원소 1, 14, 27를 해싱을 사용한 자료구조에 저장한다고 해봅시다.

그러면 이 해시 함수에 의해서 0부터 9까지의 정수가 해시값으로 나올 수 있을 것입니다. 그리고 그 해시값에 대응되는 해시 테이블(Hash Table)을 만듭니다.

이제 해시값을 위치 정보로 사용해서 원래의 값을 저장합니다. 해싱 깊이 보기 충돌(Collision) 해싱은 들어오는 입력값에 따라서 중복되는 해시값을 반환할 수 있다는 문제점이 있습니다.

위 예시를 이용해서 "h(x)= x mod 10" 해시 함수는 x = 1, 11, 21 ... 등에 대해서 1이라는 공통된 해시값을 반환합니다.

좋은 해시 함수 ...

요청 처리 중입니다...

[Data Structure]해싱(Hashing)

등록된 다른 글