14-2 해싱

1. 해싱의 개념

① 해싱

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

  - 검색 방법

    1. 키 값에 대해 해시 함수를 계산하여 주소 구함.

    2. 구한 주소에 해당하는 해시 테이블로 이동

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

 - 해시 함수 : 키 값을 원소의 위치로 변환하는 함수

 - 해시 테이블 : 해시 함수에 의해 계산된 주소의 위치에 항목을 저장한 것.

 

② 해싱 검색 수행 방법

③ 해싱관련 용어

  - 해시 테이블에서 버킷 수를 줄이고 같은 버킷안에 슬롯을 여러 개 두어 해시 함수로 만든 주소가 같은 키 값들은 같은 버킷에 저장한다.

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

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

              > 비어있는 슬롯에 동거자 관계로 키 값 저장하면 되지만, 비어 있는 슬롯 없을 때 문제 생김

  - 포화 버킷 상태 : 버킷에 빈 슬롯 X

  - 오버 플로우 : 포화 버킷 상태에서 충돌 발생하여 해당 버킷에 키 값 저장 불

 

④ 키값의 밀도와 적재 밀도

 -  키 값 밀도 : 실제 사용 중인 키값의 개수 / 사용 가능한 키값의 개수

 -  적재 밀도 :  실제 사용 중인 키값의 개수 / 해시 테이블에 저장 가능한 전체 키값의 개수 (버킷 개수 * 슬롯 개)

 

2. 해시 함수

① 해시 함수

 - 키 값을 원소의 위치로 변환하는 함수

 - 조건 : 1. 계산이 쉬워야 함

              2. 충돌이 적어야 함.

              3. 해시 테이블에 고르게 분포하도록 주소 만들어야 함.

② 중간 제곱함수

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

 

③ 제산 함수

 - 나머지 연산자 mod를 사용

 - M은 적당한 크기의 소수로 사용

 

④ 승산 함수

  - 곱하기 연산 사용

  - 키 값 k와 정해진 실수 a를 곱한 결과에서 소수점 이하 부분만을 테이블의 크기 M과 곱하여 정수 값을 주소로 사용

 

⑤ 접지 함수

 - 키의 비트 수가 해시 테이블 인덱스의 비트 수보다 큰 경우에 사용

 - 이동 접지 함수

- 경계 접지 함수

⑥  숫자 분석 함수

  - 키 값을 이루고 있는 각 자리숫의 분포를 분석하여 해시 주소로 사용

⑦ 진법 변환 함수

 - 키 값이 10진수가 아닌 다른 진수일 때, 10 진수로 변환하고 해시 테이블 주소로 필요한 자릿수만큼만 하위자리의 수 사용

⑧ 비트 추출 함수

  - 해시 테이블의 크기 2의 k승 일 때, 키 값을 이진 비트로 놓고 임의의 위치에 있는 비티들을 추출하여 주소로 사용하는 방법

 

3. 해싱에서 오버플로우 처리 방법

① 오버플로우 처리 방법

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

     오버플로우 발생시 , 그 다음 버킷에 빈슬롯 있는 지 조사

     > 빈 슬롯 있는 버킷 생길 때 까지 찾아서 키 값 저장

② 체이닝

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

  - 버킷에 슬롯을 동적으로 삽입하고 삭제하기 위해서 연결 리스트 사용

    ■ 각 버킷에 대한 헤드 노드 1차원 배열로 생성

    ■ 각 버킷에 대한 헤드노드는 슬롯들을 연결리스트로 가지고 있어서 슬롯의 삽입, 삭제 연산 쉽게 수행 가능

    ■ 버킷내 원하는 슬롯 검생하기 위해서는 버킷을 연결리스트 선형 검색