[ 자료구조 ] 해시 테이블 - 01 . 해시와 해시 테이블

[해시에 관하여]

[들어가기 전에]

1 . 이진 탐색이 아무리 빠르다 하더라도 인덱스를 이용 , 바로 목표 요소에 접근하는 배열에 비하면 아쉬운 점이 있다 .

만약 , 배열처럼  데이터 값을 이용하여 각 요소가 담길 주소를  계산하고 , 이 주소에 데이터를 담는다면 ?

 

2.해시는 해시 테이블 , 암호화 , 문자열 검색등 많은 알고리즘에 응용되는 알고리즘이다 . 그렇다면 해시란 ?

 

[해시]

Hash (해시)란 무엇일까?

영단어를 보면 , "잘게 자른 고기를 양파,감자와 같은 다른 재료와 함께 튀겨 한 덩어리로 만든 요리"를 뜻한다 .

이와 같이 해시는 데이터를 입력받으면 완전히 다른 모습의 데이터로 바꾸어 놓는 작업이다 .

 

해시는 다음의 용도로 쓰인다 .

• 해시 테이블 : 해시 테이블은 데이터의 해시값을 테이블 내의 주소로 이용하는 탐색 알고리즘이다 . 
• 암호화 : 해시는 입력받은 데이터를 완전히 새로운 모습의 데이터로 만든다 . 해시를 통해 변환된 데이터는 원본의    모습을 알아볼 수 없게 완전히 달라진다 . ex ) SHA(Secure Hesh Argorithm)
• 데이터 축약 : 해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다 . 이 특성을 이용 , 커다란 데이터를 "해시"하면 짧게 축약이 가능하다 . 이렇게 축약된 데이터끼리 비교를 수행하면 , 커다란 원본 데이터들의 비교에 비해 뛰어난 효율을 가질 수 있다 .

[해시 테이블]

[ 배열의 문제 ]

배열을 선언하면 메모리(스택 혹은 자유저장소)에 일정 크기의 메모리가 예약된다 .

배열 내의 각 요소는 0,1,2와 같은 인덱스로 접근 가능하다 . 하지만 특정 값의 탐색은 다음의 과정이 필요하다 .

 

ex)크기가 59999인 배열중 123817 이라는 데이터가 있는 요소에 접근한다면 ?

=>순차탐색 혹은 배열을 정렬후 이진탐색으로 찾아야 할 것이다 .

요즘 컴퓨터는 순식간에 해내겠지만 , 극한의 성능을 요구하는 분야 : 특히 금융쪽에서는 이런 성능은 용납하지 않는다 .

금융 컴퓨팅 분야에서 시간은 돈이다 . 이런 문제는 이진탐색으로도 해결 하지 못한다 .

 

[ 해결 : 해시 테이블 ]

해시테이블은 이 문제를 데이터를 해시해서 테이블내의 주소로 바꾸는 것으로 간단히 해결한다 .

데이터는 해시 함수를 거쳐 테이블내의 주소 (인덱스)로 변환된다 .

=>위와 같이 해시하여 얻은 값을 주소값(인덱스)으로 사용하면 된다 . ex ) Table [3819] = 123817 

=>데이터를 읽는 것 또한 마찬가지 이다 ex) printf(Table[3819]);     //123817 출력

 

=> 즉 , 해시 테이블은 데이터를 담을 테이블을 미리 크게 확보 , 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 ,이 주소에 데이터를 담는 것 .

 

=>해시를 통해 데이터가 담길 주소값을 얻는 것은 상수 시간내에 결정되기에 , 성능은 테이블 크기에 구애받지 않는다 .

 

=>그렇기에 해시 테이블에게  "탐색"이라는 단어가 무색하게 , 주소 (인덱스)를 구하는 방법만 다를뿐 배열과 다름없는 

요소에 대한 접근 속도를 자랑한다

 

=>다만 , 해시 테이블의 성능은 공간을 대가로 한 성능임을 알아야 한다 . (특이하게 , 해시 테이블은 데이터가 입력되지 않은 여유공간이 많아야 제 성능 유지가 가능하다 .)

 

[해시 함수]

[ 나눗셈법 ]

입력값을 테이블의 크기로 나누고 , 그 나머지를 테이블의 주소로 사용한다 .

