[자료구조] 해싱 (Hashing)

해싱(Hashing)

: 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식

 - 검색 방법 : 키 값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 이동

    => 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패

 - 해싱 함수(hashing function) : 키 값을 원소의 위치로 변환하는 함수

 - 해시 테이블(hash table) : 해싱 함수에 의해서 계산된 주소의 위치에 항목을 저장한 표

 

 - 해싱 용어

    ㄴ 충돌 : 서로 다른 키 값에 대해 해싱 함수에 의해 주어진 버킷 주소가 같은 경우

        해결 방법 : 충돌이 발생한 경우 비어있는 슬롯에 동거자 관계로 키 값 저장

    ㄴ 동거자 : 서로 다른 키 값을 가지지만 해싱 함수에 의해 같은 버킷에 저장된 키 값들

    ㄴ 오버 플로우 : 버킷에 비어있는 슬롯이 없는 포화 버킷 상태에서 충돌이 발생하여 해당 버킷에 키 값을 저장할 수 없는 상태

    ㄴ 키 값 밀도 : 사용 가능한 전체 키 값들 중 현재 해시 테이블에 저장되어서 실제 사용되고 있는 키 값이 개수 정도

    ㄴ 적재 밀도 : 해시 테이블에 저장 가능한 키 값의 개수 중 현재 해시 테이블에 저장되어 실제 사용되고 있는 키 값의 개수 정도

---

해싱 함수

 - 조건 ① : 해싱 함수는 계산이 쉬워야 한다.

    ㄴ 비교 검색으로 키 값의 비교 연산을 수행하는 시간보다 해싱 함수 계산이 빨라야 해싱 검색 사용의 의미가 생김

 - 조건 ② : 해싱 함수는 충돌이 적어야 한다.

    ㄴ 충돌이 많이 발생한다는 것은 동거자가 많아진다는 뜻으로 다른 비어있는 버킷이 많음에도 특정 버킷에 오버플로우가 발생할 수 있는 상태가 되므로 좋은 해싱 함수라 볼 수 없다.

 - 조건 ③ : 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.

---

함수 종류

 - 중간 제곱 함수

    : 키 값을 제곱한 결과 값에서 중간에 있는 적당한 비트를 주소로 사용

    ㄴ 제곱한 값의 중간 비트들은 대개 키의 모든 값과 관련이 있기 때문에 서로 다른 키 값은 서로 다른 중간 제곱 함숫값을 갖게 됨

 

 - 제산 함수

    : 나머지 연산자(mod)를 사용하는 방법

    ㄴ 키 값 k를 해시 테이블의 크기 m으로 나눈 나머지를 해시 주소로 사용

    ㄴ h(k) = k mod m

    ㄴ m으로 나눈 나머지 값은 0~(m-1)이므로 해시 테이블의 인덱스로 사용

    ㄴ 해시 주소는 충돌이 발생하지 않고 고르게 분포하도록 생성되어야 하므로 키 값을 나누는 해시 테이블의 크기 m은 적당한 크기의 소수(Prime Number) 사용

---

수행 방법

---

오버 플로우 처리 방법

 - 선형 개방 주소법 (선형 조사법(Linear Probing))

    : 해싱 함수로 구한 버킷에 빈 슬롯이 없어 오버플로우가 발생하면 그다음 버킷에 빈 슬롯이 있는지 조사

    ㄴ 빈 슬롯 있으면 키 값을 저장

    ㄴ 빈 슬롯 없으면 다시 그다음 버킷 조사

 

Ex)

• 해시 테이블의 크기 : 5

• 해시 함수 : 제산 함수 사용. 해시 함수 h(k) = k mod 5

• 저장할 키 값 : {45, 9, 10, 96, 25}

 

① 키 값 45 저장 : h(45) = 45 mod 5 = 0

    ⇒ 해시 테이블 0번에 45 저장

0	45
1
2
3
4

② 키 값 9 저장 : h(9) = 9 mod 5 = 4

    ⇒ 해시 테이블 4번에 9 저장

0	45
1
2
3
4	9

③ 키 값 10 저장 : h(10) = 10 mod 5 = 0

    ⇒ 충돌 발생! 다음 버킷 중에서 비어있는 버킷 1에 10 저장

0	45
1	10
2
3
4	9

④ 키 값 96 저장 : h(96) = 96 mod 5 = 1

    ⇒ 충돌 발생! 다음 버킷 중에서 비어있는 버킷 2에 96 저장

0	45
1	10
2	96
3
4	9

⑤ 키 값 25 저장 : h(25) = 25 mod 5 = 0

    ⇒ 충돌 발생! 다음 버킷 중에서 비어있는 버킷 3에 25 저장

0	45
1	10
2	96
3	25
4	9

 

- 체이닝

    : 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 저장할 수 있도록 함

    ㄴ 버킷에 슬롯을 동적으로 삽입하고 삭제하기 위해 연결 리스트 사용 ☞ ArrayList <> al [] = new ArrayList [];

 

Ex)

• 해시 테이블의 크기 : 5

• 해시 함수 : 제산 함수 사용. 해시 함수 h(k) = k mod 5

• 저장할 키 값 : {45, 9, 10, 96}

 

① 키 값 45 저장 : h(45) = 45 mod 5 = 0

    ⇒ 해시 테이블 0번에 노드를 삽입하고 45 저장

0	●	→	45	NULL
1	NULL
2	NULL
3	NULL
4	NULL

② 키 값 9 저장 : h(9) = 9 mod 5 = 4

    ⇒ 해시 테이블 4번에 노드를 삽입하고 9 저장

0	●	→	45	NULL
1	NULL
2	NULL
3	NULL
4	●	→	9	NULL

③ 키 값 10 저장 : h(10) = 10 mod 5 = 0

    ⇒ 해시 테이블 0번에 노드를 삽입하고 10 저장

0	●	→	45	●	→	10	NULL
1	NULL
2	NULL
3	NULL
4	●	→	9	NULL

④ 키 값 96 저장 : h(96) = 96 mod 5 = 1

    ⇒ 해시 테이블 1번에 노드를 삽입하고 96 저장

0	●	→	45	●	→	10	NULL
1	●	→	96	NULL
2	NULL
3	NULL
4	●	→	9	NULL