DB 유형 - 해시

해싱함수

 

정적/동적

개방주소법, 체이닝기법

고속성,사상함수,단방향성

충돌, 동거자, 오버플로우

개선이이, 체합분

고속검색, 특징(압축,단방향,충돌회피,효율)

 

해시함수, 주소 접근, 종류(버켓, 슬롯, 충돌, 해싱표)

해결방법 ( 선형개방 , 체인이용형)

활용 : 주소 탐색 , 자료 탐색

패턴 : - 버킷 -> slot -> synomym -> (collision / overflow)

 

해쉬 테이블은 Key에 Value를 저장하는 데이타 구조로, value := get(key)에 대한 기능이 매우매우 빠르게 작동한다.

hash_function(key) / size_of_array의 값이 중복

 

 

[개념] 해시를 통해 생성된 키로 목표 레코드를 직접 접근할 수 있게 하는 기법

[구성요소] 해싱함수,해시키,버킷,슬롯,해싱표,Synonym(동거자),충돌(Collision)

 

 

해싱함수 종류

 

 

 

 

 

 

 

[충돌현상] 서로 다른 두 개 이상의 키 값들이 해시 함수에 의해 동일한 주소로 변환되는 경우

 

 

 

[개방/체인법 성능관점 비교항목]

복잡도, 평균비교횟수 기대치, 속도, 기억소모량, 테이블크기

 

해싱 오버플로우

 

개방주소, 폐쇄주소

 

[개방주소] : 선형검색, 2차검색, 랜덤검색

 

1)개방주소법 - 충돌발생시 저장할 공간을 비어있는 버킷에서 찾는 방법

가.선형탐색법(첫번째 빈버킷)

나.2차탐색법(특정 수만큼 떨어진 곳의 순환서치) 다.재해싱(키값을 두번 해싱)

 

1) 선형검색 : 충돌발생시 차례로 빈 버킷 검색, 간단한 기법/집중현상

2) 2차검색: 집중문제 해결, 특정거리 떨어진곳 순환적 빈 버켓 검색

3) 랜덤검색: 충돌발생시 무작위로 빈 버켓 검색

 

2)체이닝기법 - 같은 주소로 해싱되는 동거자를 하나의 linked list로 관리

가.합병체인법(저장후 포인터)

나.분리체인법(링크드리스트)

 

 

[폐쇄주소] : Direct, Indirect, Overflow 영역

1) Direct Chaning: 충돌발생시 빈 버캣 찾아 삽입, 위치 저장

2) Indirect Channing: 충돌 키값 연결리스트 구성 처리

3) Overflow Area: 별도 영역 구성, 테이블에 없는 record 검색

 

 

 

[비교] 복잡도, 평균비교횟수, 검색속도, 기억 소모량, 테이블 크기

1)복잡도: 단순/복잡

2)횟수: 적재밀도 a : (2-a)/(2-2a) | 1 + a/2

3)속도: 빠름, 문제발생시 성능저하/ 속도빠름

4)소모량: 적음/많음

5)테이블 크기:크기의존, 크기 독립적

 

[활용분야]연관배열자료구조, 캐시, 페이지 테이블, DB

 

해싱 테이블

 

[개념] 해시 함수에 의해 산출된 주소 값의 위치에 각 레코드를 기억 시킨 테이블

* 충돌해결전략 [개선이이 폐합분]

1) 개방주소법 : 비어 있는 버킷 탐색

- 선형 조사법(Linear Probing) : 빈 버킷 순차적 탐색

- 이차 조사법(Quadratic Probing) : 2차함수 이용해 탐색

- 이중 해싱 (Double Hashing) : 충돌 발생시 2차 해시함수 이용 새주소 할당

2) 폐쇄주소법

- 합병 체인법 (Coalesced Chaining)

: 충돌 발생시 빈 버킷을 찾아 삽입하고 삽입된 위치를 포인터 부분에 기억

- 분리 체인법 (Separate Chaining) : 충돌 발생한 키 값들을 연결리스트로 처리