◎ 해싱에대해서?
○ 해싱이란?
해시 함수를 이용하여 키 값을 위치로 변환하고 이를 이용해
저장된 자료를 바로 찾아가는 계산 검색 방식이다.
값의 연산에 의해 직접 접근이 가능한 구조를 해시테이블(hash table)
해시테이블을 이요한 탐색을 해싱(hashing)
○ 해싱구조..
레코드 키들의 집합을 버켓주소의 집합에 대응시킨다는 의미에서 사상함수라 한다.
가장 이상적인 해싱 함수는 키 집합의 한 레코드와 버켓 주소 집합의 한 레코드가
1 : 1 대응하여 해시 테이블의 정해진 범위에 고르게 분포되어 있는것을 뜻함.
-저장 및 검색 과정-
키 값 –> 해싱 함수 –> 해시 주소(버킷 주소) –> 해시 테이블
해싱 함수 구현부분-
----------------------------------------------------------------------------------------
public static int hash(Object key) // hashing method >> private
{
int sum = 0;
byte compare[] = null;
compare=((String)key).getBytes(); // 문자열을 바이트로 환산해주는 메서드 >> 리턴값 : 배열
for(int i=0;i<((String)key).length();i++)
{
sum+=(int)compare[i];
}
int h=(sum & 0x7FFFFFFF) % capacity;
return h;
}
------------------------------------------------------------------------------------------
○ 해시 테이블
해상함수로부터 계산된 함수값에 해당하는 위치에 각 레코드를 한 개 이상 보관할 수 있는
버켓들로 구성된 기억 공간이며, 주어진 key값을 가지고 해당 레코드를 빠르게 검색하기 위한
수단을 제공하며 레코드의 삽입과 삭제를 용이하게 한다.
해시 테이블은 크기가 파일보다 커야한다. n개의 레코드에 대해 n개의 해쉬 주소를 생성
하는 해쉬 함수를 찾는것은 불가능 하기 때문.
일반적으로 부하율(load factor) 75%이상이면 일정의 테이블 공간을 늘려주는 것이 좋다.
그이상의 급격하게 성능 저하가 발생!!
○ 버켓
일종의 자료구조로 해싱함수에 의해 계산된 주소인 홈 주소에 레코드를 저장하기 위해 마련된 기억공간.
○ 해싱함수란?
탐색 키를 간단화하는 함수를 해싱 함수(hashing function) 라 하며,
탐색 키를 받아서 해시 주소를 생성하는 기능을 한다.
이 해시 주소가 바로 간단화된 탐색 키라고 할 수 있고. 자리수가 몇 안 되는 정수이고 곧 배열의 번호이다.
※ 좋은 해시 함수 조건
- 주소 계산이 빠르게 구해져야 한다.
- 서로 다른 레코드의 계산된 값이 가급적 중복되지 안하야 한다(충돌이 적어야한다)
○ 해싱함수의 종류
-제산법(Division) : 나머지 연산자(%)를 사용하여 테이블 주소를 계산하는 방법!!
＊ 버켓주소 = 키 값 % 해쉬테이블 크기
-제곱법(Mid-Saure) : 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를
선택하여 해시 테이블의 홈 주소로 사용, 심볼 테이블 응용에서 자주 사용
＊ k = 35270 제곱시 테이블의 크기가 10,000일때(중간 4비트선택)
11243972900 -> 1243ㅣ9729ㅣ00 -> 9729가 주소값
-숫자 분석법(Digit-Analysis) : 레코드 모든키들 내에서 각 자리별로 어떤 분포인지 조사하여
비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 사용
* 정적 파일에 유효, In/out 빈번히 발생할경우 비효율적
-폴딩법(Folding) : 레코드 키의 마지막 부분을 제외한 모든 길이가 동일하게 여러부분으로 나누고
이를 모두 더하거나 배타적 노리합을 취하여 홈주소로 이용하는 방법
탐색키 : 123ㅣ203ㅣ241ㅣ112ㅣ20
＊이동폴딩 : 각부분의 값을 계산하기 위해 마지막을 제외한 모든 부분을 이동시
최하위 비트가 마지막 부분의 자리와 일치하도록 우측끝을 맞추어 더한 값
123+203+241+112+20 =699
＊경계폴딩 : 나누어진 각 부분의 경계선을 종이 접듯이 접어 역으로 정렿한 다음 더한 값
123+302+241+211+20=897
- 기수변환법 , 무작위 방법 등이 있음
○ OverFlow 해결
- 선형조사법,이차조사법,이중해싱법,체이닝 의 방법 사용 (선형법과 체이닝 많이사용)
＊ 선형 조삽법(선형 개방 주소법) : 충돌이 일어난 키값을 다른 비어있는 버킷을 찾아 저장한다.
이 때 비어있는 버킷은 순차적으로 찾는다
＊ 체이닝(Chaining) : 오버플로우 문제를 연결 리스트로 해결
각 버켓에 고정된 슬롯을 할당하는 것이 아니라 각 버켓에, 삽입과 삭제가
용이한 연결리스트를 할당
버켓내에서는 원하는 항목을 찾을때는 연결리스트를 순차 탐색!
○ 동적 해싱법
해시 테이블 대신에 트라이라는 자료구조 사용
트라이 : 입력키의 각 비트값에 따라 2개의 가지로 분리되도록 만들어진 것
키 값의 맨 오른쪽 비트부터 검사 하여 0일경우 첫번째 레벨의 위쪽 1일경우 아래쪽 으로 분기
끝에서 두번째 비트를 검사하여 그값이 0이면 두번째 레벨의 위쪽 1이면 아래쪽으로 분기
......순차적으로 오른쪽에서 왼쪽으로 키값을 비교해 나가면서 분기한다.,
------------------------------------------------------------------------------------------------------------------------
구현
----Entry Class---------------------------------------------------------------------------------------------------------
public class Entry
{
public Object key, value; //key,value 필드 분리
public Entry next; // Node 개념 적용 - 자기 참조
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
}
public Object getKey() { //key 리턴
return key;
}
public Object getValue() { //value 리턴
return value;
}
public void setValue(Object value) { //value 설정
this.value = value;
}
}
----HashTable Class----------------------------------------------------------------------------------------------------
public class HashTable
{
private static final int CAPACITY = 10; //기본테이블 크기
private static int capacity;
public Entry[] hTable; // 해쉬테이블은 배열로 구성되어 있고 각각의 배열에는 엔트리가 들어감
public HashTable(int capacity) // 파라미터가 테이블 용량을 넘겨줄경우 생성자
{
this.capacity = capacity;
hTable = new Entry[capacity]; // 테이블 크기만큼 엔트리 생성 해서 해쉬 테이블 생성
}
public HashTable() // 파라미터가 없을경우
{
this(CAPACITY); // 기본값 크기로
}
public static int hash(Object key) // hashing method >> private
{
int sum = 0;
byte compare[] = null;
compare=((String)key).getBytes(); // 문자열을 바이트로 환산해주는 메서드 >> 리턴값 : 배열
for(int i=0;i<((String)key).length();i++)
{
sum+=(int)compare[i];
}
int h=(sum & 0x7FFFFFFF) % capacity;
return h;
}
public void put(Object key, Object value) // 넣기
{
int h = hash((String)key); // key 값으로 해싱
Entry cur = hTable[h]; // 해싱값에 해당하는 배열칸값
Entry entry = new Entry(key, value); // 엔트리 형성
if (hTable[h] == null) //
{
hTable[h] = entry; // 입력된 값 저장
}
else { // 해시값 충돌시
while (cur.next != null)// 노드 끝까지
{
if(cur.getKey().equals(key)) // 혹시나 키값이 같은 자료 입력을 시도랬다면
{
cur.setValue(value); // 해당엔트리의 자료값만 변경
break; // 그다음 끝냄
}
cur = cur.next; // 리스트가 끝날때까지 next 로 찾아감
}
cur.next = entry; // 리스트의 끝에 입력된 엔트리 달기
}
}
public void searchMap(Object word) // 검색 메서드
{
int flag = 0; // 결과 상태
Object result = null; // 결과값
Entry cur = hTable[hash(word)];
if (cur == null)
flag = 0;
else
{
while(cur != null)
{
if (cur.getKey().toString().equals((String)word))
{
flag = 1;
result = cur.getValue(); break;
}
else
cur = cur.next;
}
}
//검색결과 출력
if (flag == 0 ) System.out.println("검색결과가 없습니다.");
else System.out.println("검색결과가 있으며 값은 " + (String)result + " 입니다.");
}
public void printMap() // 출력
{
Entry cur; // 출력할 엔트리를 '포인팅' 하기 위해 정의한 변수
for(int i=0; i<capacity; i++) // 테이블 크기 수 만큼
{
System.out.print("|"+i+"|\t");
cur = hTable[i]; // i번 배열에 있는 엔트리를 받아오기
if((cur == null)) // 비어있을경우
System.out.print("null"); // null 출력
else
{
while(cur != null)
{ // 엔트리 끝이 더이상 없을 때까지
System.out.print("Key : "+ cur.getKey() +" Value : "+ cur.getValue()+" "); // 현재 엔트리의 키값과 자료값을 불러와 출력
cur = cur.next; // 다음번 엔트리로 넘어가기
}
}
System.out.println(""); // 줄바꾸기
}
}
}
----Testinput Class-----------------------------------------------------------------------------------------------------
public class Testinput
{
public static void clearScreen() // 화면 초기화
{
for (int i = 0; i < 80; i++)
System.out.println("");
}
public static void main(String[] args) throws IOException
{
HashTable map2 = new HashTable();
int msel;
String con; // 계속 여부
do
{
//clearScreen();
System.out.println("메뉴를 선택하세요");
System.out.println("1. 입력");
System.out.println("2. 출력");
System.out.println("3. 검색");
System.out.println("4. 종료");
BufferedReader ar = new BufferedReader(new InputStreamReader(System.in));
msel =Integer.parseInt(ar.readLine());
switch (msel)
{
case 1: // 입력
{
System.out.println("key : ");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String b=br.readLine().toString();
System.out.println("value : ");
BufferedReader cr = new BufferedReader(new InputStreamReader(System.in));
String c=cr.readLine().toString();
map2.put(b,c);
break;
}
case 2: // 출력
{
map2.printMap();
break;
}
case 3: // 검색
{
System.out.println("search : ");
BufferedReader dr = new BufferedReader(new InputStreamReader(System.in));
String d=dr.readLine().toString();
map2.searchMap(d);
break;
}
case 4: // 종료
{
return;
}
}
} while (true);
}
}
----TestChaining Class--------------------------------------------------------------------------------------------------
public static void main(String[] args)
{
HashTable map1 = new HashTable(); // 첫번째 맵 형성
map1.put("태희","011-234-5348"); // 자료입력
map1.put("미","011-214-7678");
map1.put("동훈","015-434-8378");
map1.put("종훈","011-2674-5878");
map1.put("Hut","016-214-2678");
map1.put("Ohr","013-134-1678");
System.out.println("map1 is ");
map1.printMap(); // 자료출력
map1.searchMap("Ohr");
map1.searchMap("종훈");
//System.out.println(map1.hash("Tor"));
//System.out.println(map1.hash("Rad"));
HashTable map55 = new HashTable();
map55.put("a","1234");
map55.put("b","3456");
map55.put("c","9874");
map55.put("d","5478");
map55.searchMap("c");
}
}
------------------------------------------------------------------------------------------------------------------------LRU 기법? 주기억장치에 저장된 시점과 관계없이, 사용률이 가장 저조한 페이지를 교체하는것!
'자료구조' 카테고리의 다른 글
| 자료구조(Stack 과 Queue) (0) | 2009.11.06 |
|---|---|
| 자료구조 ( Array와 Linked List)- (0) | 2009.11.06 |