해쉬함수 충돌해결법과 특징 강원대학교 컴퓨터과학과 이해원.

Presentation on theme: "해쉬함수 충돌해결법과 특징 강원대학교 컴퓨터과학과 이해원."— Presentation transcript:

1 해쉬함수 충돌해결법과 특징 강원대학교 컴퓨터과학과 이해원

2 충돌 전화번호 키 445-3800이라는 전화번호를 키로 하는 레코드
키 자체를 인덱스로 하여 이 레코드를 T[ ]에 저장 이 경우의 해쉬 함수는 자체 매핑(Identity Mapping) 메모리 크기는 제한적이므로 배열 인덱스의 범위를 줄일 필요가 있음. 같은 동네라면 국을 생략 T[3800]에 저장. 이 경우 해쉬 함수는 에서 3800으로 가는 매핑. 스트리핑(Stripping) 메모리 크기 인덱스 로 매핑. 전화번호의 처음 네 자리를 떼어버리면 T[800]에 이나 이나 모두 동일한 인덱스로 매핑 충돌(Collision) 서로 다른 키에 해쉬 함수를 가한 결과 동일한 인덱스로 매핑 되는 현상 메모리에 여유 공간이 있음에도 불구하고, 해쉬 함수 자체의 특성으로 인해 발생

3 충돌 해결방법 충돌 어떤 해쉬 함수를 사용하든 피해갈 수 없는 문제 해결책(Collision Resolution)이 필요.
열린 어드레싱(Open Addressing) 충돌이 일어나면 자기 자리가 아닌 곳으로 들어갈 수 있도록 허용 다른 키를 가진 레코드가 해쉬 되어 들어가야 할 자리까지도 오픈 선형탐사, 제곱탐사, 이중해쉬 닫힌 어드레싱(Closed Addressing) 자기자리가 아니면 절대로 못 들어가게 함 버켓, 별도 체인

4 선형탐사 선형탐사(Linear Probing) 충돌이 일어나면 그 다음 빈 곳
T[h(KEY)]가 점유되어 있을 때,  T[h(KEY) + 1],  T[h(KEY) + 2], ... 의 순서로 빈 곳이 있을 때까지 찾아감. 배열의 끝을 만나면 다시 처음으로 되돌아와서 거기서부터 빈자리를 찾음 h(key) = h % 31

5 선형탐사의 태그 필요성 65, 34, 127까지 들어간 상태에서 키 34인 레코드를 삭제. 인덱스 4의 위치는 빈칸
이후, 키 127을 가진 레코드를 탐색시, 인덱스 4가 “빈칸이니 찾는 레코드가 없다”라고 결론지을 수는 없음. 인덱스 5에 찾는 레코드가 있기 때문. 배열 아이템을 세 가지 상태로 분류 사용 중(Occupied), 삭제 됨(Deleted), 미 사용(Empty) 탐색도중 미 사용 칸을 만나면 탐색을 중지하고 찾는 레코드가 없다고 결론 탐색도중 삭제됨 칸을 만나면 탐색을 계속함.

6 클러스터 현상 선형탐사의 최대 단점 클러스터(Cluster, 군집, 群集) 현상
선형탐사의 클러스터는 1차 클러스터(Primary Cluster) 클러스터 = 레코드가 분산되지 않고 떼 지어 몰려다님 키 34인 레코드는 사실상 34 % 31 = 3에 들어가야 할 레코드가 오른쪽에 밀린 것이고, 키 127인 레코드도 사실은 127 % 31 = 3에 들어가야 하는 레코드.

7 제곱탐사 제곱 탐사(Quadratic Probing) 충돌이 일어날 때 바로 그 뒤에 넣지 않고 조금 간격을 두고 삽입
T[h(KEY)]가 점유되어 있을 때, T[h(KEY) + 1],  T[h(KEY) + 2], T[h(KEY) + 3], ... 의 순서로 제곱 간격을 두고 빈 곳을 찾아감. 정확하게는  T[h(KEY) + 1] % M이 다음 찾을 인덱스 위치 65, 34, 127의 삽입 h(key) = h % 31 65인 레코드가 인덱스 3으로 들어감. 키 34인 레코드가 인덱스 3으로 해쉬 어 충돌. 1의 제곱은 1이므로 이 레코드는 인덱스 4로 키 127인 레코드가 역시 인덱스 3으로 해쉬됨. 이후 4, 7, 2 순으로 탐사

8 제곱탐사의 빈칸

