반응형
해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하는 방식이다
- 해시 함수 : 키 값을 해시 테이블의 주소로 변환하는 함수
- 종류 : 제산 함수, 폴딩 함수, 중간 제곱 함수, 비트 추출. 숫자 분석 / 주로 제산 함수 사용 - 해시 : 해시 함수의 결과물 (해시 테이블의 인덱스)
- 해시 테이블 : 해시에 의해 직접 접근이 가능한 자료구조 (배열)
- 버킷 : 해시 테이블에 저장되어 있는 데이터
제산 함수 : h(x) = x mod M :: 키 값이 0 ~ M - 1으로 형성됨
- 군집화 방지를 위해 M은 소수로 설정
해싱의 문제점
① 충돌 (Collision) : 서로 다른 키의 해시가 동일한 경우
② 군집화 (Clustering) : 데이터가 해시 테이블에 분산되지 않고 집중되는 현상
충돌 해결 방법
1. 개방 조사법
- 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
① 선형 조사법 (Linear Probing) : (h(x) + i) % M, i = 1 ~ M - 1
- 장점 : 간단
- 단점 : 1차 군집화 가능
8, 1, 15, 6, 13 순서대로 삽입 / 테이블 크기 7
1. 8 % 7 = 1
2. 1 % 7 = 1 [충돌] -> (1 % 7 + 1) % 7 = 2
3. 15 % 7 = 1 [충돌] -> (15 % 7 + 1) % 7 = 2 [충돌] -> (15 % 7 + 2) % 7 = 3
4. 6 % 7 = 6
5. 13 % 7 = 6 [충돌] -> (13 % 7 + 1) % 7 = 0
② 이차 조사법 (Quadratic Probing) : (h(x) + \(i^2\)) mod M, i = 1 ~ M - 1
- 장점 : 1차 군집화 개선
- 단점 : 2차 군집화 가능
8, 1, 15, 6, 13 순서대로 삽입 / 테이블 크기 7
1. 8 % 7 = 1
2. 1 % 7 = 1 [충돌] -> {(1 % 7) + 1} % 7 = 2
3. 15 % 7 = 1 [충돌] -> {(15 % 7) + 1} % 7 = 2 [충돌] -> {(15 % 7) + 4} % 7 = 5 [충돌] -> {(15 % 7) + 9} % 7 = 3
4. 6 % 7 = 6
5. 13 % 7 = 6 [충돌] -> {(13 % 7) + 1} % 7 = 0
③ 이중 해싱 (Double Hasging) : 키를 참조하여 더해지는 값을 결정
- step = C - (x mod C), C는 M보다 작은 소수
- (h(x) + (1 .. ) * step) mod M
- 장점 : 군집화는 거의 없음
- 단점 : 완벽한 방법은 아님
8, 1, 15, 6, 13 순서대로 삽입 / 테이블 크기 7 / C는 5
1. 8 % 7 = 1
2. 1 % 7 = 1 [충돌] -> [1 + {5 - (1 % 5)}] % 7 = 5
3. 15 % 7 = 1 [충돌] -> [1 + {5 - (15 % 5)}] % 7 = 6
4. 6 % 7 = 6 [충돌] -> [6 + {5 - (6 % 5)}] % 7 = 35. 13 % 7 = 6 [충돌] -> [6 + {5 - (13 % 5)}] % 7 = 1 [충돌] -> [6 + 2 * {5 - (13 % 5)}] % 7 = 3 [충돌] -> [6 + 3 * {5 - (13 % 5)}] % 7 =5 [충돌] -> [6 + 4 * {5 - (13 % 5)}] % 7 = 0
2. 체이닝
- 연결 리스트를 사용해 각 버킷에 하나 이상의 값을 저장하도록 함
8, 1, 15, 6, 13 순서대로 삽입
1. 8 % 7 = 1
2. 1 % 7 = 1
3. 15 % 7 = 1
4. 6 % 7 = 6
5. 13 % 7 = 6
반응형