[ 자료구조 ] 해시 테이블 - 03 . 개방 주소법

[ 개방 주소법 ]

[ 개방 주소법 ]

개방 주소법 (Open Addressing)은 충돌이 일어날 떄 해시 함수에 의해 얻어진 주소가 아니라

다른 주소를 사용하게 허용하는 충돌해결 알고리즘이다 . 충돌이 일어나면 해시 테이블 내의 새로운

주소를 탐사 (Probe)하여 충돌된 데이터를 입력하는 방식으로 동작한다  .

 

cf ) 체이닝은 오픈 해싱기법이자 폐쇄 주소법(Closed Addressing) 알고리즘이기도 하다 .

 

탐사방식은 다음과 같이 나뉜다

• 선형탐사
• 제곱탐사
• 이중해싱

 

[ 선형 탐사 ]

가장 간단한 탐사방법이다 . 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 있다면 , 해당 주소에서

고정폭 (1,2 .. )으로 빈 곳을 찾을때까지 다음 주소로 이동한여 찾는다면 그곳에 데이터를 입력한다 .

 

ex)크기가 13 나눗셈법 기반의 해시 함수를 이용하는 해시 테이블을 가정하자 .

1. 42 입력 : 42%13 =3 이므로 3번째 요소에 입력
2. 55 입력 :  55%13 =3 으로 42와 겹치므로 고정폭(1)만큼 이동 , 4번째 요소에 입력 
3. 81 입력 : 81%13=3 으로 42와 겹치므로 고정폭 이동 , 55가 있으니 고정폭 다시 이동 , 5번째 요소에 입력

=>그림처럼 해시 테이블에 삽입된 데이터들이 모이는 "클러스터" 현상이 매우 잘 발생한다 .

 [1차 클러스터링 : 레코드들이 연속된 위치를 점유하여 클러스터를 형성하고 이것이 점점 더 커짐]

이로 인해 새로운 주소를  찾기 위해 수행하는 선형 탐사의 시간이 길어지고 , 성능은 저하되게 된다 .

이를 해결한게 제곱 탐사이다 .

 

[ 제곱 탐사 ]

선형 탐사와 같지만 , 고정폭만큼의 이동이 제곱수만큼의 이동으로 늘어나는게 차이점이다 .

 

ex)크기가 13 나눗셈법 기반의 해시 함수를 이용하는 해시 테이블을 가정하자 .

1. 42 입력 : 42%13 =3 이므로 3번째 요소에 입력 
2. 55 입력 :55%13 =3 으로 42와 겹치므로 "제곱수"(첫 탐사는 1의 제곱수 =1 )만큼 이동
3. 81 입력 : 81%13=3 으로 42와 겹치므로 "제곱수"(두번째 탐사는 2의 제곱수 = 4 )만큼 이동
4. 109 입력 : 109%13은 6이므로 충돌없이 자기 자리를 찾는다 .

=>여기까지 봤을때는 클러스터로부터의 해방 같지만 , 제곱수의 폭으로 이동한다는 규칙은

또 다른 종류의 클러스터가 발생한다 .

(이해한 바로는 규칙이 있기에 같은 해시값에서는 값이 늘어날수록 탐사가 늘어남을(계속 다음 제곱으로 이동) 야기함)

 

5.107 입력 : 107%13 =3 으로 자리를  "제곱수"(세번째 탐사는 3의 제곱수 = 49)만큼 이동

 

=>이유는 한 주소에서 충돌이 발생하면 탐사할 위치가 정해져 있기 떄문이다 .

즉, 제곱 탐사는 서로 다른 해시값을 갖는 데이터에 대해서는 클러스터가 형성 되지 않는 효과가 어느정도 있지만 ,

같은 해시값을 갖는 데이터에 대해서는 2차 클러스터를 형성하기 떄문이다 .

[2차 클러스터링: 두 키의 홈 위치가 동일하면 이후 전체 탐사 순서가 동일하게 됨]

 

 

[ 이중 해싱 ]

클러스터를 제대로 방지하려면 탐사할 주소의 규칙성을 없애는 길뿐이다 .

 

만약 rand함수를 사용하여 얻은 난수값을 이동폭으로 삼는다면 ? 

=>같은 키를 입력하면 항상 같은 해시값(주소)를 얻어야 하는데 항상 다른 값을 얻을 것이다

 

