해시 Flashcards
해싱
[정의] 키 값으로부터 해시함수를 적용하여 주소 값을 계산하고, 계산된 주소 값으로 레코드가 저장되어 있는 위치에 직접 접근하는 방법
[특징] 고속성 O(1), 사상함수 (키-주소), 단방향성
[구성요소] 해시함수, 해시키, 해시 테이블, 버킷, 슬롯, Direct File, 해싱표
[종류]
- 정적 해싱 : 버켓 주소의 집합을 고정시켜 처리하는 해싱 기법
- 동적 해싱 : 해싱 함수를 동적으로 변경 시키는 해싱 기법(Overflow 발생시 2배수 확장)
- 확장 해싱(Extendible Hashing) : 동적 해싱의 한 형태이며 트리의 깊이가 2인 특별한 경우
[활용] 연관 배열 자료구조, DB, 캐시, Page 테이블, 프로그래밍 언어(Perl, Ruby)
[문제점] 충돌(Collision), 동거자(Synonyms), 오버플로우(Overflow)
[차별화] 충돌 해결방법
1. 개방주소법(폐쇄 해싱) : 선형 조사법, 이차 조사법, 이중 해싱법, 무작위 검색, 재해싱
2. 폐쇄주소법(개방 해싱, 체이닝) : 합병 체인법(coalesced chaining), 분리 체인법(separate chaining)
정적 해싱 기법
[정의] 버킷 주소 집합의 크기를 고정시켜 처리하는 해싱 기법
[특징] 해시 Table 크기 고정, (장) 삽입,삭제 간단, 빠름 (단) 공간 낭비, 주기적 재구성 필요
[문제점] Collision, Overflow
[해결법] 선형 검색법, 랜덤 검색법, 체인 이용법(Direct, Indirect)
동적 해싱 기법
[정의] 데이터베이스가 확장 또는 축소 시 해싱 함수를 동적으로 변경시키는 해싱 기법, Overflow발생시 2배 확장
[특징] 해시 Table 크기 조정, (장) 저장 공간의 효율성 (단) 성능 저하
[문제점] Collision
[해결법] Linear Method(주소+1로 빈곳 검색), Re-Hashing, Random Method
해시 테이블
[정의] 해시 함수에 의해 산출된 버킷 주소 값의 슬롯에 각 레코드를 기억 시킨 테이블
[특징] 버킷으로 구성, 버킷은 슬롯으로 구성
탐색적 알고리즘 해싱
[정의] 키값을 기반으로 데이터의 저장 위치를 직접 계산, 상수 시간내 데이터에 접근 할수 있는 탐색 알고리즘
[특징] 해시 함수가 성능에 영향, [핵심요소] 해시함수, 해시테이블(버킷,슬롯)
* 해시함수 결과인 키값을 인덱스와 같이 테이블 주소로 활용, 순차O(n), 이진트리O(log n)의 반복비교 수행 시간 단축
[매커니즘] 키값 → 해싱함수 → 해시주소(버킷주소) → 해시테이블 검색완료
* 탐색 성능 향상을 위해서는 각슬롯이 동일한 확률로 채워 질수 있는 해시 함수 선택중요
[해시함수 유형]
- 제산잔여법 : h(x) = x mod m (테이블 크기가 성능 영향) * m= 테이블 크기
- 비닝 : 키 값의 범위를 해시 테이블 크기로 분할(키값의 분포가 성능영향)
- 중간제곱법 : 키 값 제곱후 중간 값을 취해 해시주소로 활용 (정수키값 활용시 효율적)
- 문자열 해시 : 각 문자 ASCII 값의 합 % 테이블 크기 (문자출현 순서에 따라 결과영향)
- 폴딩법 : 레코드키 값을 여러부분으로 나눈 후 각 부분의 값을 더하거나 XOR
* 효과적인 탐색을 위해 해시 테이블에 충돌을 최소화한 균등 분포가 좋지만 현실적으로는 Collision 발생
[해싱 충돌방안 해결방안]
- 패쇄해싱(개방주소법), 개방해싱(폐쇄 주소법, 체이닝)
* 정기적 Rehashing 수행, Tombstone 제거를 통한 탐색 평균거리 축소 필요
해싱 충돌 해결 방안
[정의] 해시 함수가 서로 다른 두개의 입력값에 대해 동일한 출력값을 내는 현상
[영향] 알로리즘 효율성 저하, 오버 플로우 발생
[예방기법]
1. 체이닝(Chaining) : Linked List로 관리, 추가적인 연결 리스트 필요, 같은 주소값
2. 개방 주소법 : 주어진 테이블 공간내에서 빈 버킷 탐색 저장, 추가적인 공간 불필요, 주소값 변환
[예방기법 상세]
1. 개방해싱 / 폐쇄 주소법(Closed Address) / 체이닝(Chaining) 방식
- Direct Chaining : 동일 해시 테이블 내 유사 레코드를 연결리스트 구성
- Indirect Chaining : 해시 테이블과 별도로 기억 공간 확보, 유사레코드 연결
- Coalesced Chaining(합병 체인) : 빈 버킷을 찾아 삽입 후 삽입된 위치를 포인터 부분에 기억
- Separate Chaining(분리 체인) : 충돌이 발생한 키값들을 연결리스트로 처리
2. 폐쇄해싱 / 개방 주소법(Open Address) 방식
- 선형 조사법 : 충돌 위치로부터 순차적으로 탐색 저장 (구조 간단, 모든 테이블 탐색문제 발생)
- 이차 조사법 : 2차함수 기반 순환적 탐색, 2^n만큼 이동 탐색 (제2군집현상 발생 가능)
- 이중 해싱법 : 두 개의 함수를 이용, 하나의 함수는 최초 해시값, 다른 함수는 해시 충돌시 이동할 폭
- 랜덤 검색법 : 무작위 값 대입, 주소할당
- 재해싱 : 해시 테이블의 크기를 늘리고 새로운 해시 테이블의 크기에 맞춰 모든 데이터를 재해싱하는 방법