(어떤 값이든 그 나머지는 테이블의 크기를 넘지 않는다 즉 , 0부터 n-1 사이 주소를 반환함을 보장한다 )

주소 =  입력값 % 테이블의 크기

int Hash(int Input , int TableSize)
{
	return Input % TableSize;
}

일반적으로 나눗셈 법으로 구현된 해시 함수가 테이블내의 공간을 효율적으로 사용하려면 ,

테이블의 크기를 n의 소수(Prime Number) , 특히 2의 제곱수와 거리가 먼 소수를 사용함이 좋은 성능을 낸다 .

ex)2의 7 승 (128)과 2의 8승 (256) 의 중간인 193

[ 나눗셈법의 구현 ]

해시 테이블이 배열의 인덱스 대신 해시한 주소를 사용하는 과정을 보여준다 .

해당 구현은 다음의 Node 구조체의 배열을 해시 테이블의 자료구조로 사용한다 .

Key는 주소로 사용할 데이터 / Value는 Key를 이용하여 얻어낸 주소에 저장할 데이터이다 .

(Key는 직접 주소가 아닌 해쉬 함수에넣어 계산될 값이다)

typedef struct tagNode
{
    KeyType Key;
    ValueType Value;
}Node;

[ SHT.h ]

#ifndef SHT_H
#define SHT_H

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

typedef int KeyType;
typedef int ValueType;

//해시 테이블의 자료구조로 이용되는 배열의 구조체
typedef struct tagNode
{
	KeyType Key;
	ValueType Value;
}Node;

//해시 테이블
typedef struct tagHashTable
{
	int TableSize;
	Node* Table;
}HashTable;


//해시 태이블의 생성
HashTable* SHT_CreateHashTable(int TableSize);
//키를 해시하여 테이블의 해당 인덱스에 값을 넣는다
void SHT_Set(HashTable* HT, KeyType Key, ValueType Value);
//키를 해시하여 테이블의 해당 인덱스의값을 받는다
ValueType SHT_Get(HashTable* HT, KeyType Key);
//해시테이블 삭제
void SHT_DestroyHashTable(HashTable* HT);
//해시 : 키를 받아 변형 , 주소값을 만든다
int SHT_Hash(KeyType Key, int TableSize);


#endif // !SHT_H

[ SHT.cpp ]

#include"SHT.h"

//해시 태이블의 생성
HashTable* SHT_CreateHashTable(int TableSize)
{
	HashTable* HT = (HashTable*)malloc(sizeof(HashTable));
	HT->Table = (Node*)malloc(sizeof(Node) * TableSize);
	HT->TableSize = TableSize;
	return HT;
}
//키를 해시하여 테이블의 해당 인덱스에 값을 넣는다
void SHT_Set(HashTable* HT, KeyType Key, ValueType Value)
{
	int Address = SHT_Hash(Key, HT->TableSize);
	HT->Table[Address].Key = Key;
	HT->Table[Address].Value=Value;
}
//키를 해시하여 테이블의 해당 인덱스의값을 받는다
ValueType SHT_Get(HashTable* HT, KeyType Key)
{
	int Address = SHT_Hash(Key, HT->TableSize);
	return HT->Table[Address].Value;
}
//해시테이블 삭제
void SHT_DestroyHashTable(HashTable* HT)
{
	free(HT->Table);
	free(HT);
}
//해시 : 키를 받아 변형 , 주소값을 만든다
int SHT_Hash(KeyType Key, int TableSize)
{
	return Key % TableSize;
}

[ Test.cpp ]

#include"SHT.h"

int main(void)
{
	//해시테이블의 크기는 2의 제곱수에서 멀은 소수가 좋다.
	HashTable* HT = SHT_CreateHashTable(193);

	SHT_Set(HT, 418, 32114);
	SHT_Set(HT, 9, 514);
	SHT_Set(HT, 27, 8917);
	SHT_Set(HT, 1031, 286);
	printf("Key : %d , Value : %d \n", 418, SHT_Get(HT, 418));
	printf("Key : %d , Value : %d \n",9, SHT_Get(HT, 9));
	printf("Key : %d , Value : %d \n", 27, SHT_Get(HT,27));
	printf("Key : %d , Value : %d \n", 418, SHT_Get(HT,1031));

	SHT_DestroyHashTable(HT);
	return 0;



}

 

 