그렇다면 이동폭을 제2 해시 함수로 계산한다면 ?

=>탐사 이동폭의 규칙성은 없애지만 같은 키에 대해 항상 같은 값을 얻을 수 있다 .

 

ex)크기가 13 나눗셈법 기반의 해시 함수를 이용하는 해시 테이블을 가정하자 .

이 해시 테이블은 두개의 해싱 함수가 존재한다 .

• 최초의 주소 계산 Hash1()

int Hash1(int Key)
{
	return Key % 13;
}

 

 

• 충돌 발생시 탐사 이동폭 계산 Hash2()

int Hash2(int Key)
{
	return (Key % 11) +2 ;
}

 

 

1. 42 입력 : 42%13 =3 이므로 3번째 요소에 입력 
2. 55 입력 :55%13 =3 으로 42와 겹치므로 Hash2()로 받은 2를 더한 5로 이동 .
3. 81 입력 : 81%13=3 으로 42와 겹치므로  Hash2()로 받은 6를 더한 9로 이동 .
4. 109 입력 : 109%13은 6이므로 충돌없이 자기 자리를 찾는다 .

=>제곱 탐사에서는 81 입력시 42에서 충돌 ,55에서 충돌 총 두번의 충돌이 일어났다.

반면 이중해싱으로 곧바로 자기 자리를 찾아갔다 . 이렇듯 이중 해싱은 2차 클러스터를 효과적으로 방지 ,

해시 테이블의 성능을 유지한다 .

 

    5 .224 입력 : 224%13은 3이므로 42와 충돌 ,  Hash2()로 받은 6를 더한 9로 이동 . 다시 81과 충돌 6만큼의 이동으로

    마지막 주소인 12를 지나친 15로 이동 . 끝을 넘어가면 처음부터 탐사를 시작해 2로 이동한다 .

 

 

[ 재해싱 ]

아무리 성능이 뛰어난 충돌 해결 알고리즘도 해시 테이블의 여유공간이 차버려 발생하는 성능저하

(연쇄충돌이 계속 일어나기에)는 당해낼 방법이 없다 .

 

재해싱(Rehashing)은 이를 해결하기 위한 좋은 방법이다 .

해시 테이블의 크기를 늘리고 , 늘어난 테이블의 크기에 맞춰 테이블 내의 모든 데이터를 다시 해싱한다 .

 

통계적으로는 공간 사용률이 70 % ~ 80 %이 되면 성능 저하가 나타나기에 이전에 수행해야 성능 저하를 막을 수 있다 .

다만 , 재해싱 역시 만만찮은 오버헤드를 요구하기에 75 % 정도를 임계치로 설정하는게 보통이다 

[ 개방 주소법 예제 ]

[ OAHT.h ]

#ifndef OPEN_ADDRESSING_H
#define OPEN_ADDRESSING_H
#define _CRT_SECURE_NO_WARNINGS


#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//키와 밸류
typedef char* KeyType;
typedef char* ValueType;

//노드의 상태
enum ElementStatus
{
	EMPTY=0,
	OCCUPIED=1
};

//노드
typedef struct tagElementType
{
	KeyType Key;
	ValueType Value;

	ElementStatus Status;
}ElementType;

//해시 테이블
typedef struct tagHashTable
{
	tagElementType* Table;

	int OccupiedCount;
	int TableSize;
}HashTable;

//해쉬 테이블의 생성
HashTable* OAHT_CreateHashTable(int TableSize);
//해쉬 테이블의 삭제
void OAHT_DestroyHashTable(HashTable* HT);
//내부 배열의 삭제
void OAHT_ClearElement(ElementType* Element);

//해시 테이블에 데이터를 입력
void OAHT_Set(HashTable** HT, KeyType Key, ValueType Value);
//해시 테이블에서 데이터를 가져옴
ValueType OAHT_Get(HashTable* HT, KeyType Key);

//해싱
int OAHT_Hash(KeyType Key, int KeyLength, int TableSize);
//더블 해싱
int OAHT_Hash2(KeyType Key, int KeyLength, int TableSize);
//재해싱
void OAHT_Rehash(HashTable** HT);

#endif // !OPEN_ADDRESSING_H

[ OAHT.cpp ]

#include"OAHT.h"

