해싱(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