[자리수 접기]

[나눗셈법의 문제]

나눗셈법은 서로 다른입력값에 대해 동일한 해시값 , 즉 해시테이블내의 동일한 주소를 반환할 가능성이 높다 .

이를 충돌이라고 한다 .

 

혹은 , 같은 해시값이 아니더라도 해시 테이블 내의 일부 지역의 주소들은 집중적으로 반환하는 결과로 데이터들이

한 곳에 모이는 문제가 발생할 가능성이 높다 . 이를 클러스터라고 한다 .

 

이 둘의 문제를 완벽히 해결은 어렵지만 줄여주는 가능성을 줄여주는 알고리즘이 몇가지 존재한다 .

이중 하나가 자릿수 접기이다 .

 

[자릿수 접기]

자릿수접기는 종이를 접듯 숫자를 접어 일정한 크기 이하의 수로 만드는 방법이다 .

ex ) 8129335

• 한자리 접기 : 8+1+2+9+3+3+5 =31
• 두자리 접기 : 81+29+33+5 = 148

이처럼 숫자의 각 자릿수를 더해 해시값을 만드는 것을 자릿수 접기라 한다 .

나눗셈법처럼 일정한 범위내의 해시값을 얻을 수 있다 .

ex) 7자리수의 한자리 접기 :7+7+7+7+7+7+7 = 63 최대 63까지 값을 가진다 .

      7자리 수의 두자리 접기 : 99 + 99+ 99 + 9 306까지의 해시값.

 

[자릿수 접기와 문자열]

자릿수접기는 문자열을 키로 사용하는 해시테이블에 잘 어울린다 . 문자열의 각 ASKIII 코드 번호(0 -127)

로 바꾸고 , 이 값들을 각각 더하여 접으면 문자열을 해시테이블내의 주소로 바꿀 수 있다 .

int Hash(char* Key , int KeyLength , int TableSize)
{
	int i=0;
    int HashValue=0;
    
    //문자열의 각 요소를 ASCII 코드 번호로 변환하여 더한다
    for(i=-;i<KeyLength;i++)
    	HashValue+=Key[i];
        
    return HashValue % TableSize;
}

[자릿수 접기의 문제]

해시 테이블의 크기가 12289 이고 문자열의 최대 길이가 10자리이고 한자리 접기를 한다면

해시 함수는 10 * 127 = 1270 이므로 (ASCII 코드이기에 각 자리는 127가지의 값을 가질 수 있다 .)

 

0부터 1270 사이의 주소만 반환하고 , 1271 ~ 12288 사이의 주소가 전혀 활용이 되지 않는다 .

또한 , ASCII 코드로 10 자리를 만들었을때 조합 가능한 경우의 수는 127의 10승 = 1,091,533,853,073,393,531,649

가지 임을 감안하면 이는 심각한 문제이다 .

 

다시 보자면 , 테이블의 크기 12289는 2진수로 표현하면 11000000000001이다 . 이는 총 14개의 비트로 이루어져 있다 .

반면 , 우의 Hash 함수의 반환값인 1270은 10011110110으로 11 비트만을 사용한다 .이를 미루어 봤을때 , 

테이블의 주소중 3개의 비트는 사용되지 않음을 알 수 있다 .

 

만약 이 비트 3개를 활용한다면 앞의 문제는 해결 할 수 있을 것이다 .

 

[해결]

해결은 Hash()함수가 남는 비트까지 모두 활용 할 수 있게 만들면 된다 .

Hash()함수는 루프가 반복될때마다 HashValue를 왼쪽으로 3비트씩 밀어올려 다음 ASCII 코드 번호를 더한다 .

이론적으로는 해시 테이블 내의 모든 주소를 해싱 할 수 있고 , 결과적으로는 해당 문제를 해결 할 수있다 .

int Hash(KeyType Key , int KeyLength , int TableSize)
{
	int i=0;
    int HashValue=0;
    
    for(i =0;i<KeyLength;i++)
    {
    	HashValue = (HashValue << 3) + Key[i];
    }
    
    return HashValue % TableSize;
}