//해쉬 테이블의 생성
HashTable* OAHT_CreateHashTable(int TableSize)
{
	HashTable* HT = (HashTable*)malloc(sizeof(HashTable));

	HT->Table = (ElementType*)malloc(sizeof(ElementType) * TableSize);
	memset(HT->Table, 0, sizeof(ElementType) * TableSize);

	HT->OccupiedCount = 0;
	HT->TableSize = TableSize;

	return HT;
}
//해쉬 테이블의 삭제
void OAHT_DestroyHashTable(HashTable* HT)
{
	//각 링크드 리스트를 자유 저장소에서 제거하기
	for (int i = 0; i < HT->TableSize; i++)
	{
		OAHT_ClearElement(&HT->Table[i]);
	}
	//해시 테이블을 자유 저장소에서 제거하기
	free(HT->Table);
	free(HT);
}
//내부 배열의 삭제
void OAHT_ClearElement(ElementType* Element)
{
	if (Element->Status == NULL)
		return;

	free(Element->Key);
	free(Element->Value);
}

//해시 테이블에 데이터를 입력
void OAHT_Set(HashTable** HT, KeyType Key, ValueType Value)
{
	int KeyLen, Address, StepSize;
	double Usage;

	Usage = (double)(*HT)->OccupiedCount / (*HT)->TableSize;

	//사용률이 50 %를 넘는다면 재해싱을 수행한다
	if (Usage > 0.5)
	{
		OAHT_Rehash(HT);
	}

	//키의 길이
	KeyLen = strlen(Key);
	//주소
	Address = OAHT_Hash(Key, KeyLen, (*HT)->TableSize);
	//탐색이동폭
	StepSize = OAHT_Hash2(Key, KeyLen, (*HT)->TableSize);

	// 1차 해싱후 구한 Address가 이미 점유되어 있고, 키 값이 다른 경우 -> 충돌이 일어난 경우
	// 2차 해싱값을 더한 주소를 탐색한다
	while ((*HT)->Table[Address].Status != EMPTY && strcmp((*HT)->Table[Address].Key, Key) != 0)
	{
		printf("충돌 발생! 키는 (%s) , 주소는 (%d) , 탐사 이동폭은 (%d)\n", Key, Address, StepSize);
		printf("발생지의 키는 (%s) , 주소는 (%d) \n", (*HT)->Table[Address].Key, Address);

		//다음 주소를 탐색한다 . TableSize로 나누는 이유는 이동폭이 사이즈 넘어갔을때를 위해서
		Address = (Address + StepSize) % (*HT)->TableSize;
	}
	//키만큼 할당후 , 키 값을 넣어준다
	(*HT)->Table[Address].Key = (char*)malloc(sizeof(char) * (strlen(Key) + 1));
	strcpy((*HT)->Table[Address].Key, Key);
	//Value만큼 할당후 , Value 값을 넣어준다
	(*HT)->Table[Address].Value = (char*)malloc(sizeof(char) * (strlen(Value) + 1));
	strcpy((*HT)->Table[Address].Value, Value);

	//테이블의 상태를 차있음으로 변경한다
	(*HT)->Table[Address].Status = OCCUPIED;
	//테이블의 점유 개수를 더해준다
	(*HT)->OccupiedCount++;

	printf("Key (%s) entered at address (%d)\n", Key, Address);
}
//해시 테이블에서 데이터를 가져옴
ValueType OAHT_Get(HashTable* HT, KeyType Key)
{
	int KeyLen = strlen(Key);

	int Address = OAHT_Hash(Key, KeyLen, HT->TableSize);
	int StepSize = OAHT_Hash2(Key, KeyLen, HT->TableSize);

	//테이블이 비어있지 않고 , 키 값이 같을때까지 (원하는 값을 찾을때까지 )
	while (HT->Table[Address].Status != EMPTY && strcmp(HT->Table[Address].Key, Key) != 0)
	{
		Address = Address + StepSize % HT->TableSize;
	}
	//찾은 값을 보낸다 .
	return HT->Table[Address].Value;
}

