테이블 그리고 해쉬 , 이중 해쉬 , 체이닝
테이블 - 키를 통해서 탐색대상을 담번에 찾을 수 있는 자료구조 형태
그러므로 시간 복잡도 가 O(1) 이다
하지만 테이블에 문제점이 있다
문제점 1. 조회번호 의 범위가 생성한 배열의 인덱스 값보다 큰 경우
2. 그러므로 조회번호의 범위를 수용 할 수 있는 매우 큰 배열이 필요하다.
위 두가지 문제점을 해결 해주는것이 해쉬 함수 이다
어느회사의 직원의 조회번호를 입사년도와 입사순서로 조합 했다고 가정하자 예로 2012년 3번째 입사한사람의 조회번호는20120003 이다
이 조회 번호를 getHashValue 라는 함수에 넣어서 해쉬값을 구한다는 전제하에 간단한 getHashValue 함수를 작성하겠다
public int getHashValue(int 조회번호){
reurn 조회번호 % 100 ;
}
20120003 넣었을시 03 이 답이다
위의 함수의 의미는 100 으로 % 연산을 햇는데 즉 여덟자리의 수로 이뤄진 조회번호를 두자리의 수로 변경한다 이다
위와 같은 함수를 해쉬 함수라고 한다 . 해쉬 함수의 역할은 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다.
위와 같이 해쉬 함수를 이용했을때 문제가 발생한다 예로 2012년에 100명 이상의 직원이 채용된경우 20120003 과 20120103을 부여받은 직원이 생겨나는데 둘다 위 해쉬 함수에 넣으면 같은 해쉬 값인 3을 얻게 된다 .
즉 해쉬값 충돌이라는 문제가 생기게 된다 .
이 해쉬값 충돌로 인해서 좋은 해쉬 함수와 좋지 않은 해쉬 함수가 구분이 되는데
예로
1..좋은 해쉬 함수의 메모리 구성 12개의 데이터가 입력되있경우
| | || | | | | | | | |
메모리의 시작 메모리의 끝
2.좋지 않은 해쉬 함수의 메모리 구성 12개의 데이터가 입력되있경우
| | | |||||| ||| |
메모리의 시작 메모리의 끝
결론은 좋은 해쉬 를 쓰면 데이터가 골고루 저장 되고 나쁜 해쉬를 쓰면 데이터가 골고루 저장이 안된다.
좋은 해쉬 함수를 구성하기위한 일반적인 조언은 - 작은 수의 데이터의 조합으로 해쉬값을 생성할때 보다 다양한 수의 데이터 조합으로 했을때 다양한 해쉬값이 나오고 데이터는 다양한곳에 메모리 골고루에 저장된다
데이터 조합 방법으로는 -자릿수 선택 방법과 자릿수 폴딩 방법
충돌 해결 방법
1.열린어드레싱방법 -- 충돌이 나면 그곳을 피해서 값을 집어 넣는다
즉 충돌이 나면 빈곳이 어딘가 탐색해서 빈곳에 값을 넣는식이다 .
그러므로 탐색 방법에 의해서 구분이 된다
1-1. 선형 조사 방법 -- 위의 20120003 과 20120103을 부여받은 직원이 생겨나는데 둘다 위 해쉬 함수에 넣으면 같은 해쉬 값인 3을 얻게 된다 . 경우를 예를 들어서 얘기하겠다
위와 같은 경우 3의 바로 옆자리인 4의 자리에 데이터의 값을 넣는다.만약에 4의 자리도 빈곳이 아니라면 5가 비었는지 본다
이와 같이 충돌이 일어나는 곳의 바로 옆을 탐색한다.
선형 조사의 탐색 순서는 그러므로 다음과 같이 전개된다.
f(k)+1 -> f(k)+2 -> f(k) +3 .........
그러므로 클러스터 현상(한곳에 밀집되서 충돌이 계쏙 일어나는 현상)이 일어난다는 단점이 있다
이러한 점을 극복하기 위해 이차 조사방법이 나왔다.
1-2.이차 조사 방법 -- 1.1의 문제점을 극복하기 위해서 " 좀 더 멀리 떨어진 곳에서 빈곳을 찾으면 어떨까라는 "생각에 맞춘 조사 방법
이와 같은 생각에 근거해서 이차조사방법의 전개도는 아래와 같다.
f(k)+1^2 -> fi(k)+2^2 -> f(k)+2^3 -> f(k)+2^4 -> f(k)+2^5 -> f(k)+2^6 ....
즉 선행 조사법은 충돌시 n칸 옆으로 이동하면서 조사를 한다면 이차 조사법은 충돌시 n^2칸 옆으로 이동하면서 빈칸이 없는지 조사를 한다 .
단점 -- k가 다르더라도 f(k)에 대한 해쉬 값이 같아면 일정한 부분만 조사하게 되서 클러스터 현상이 발생할 확률은 여전히 높다.
1-3. 이중 해쉬 - 이차 조사 방법의 단점을 해결하기 위한 가장 이상적인 충돌 해결책
이차 조사법의 단점을 극복하기 위해서
이중 조사법은 좀 멀리서 빈공간을 찾긴 하지만 그 빈 공간을 선택하는 방식이 한칸 , 네칸 , 아흡칸 이런식으로 규칙적인 부분을 좀 불규칙하게 구성 하면 된다 .
1차 해쉬 함수 - 키를 근거로 저장위치를 결정하기 위한 것
2차 해쉬 함수 - 충돌 발생시 몇 칸 뒤를 살필지 결정하기 위한 것
예로 1차 해쉬 함수 를 아래와 같이 정의한다고 가정하자
H1(K)=K%15
위의 식의 근거로 이중해쉬의 2차 해쉬 함수를 결정하게 된다
H2(K)=1+(K%C)
위의 2차 해쉬 함수식이 절대적인 것은 아니지만 일반적인 형태이다.
이러한 식에서 C를 구해주는 방법은 1차 해쉬 함수를 %15로 결정한 것으로 보아 , 배열의 길이가 15라고 예상해 볼 수 있다 .
이와 같이 가급적 2차해쉬 값이 1차 해쉬 값을 넘어서지 않게 하기 위함은 1차 해쉬 최대값이 14인데 2차 해쉬의 최대 값이 32 라면 빈자리를 찾아서 몇 바퀴 돌아야 할 지 모르기 때문이다.
즉 위와 같은 경우 C는 15보다 작은 그러면서도 소수 중 하나로 결정을 하면된다.
여기서 C를 소수로 결정하는 이유는 소수 선택했을 시 클러스터 현상의 발생 확류를 현저히 낮춘다는 통계를 근거로 한다.
그리고 먼저 1을 더하는 이유는 2차 해쉬 값이 0이 되는 것을 막기 위해서이다.
위를 기준으로 2차함수를 H2(K)=1+(K%C) 로 한다는 전제하에 예를 들겠다.
예로 키 3 , 18 , 33 을 넣었을때 생기는 과정을 보여주겠다.
H1(3)=3%15=3
H1(18)=18%15=3
H1(35)=33%15=3
이러한경우 18 35는 해쉬 값이 같아서 충돌이 발생하므로 2차 해쉬 함수에 넣어준다
H2(18)=1+18%7=5
H2(33)=1+33%7=6
위 와 같이 1차 해쉬 값은 같아도 2차 해쉬 값은 다르다 그리고 이 2차 해쉬 값을 근거로 빈슬룻을 찾는 과정은 각각 다음과 같이 전개가 된다
H2(18) -> H2(18)+5*1 -> H2(18)+5 *2 -> H2(18)+ 5*3 .....
H2(33) -> H2(33) + 6*1 -> H2(33)+6*2 -> H2(33) +6*3 ....
위 와 같이 2차 해쉬 값의 크기만큼 건너 뛰면서 빈 슬룻을 찾게 되므로 키가 다르면 건너 뛰는 길이도 달라져서 클러스터 현상의 발생확률을 현저히 낮출 수 있다.
2. 닫힌어드레싱방법--충돌이 나도 반드시 그자리에 값을 집어 넣는다
체이닝
2-1. 배열기반
2-2. 링크드 리스트 기반
아래는 간단한 배열 기반 테이블 소스
package Datastructure;
import java.util.Scanner;
public class Tablearray {
int prinum;
int age;
public static void main(String[] args) {
Tablearray []ta= new Tablearray[1000];
Tablearray tmp;
Tablearray t= new Tablearray();
int searchnum;
Scanner sc = new Scanner(System.in);
System.out.println("사번입력:");
t.prinum=sc.nextInt();
System.out.println("나이 입력:");
t.age=sc.nextInt();
ta[t.prinum]=t;// 여기가 포인트
System.out.println(" 조회할 사번:");
searchnum=sc.nextInt();
tmp=ta[searchnum];
System.out.println("나이 :"+tmp.age +","+"검색 키:"+ tmp.prinum);
}
}
이중 해쉬를 구성할 시에 슬롯의 상태 정보를 별도로 관리 해야한다
그러한 이유는 예로 해싱 함수가 key% 7 인 경우로 예를 들겠다.
key 값이 9인 데이타의 해쉬 값은 2이다
그림 아래와 같이 9가 2에 들어가게 될것이다
9
|0 | 1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
이어서 키값이 2인 데이터 가 등장하면 똑같이 해쉬 값이 2가된다
여기서 선형조사법식으로 값을 넣는다면 아래와 같을 것입니다.
9 2
|0 | 1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
이러한 상태에서 9를 삭제한다고 한다면
아래와 같이 됩니다.
2
|0 | 1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
E E D I E E E E E E
슬롯의 상태는 아래와 같습니다.
EMPTY - 이 슬룻에는 데이터가 저장된 바가 없다.
DELETED -이 슬롯에는 데이터가 저장된바 있으나 현재는 비워진 상태이다.
INUSE - 이 슬룻에는 현재 유효한 데이터가 저장되어 있다.
슬롯의 상태를 주는 궁극적인 이유는 데이터가 삭제된 슬룻의 상태 정보를 DELETE로 두어 EMPTY 와 구분 하였다는 것입니다.
위와 같은 상황에서 키가 2인 데이터를 탐색을 진행하기 위해서는 %7의 해쉬 함수를 거친다. 그리고 그결과로 얻은 2를 인덱스 값으로 하여 탐색을 진행 하게 된다 . 만약에 그위치의 슬롯 상태가 EMPTY 라면 데이터가 존재하지 않는다고 판단 탐색을 종료 한다 . 그 옆자리를 확인 하지 않은 채 말이다.
반면 DELETED 상태임을 확인한다면 충돌이 발생했음을 의심하여 선형 조사법에 근거한 탐색의 과정 진행한다.
http://blog.daum.net/_blog/BlogTypeView.do?blogid=0MMaA&articleno=8039326&categoryId=719070®dt=20120915060134
체이싱
http://sowlgns.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%95%B4%EC%8B%B1