9 이중해쉬 이중 해쉬(Double Hash) 제곱탐사의 단점인 2차 클러스터를 방지
선형 탐색과 제곱탐색에서의 탐사 순서가 키 값과는 무관하게 규칙적 키 값에 따라서 탐사순서를 달리함으로써 탐사순서의 규칙성을 제거 두 개의 해쉬 함수 h1, h2를 사용 h1은 주어진 키로부터 인덱스를 계산하는 해쉬 함수 h2는 충돌 시 탐색할 인덱스의 간격(Step Size)을 의미

10 이중해쉬 h1 = KEY % 13, h2 = 1 + KEY %  11 키 14인 레코드의 삽입 14 % 13 = 1에서 충돌. (1 + (14 % 11)) = 4를 간격으로 탐사 순서는 1, 5, 9, 0으로 진행. 인덱스 0에서 빈 곳을 찾았으므로 거기에 삽입 키 27인 레코드의 삽입 27 % 13 = 1. (1 + (27 % 11)) = 6. 탐사 순서는 1, 7, 0, 6 인덱스 6에 삽입 키 18인 레코드의 검색 18 % 13 = 5. (1 + (18%11)) = 8. 탐사 순서 5, 0, 인덱스 0에서 빈 곳이므로 그런 레코드 없다고 결론. h2 함수의 선택 어떤 키에 대해서도 h2의 결과는 0이 되어서는 안 됨. 0이면 계속 같은 자리에서 찾는 꼴 h1과 동일한 함수여서는 안됨. 모든 키에 대해서 간격이 같아지기 때문. 2차 클러스터를 제거. 그러나 두 개의 해쉬 함수를 계산해 내는데 따른 시간적 손실을 전제로 함.

11 선형탐사, 이중해쉬 선형탐사, 이중해쉬 부하율 50% 66% 75% 90% 선형탐사 탐색 1.5 2.0 3.0 5.5 삽입
부하율 50% 66% 75% 90% 선형탐사 탐색 1.5 2.0 3.0 5.5 삽입 2.5 5.0 8.5 55.5 이중 해쉬 1.4 1.6 1.8 2.6

12 닫힌 어드레싱 버켓 별도체인

13 버켓 버켓(Bucket) 배열 요소가 다시 여러 개의 요소로 이루어짐
이 경우 자료구조는 배열의 배열(Array of Array)로서 2차원 배열 충돌되는 레코드를 하나의 인덱스 안에 둘 수는 있음 해당 인덱스로 가서 다시 키가 일치하는 레코드를 찾아야 하는 시간적 부담 사용되지 않는 배열 공간이 낭비됨.

14 별도 체인 별도 체인(Separate Chaining) 배열 요소가 연결 리스트를 가리키는 헤드
일명 분산 테이블(Scatter Table) 충돌이 일어날 때마다 해당 레코드를 연결 리스트의 첫 위치에 삽입 동적 구조(Dynamic Structure)

15

16 별도 체인 별도 체인의 효율 체인의 길이에 비례 평균적으로 체인 길이는 부하율(N/M)과 동일
부하율 λ일 때 별도 체인에서의 평균 키 비교회수는 (1 + λ/2) 부하율 1 이하의 별도 체인에서는 상수시간 삽입 및 검색이 가능 노드 공간을 할당하는 함수를 불러야 하는 시간, 포인터를 따라가는 시간, 포인터 변수 자체가 차지하는 공간을 요함 버켓과 별도 체인 닫힌 어드레싱 해쉬 된 인덱스 안에서 다시 배열이나 연결 리스트 등의 또 다른 자료구조를 사용함으로써 충돌을 해결

17 감사 합니다.

18

19 유니버설 해쉬 좋은 해쉬 함수 레코드를 메모리 공간에 골고루 분포시킴으로써 충돌을 최소화
입력 데이터 패턴과 무관하게 이러한 특성을 보여야 함. 그러나 실제로 이런 함수를 만들기가 어려움 유니버설 해쉬 다양한 해쉬 함수를 준비해 놓고 선택적으로 사용 해쉬 함수의 선택은 랜덤(Random)하게 이루어 짐. 응용 프로그램이 시작할 때 하나를 골라서 끝날 때까지 사용 유니버설(Universal, 보편적) 테이블 크기 M일 때, 서로 다른 키가 같은 인덱스로 매핑 될 확률이 1/M 이하인 해쉬함수

20 재 해쉬 재 해쉬(再 해쉬, Rehash) 삽입이 계속되면 부하율이 일정 한계를 넘음
부하율을 낮추는 테이블 크기 M을 키우는 것. 힙 공간에 동적 배열 생성 한꺼번에 기존 테이블의 2 배 크기의 배열을 생성 이전 데이터를 복사 재 해쉬를 가하는 시기 테이블이 반 정도 찰 때 부하율이 미리 정해진 어떤 값을 넘을 때 삽입이 실패할 때