//해싱 - 1차 해싱으로 주소값을 보낸다
int OAHT_Hash(KeyType Key, int KeyLength, int TableSize)
{
	int i = 0;
	int HashValue = 0;

	for (i = 0; i < KeyLength; i++)
	{
		HashValue = (HashValue << 3) + Key[i];
	}
	//자릿수 접기
	HashValue = HashValue % TableSize;

	return HashValue;
}
//더블 해싱 - 2차 해싱으로 충돌시 이동폭을 정한다
int OAHT_Hash2(KeyType Key, int KeyLength, int TableSize)
{
	int i = 0;
	int HashValue = 0;

	// 2차 해싱 함수 - 1차 해싱함수와 같은 값을 갖지 않도록 만듬.
	//  ~ Cluster 현상과 Collusion 방지
	for ( i = 0; i < KeyLength; i++)
	{
		HashValue = (HashValue << 2) + Key[i];
	}
	//나머지 연산으로 같은 값을 갖지 않도록 테이블의 크기에서 3을 뺀 수로 나눈다
	HashValue = HashValue % (TableSize - 3);

	return HashValue + 1;
}
//재해싱
void OAHT_Rehash(HashTable** HT)
{
	int i = 0;
	ElementType* OldTable = (*HT)->Table;
	//새로운 해시 테이블을 만든다
	HashTable* NewHT = OAHT_CreateHashTable((*HT)->TableSize * 2);
	printf("\nRehashed . New Table size is %d\n\n ", (*HT)->TableSize * 2);

	for (int i = 0; i < (*HT)->TableSize; i++)
	{
		if (OldTable[i].Status == OCCUPIED)
		{
			OAHT_Set(&NewHT, OldTable[i].Key, OldTable[i].Value);
		}
	}

	OAHT_DestroyHashTable((*HT));

	(*HT) = NewHT;
}

[ Test.cpp ]

#include"OAHT.h"

int main(void)
{
	HashTable* HT = OAHT_CreateHashTable(11);

    OAHT_Set(&HT, (KeyType)"MSFT", (KeyType)"Microsoft Corporation");
    OAHT_Set(&HT, (KeyType)"JAVA", (KeyType)"Sun Microsystems");
    OAHT_Set(&HT, (KeyType)"REDH", (KeyType)"Red Hat Linux");
    OAHT_Set(&HT, (KeyType)"APAC", (KeyType)"Apache Org");
    OAHT_Set(&HT, (KeyType)"ZYMZZ", (KeyType)"Unisys Ops Check");
    OAHT_Set(&HT, (KeyType)"IBM", (KeyType)"IBM Ltd.");
    OAHT_Set(&HT, (KeyType)"ORCL", (KeyType)"Oracle Corporation");
    OAHT_Set(&HT, (KeyType)"CSCO", (KeyType)"Cisco Systems, Inc.");
    OAHT_Set(&HT, (KeyType)"GOOG", (KeyType)"Google Inc.");
    OAHT_Set(&HT, (KeyType)"YHOO", (KeyType)"Yahoo! Inc.");
    OAHT_Set(&HT, (KeyType)"NOVL", (KeyType)"Novell, Inc.");

    printf("\n");
    printf("Key:%s , Value:%s\n", "MSFT", OAHT_Get(HT, (KeyType)"MSFT"));
    printf("Key:%s , Value:%s\n", "REDH", OAHT_Get(HT, (KeyType)"REDH"));
    printf("Key:%s , Value:%s\n", "APAC", OAHT_Get(HT, (KeyType)"APAC"));
    printf("Key:%s, Value:%s\n", "ZYMZZ", OAHT_Get(HT, (KeyType)"ZYMZZ"));
    printf("Key:%s , Value:%s\n", "JAVA", OAHT_Get(HT, (KeyType)"JAVA"));
    printf("Key:%s  , Value:%s\n", "IBM", OAHT_Get(HT, (KeyType)"IBM"));
    printf("Key:%s , Value:%s\n", "ORCL", OAHT_Get(HT, (KeyType)"ORCL"));
    printf("Key:%s , Value:%s\n", "CSCO", OAHT_Get(HT, (KeyType)"CSCO"));
    printf("Key:%s , Value:%s\n", "GOOG", OAHT_Get(HT, (KeyType)"GOOG"));
    printf("Key:%s , Value:%s\n", "YHOO", OAHT_Get(HT, (KeyType)"YHOO"));
    printf("Key:%s , Value:%s\n", "NOVL", OAHT_Get(HT, (KeyType)"NOVL"));

    OAHT_DestroyHashTable(HT);
	return 0;

}