Hyogi's Notebook

해싱(hashing) - 알고리즘

by 효기’s
충돌(Collision)

두 개의 키가 동일한 버킷으로 해싱되는 경우

동의어(SYNONYMS)

같은 주소로 해싱되어 충돌을 일으킨 키

해싱의 탐색 시간은 O(1)

 

오버플로우(Overflow)

해시 충돌이 버킷(bucket)에 할당된 슬롯(Slot) 수보다 많이 발생해서 더이상 버킷에 값을 넣을 수 없는 현상

 

해싱 특징

검색 속도가 빠르며 삽입, 삭제의 빈도가 높음

해싱 기법에는 숫자분석법, 제산법, 제곱법, 접지법이 있다.

오버플로가 발생했을 때 해결기법으로 개방주소법(open addressing) 과 폐쇄주소법(close addressing)이 있다.

 

해싱 장점

레코드를 찾기 위해 키 값을 모두 비교할 필요 없다.

순차파일에서 데이터 탐색 시간 O(n)

 

키 값을 직접 주소로 사용하는 경우보다 기억장소 효율적

 

레코드의 저장 주소를 직접 계산에 의해 얻을 수 있으므로 탐색 속도 고속

 

오버플로우 또는 충돌이 없으면 원하는 레코드에 한번에 접근 가능

 

해싱 단점

모든 키 값을 숫자(정수형)으로 변환 필요

 

키의 변환을 통하여 생성되는 주소가 주소공간에 적절히 분포될 수 있도록 하는 해시 함수를 구하는 문제 존재

 

충돌이나 오버플로우 해결 문제 존재

 

해싱 함수(Hashing Function)

키 공간을 유효 주소 공간으로 사상(Mapping)

 

해싱 함수는 키 값들을 한정된 주소 공간으로 균등 분산하는 것이 가장 중요

 

좋은 해시 함수 조건 : 해시 함수 값이 해시 테이블의 주소 영역에 고르게 분포

해시 값 계산이 빨라야 한다.

 

숫자 분석법 (Digit analysis)

각 수의 분포를 이용해서 균등한 분포의 숫자 선택

중첩법(Folding method)

탐색키가 해시테이블 크기보다 더 큰 정수일 때 사용

키의 마지막 부분을 제외한 모든 부분이 동일한 크기로 분할

이들 부분에 대해 ADD또는 XOR연산을 해서 결과 값을 주소로 이용

 

 Folding 의 종류

Shifting folding 방법

마지막을 제외한 모든 부분을 이동시켜 하위 비트부터 일치 시켜 계산을 하고 그 결과 값을 주소로 사용

Boundary folding 방법

키 값을 나눈 후 그 값들의 경계를 중심으로 접어 역으로 정렬한 후 그 값들을 더한 값을 주소로 사용

폐쇄 주소법 - Chaining (충돌 회피)

각 버킷에 삽입과 삭제가 용이한 연결 리스트 할당

버킷 내에는 연결 리스트 순차 탐색

 

나눗셈법

Division method

나머지 연산자(%) 를 사용하여 주소를 계산

주소 = 키값%해시테이블 크기

 

특징

가장 간단한 방법

해시 주소 고르게 분포되지 않는 문제

 

선형탐사법 (Linear Probing)

장점 : 순차적으로 해결이 가능

단점 : clustering 현상이 발생하여 또 다른 오버플로 발생가능

 

해싱에서 충돌이 일어난 자리에서

그 다음 버킷들을 차례로 하나씩 검색하여 최초로 나오는 빈 버킷에 해당 데이터를 저장하는 방법

블로그의 프로필 사진

블로그의 정보

감성 개발자 효기

효기’s

활동하기