[자료구조] 06 테이블

▶ 테이블 (Table)

: 저장되는 데이터는 키와 값이 하나의 쌍을 이룬다.

: 키가 존재하지 않는 '값'은 저장 불가

: 모든 키는 중복되지 않는다.

: ex) 사전(단어-키, 설명-값)

 

 

▶

: 배열의 인덱스 값을 키 범위로 사용하기에 적당하지 않다.

: 왜냐하면 매우 큰 배열이 필요하기 때문

: 이를 해결해주는 것이 '해쉬 함수'

 

 

▶ 해쉬 함수 (Hash Function)

: 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할

: 좋은 해쉬 함수는 데이터가 메모리에 골고루 분포하여 충돌 활률이 낮다.

 

 

▶ 좋은 해쉬 함수 만드는 법

: 키의 특성에 의존되기 때문에 정답은 없다.

: 키의 일부분 참조항여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬값 만들기

 

 

▶ 해쉬 충돌 (Hash Collision)

: 서로 다른 2개 이상의 키가 해쉬 함수를 통해 나온 해쉬값이 동일한 경우

 

 

▶ 충돌 해결책

열린 주소 방법 (Open Addressing Method)	선형 조사법 (Linear Probing)
	이차 조사법 (Quadratic Probing)
	이중 해싱 (Double Hashing) (이상적인 해결책)
닫힌 주소 방법 (Close Addressing Method)	체이닝 (Chaining)

 

 

▶ 선형 조사법 (Linear Probing)

: f(k), f(k +1), f(k + 2), f(k +3) ...

: 클러스터 현상 (집중적으로 몰림 현상)

 

 

▶ 이차 조사법 (Quadratic Probing)

: f(k), f(k) + 1, f(k) + 4, f(k) + 9 ...

: 해쉬값이 같으면 충돌 발생 시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다.

 

 

▶ 이중 해싱 (Double Hashing)

: h1(k) = k % 15

: 키를 근거로 저장위치를 결정하기 위한 것

: h2(k) = 1 + (k % C)

: 충돌 발생시 몇 칸 뒤를 살필 지 결정하기 위한 것

: C는 15보다 작은 소수

 

: 1차 해쉬값이 같아도 2차 해쉬 값은 다르다

: 2차 해쉬값을 근거로 빈 슬롯을 찾는 과정은 다음과 같다

h2(18) → h2(18) + 5 × 1 → h2(18) + 5 × 2 → ...

 

 

▶ 체이닝 (Chaining)

: 연결 리스트 기반

 

 

▶ 체이닝 구현 방법 2가지

: 1. 슬롯이 연결리스트의 노드 역할을 하게 하는 방법

: 2. 연결 리스트의 노드와 슬롯을 구분하는 방법 (권장)