해싱
; 해시 함수에 의하여 계산된 키 값의 주소로 직접 접근하는 것
- 해싱 = 'key to address transformation', 즉 특정 규칙에 따라 주어진 키 값을 주소로 변환하여 해시 테이블이라는 기억공간에 키의 레코드를 저장
- 해시 함수를 이용하여 필요한 레코드의 주소를 산출함으로서 검색작업을 수행
해시 테이블
; 해시 함수에 의해 산출된 주소에 각 레코드를 기억시킨 테이블
- 버킷들로 구성되어 있으며, 각각의 버킷은 슬롯으로 구성
해시 함수
; 입력된 키 값을 해시 테이블의 주소로 변환시켜주는 함수
- 중간 제곱함수 ; 키 값을 제곱한 후 그 수의 중간에 정해진 자리 수만큼을 취해서 해시 테이블의 버킷주소로 만듬
- 나누기 함수 ; 키 값을 해시 테이블의 크기로 나누어서 그 나머지를 버킷 주소로 변환
- Folding 함수 ; 키 값을 버킷 주소 크기만큼의 부분으로 분할한 후, 분할된 것을 더하거나 연산하여 그 결과 주소의 크기를 벗어나는 수는 버리고 택하여 버킷의 주소로 만드는 방법
- 기수 변환법 ; 주어진 키 값을 다른 진법의 수로 판단하고, 이를 진법 변환을 통하여 버킷의 주소를 계산
- 숫자 변환법 ; 모든 키 값들을 임의 기수 숫자로 바꾼 후 모든 자리 수에 대한 테이블을 만들고, 각 자리 수에 대한 숫자별 빈도를 파악하여 특정 숫자로 편중되지 않고 어느 정도 균등한 분포를 갖는 자리수를 주소로 사용
해싱의 문제점
; 해싱을 하는 경우 서로 다른 두개 이상의 키 값들이 해시 함수에 의해 동일한 주소로 변환되는 경우, 충돌 발생
-> 출돌이 발생하는 경우 버킷이 여러 슬롯으로 구성되어 있다면 다른 슬롯에 저장
-> 모든 슬롯이 채워지면 오버플로우 발생
=> 오버플로우 해결 방법
- 개방 주소법 ; 한 레코드의 키로부터 관련된 일련의 버킷 주소 생성 -> 생성된 버킷주소에서 충돌이 발생하면 생성된 버킷의 주소로부터 비어있는 버킷이 발견될 때까지 찾음
- 폐쇄 주소법(=체인법) ; 충돌이 발생하는 동의어 별로 연결리스트로 저장되는 방법, 가장 많이 사용
'알고리즘' 카테고리의 다른 글
| [알고리즘] 다익스트라 (0) | 2022.06.06 |
|---|---|
| [알고리즘] DP(Dynamic Programming) (0) | 2022.06.06 |
| [알고리즘] 선형 리스트(Stack, Queue, Deque) (0) | 2022.06.06 |
| [알고리즘] 해시 (0) | 2022.06.06 |
| [알고리즘] 탐색 (0) | 2022.05.29 |
| [알고리즘] 그래프 (0) | 2022.05.22 |
| [알고리즘] 연결 리스트 (0) | 2022.05.21 |
| [알고리즘] 배열과 연결리스트 (0) | 2022.05.21 |
