-
해시에 대하여
해시는 다양한 목적으로 사용될 수 있지만, 주로 다음과 같은 용도로 사용된다.
- 해시 테이블 : 해시테이블은 데이터의 해시 값을 테이블 내의 주소로 이용하는 궁극의 탐색 알고리즘이다. 빠르다고 정평이 나있는 이진 탐색보다도 빠르다.
- 암호화 : 해시는 입력받은 데이터를 완전히 새로운 모습의 데이터로 만든다. 해시를 통해 변환된 데이터는 원본의 모습을 알아볼 수 없을 정도로 완전히 달라진다. 이 특성 때문에 해시는 암호화 영역에서 아주 주요하게 사용되고 있다. SHA(Secure Hash Algorithm)알고리즘이 그 대표적인 예이다.
- 데이터 축약 : 해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다. 이 특성을 이용하면 커다란 데이터를 '해시'하면 짧은 길이로 축약할 수 있다. 이렇게 축약된 데이터끼리 비교를 수행하면 커다란 원본 데이터들을 비교하는 것에 비해 엄청난 효율을 거둘 수 있다.
-
해시 테이블: 공간을 팔아 시간을 사다
정렬되어 있지 않는 데이터 집합에서 원하는 값을 찾기 위해서는 정렬을 하고 이진 탐색을 하면 빠르게 탐색할 수 있을 것이다.
하지만 극한의 성능을 요구하는 분야에서는 이런 성능조차 용납되지 않는다.
해시 테이블은 아주 간단한 개념을 도입해서 이 문제를 해결할 수 있다. 바로 데이터를 '해시(잘게 부수고 다시 뭉쳐서)' 해서 테이블 내의 주소로 바꾸는 것이다.
데이터는 해시 함수를 거치면 다음 그림처럼 테이블 내의 주소(즉, 인덱스)로 변환된다.
123817을 해시하여 얻은 주소값은 3819이므로 table 내의 해당 주소(인덱스)에 데이터를 저장하면 된다. table[3891] = 123817;
테이블에 저장되어 있는 데이터를 읽는 것 역시 마찬가지다. 주소값 3819를 이용해 table에서 꺼내 쓰면 된다.
데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것, 이것이 해시 테이블의 기놈 개념이다.
이런 식으로 해시를 통해 데이터가 담길 주소값을 얻는 것은 상수 시간 내에 결정되기 때문에 테이블의 크기가 얼마가 되든 성능은 전혀 달라지지 않는다. 해시 테이블에게는 '탐색'이라는 단어가 무색할 정도로, 주소(인덱스)를 구하는 방법만 다르다 뿐이지 오히려 배열과 다름없는 요소에 대한 접근 속도를 자랑한다.
해시 테이블의 성능은 공간을 팔아 얻어낸 것이다. 특이하게도 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.
-
해시 함수
입력 값에서 테이블 내의 주소를 계산해내는 것이 해시 함수(Hash Function)이다.
나눗셈법
나눗셈법(Division Method)은 해시 함수 중에서 가장 간단한 알고리즘이다. 나눗셈법은 입력 값을 테이블의 크기로 나누고, 그 '나머지'를 테이블의 주소로 사용한다.
주소 = 입력값 % 테이블 크기
어떤 값이든 테이블의 크기로 나누면 그 나머지는 절대 테이블의 크기(n)을 넘지 않는다. 입력 값이 테이블 크기의 배수 또는 약수인 경우 해시 함수는 0을 반환하고 그렇지 않은 경우에는 최대n-1을 반환한다. 0부터 n-1 사이의 주소를 반환함을 보장하게 된다.
일반적으로 나눗셈법으로 구현된 해시 함수가 테이블 내의 공간을 효율적으로 사용하기 위해서는 테이블의 크기 n을 소수(Prime Number)로 정하는 것이 좋다고 알려져 있다. 특히 2의 제곱수와 거리가 먼 소수를 사용한 해시 함수가 좋은 성능을 낸다.
|
앞 |
뒤 |
소수 |
|
25 |
26 |
53 |
|
26 |
27 |
97 |
|
27 |
28 |
193 |
|
28 |
29 |
389 |
|
29 |
210 |
769 |
|
210 |
211 |
1543 |
|
211 |
212 |
3079 |
|
212 |
213 |
6151 |
|
213 |
214 |
12289 |
|
214 |
215 |
24593 |
|
... |
... |
... |
나눗셈법 예제 프로그램
- 예제 SimpleHashTable.h
|
#ifndef _SIMPLEHASHTABLE_H__ #define _SIMPLEHASHTABLE_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_destroyHashTable(HashTable* ht); void SHT_set(HashTable* ht, keyType key, valueType value); valueType SHT_get(HashTable* ht, keyType key);
int SHT_hash(keyType key, int tableSize);
#endif |
- 예제 SimpleHashTable.c
|
#include "SimpleHashTable.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_destroyHashTable(HashTable* ht) { free(ht->table); free(ht); } void SHT_set(HashTable* ht, keyType key, valueType value) { int addr = SHT_hash(key, ht->tableSize);
ht->table[addr].key = key; ht->table[addr].value = value; } valueType SHT_get(HashTable* ht, keyType key) { int addr = SHT_hash(key, ht->tableSize);
return ht->table[addr].value; }
int SHT_hash(keyType key, int tableSize) { return key % tableSize; } |
- 예제 main.c
|
#include "SimpleHashTable.h"
void main() { 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", 1031, SHT_get(ht, 1031));
SHT_destroyHashTable(ht); } |
자릿수 접기
나눗셈법은 알고리즘이 단순해서 이해하기 쉽다 하지만 '극한의 성능'을 갈망하는 프로그래머에게는 부족한 알고리즘이다. 서로 다른 입력 값에 대해 동일한 해시 값, 즉 해시 테이블 내의 동일한 주소를 반환할 가능성이 높다. 이것을 충돌(Collision)이라고 하는데, 설사 똑같은 해시 값이 아니더라도 해시 테이블 내의 일부 지역의 주소들을 집중적으로 반환하는 결과로 데이터들이 한 곳에 모이는 문제(이를 클러스터(Cluster)라고 함)가 발생할 가능성이 높다.
물론 충돌이나 클러스터링의 문제를 완벽하게 제거할 수 있는 해싱 알고리즘은 존재하지 않다. 하지만 문제를 일으킬 가능성을 줄인 알고리즘이 있는데 그 중 하나가 자릿수 접기(Digits Folding)이다.
자릿수 접기는 종이를 접듯이 숫자를 일정한 크기 이하의 수로 만드는 방법이다.
8129335 = 8 + 1 + 2 + 9 + 3 + 3 + 5 = 31
81 + 29 + 33 + 5 = 148
이처럼 숫자의 각 자릿수를 더해 해시 값을 만드는 것을 자릿수 접기라고 한다. 10진수의 경우 모든 수는 각 자리마다 0~9까지의 값을 가질 수 있으니, 7자리 수에 대한 '한자리씩 접기'를 하는 경우 최수 0에서 최대 63까지의 해시 값을 얻을 수 있고, '두 자리씩 접기'를 하는 경우에는 최소 0에서 최대 306까지의 해시 값을 얻을 수 있다.
자릿수 접기는 문자열을 키로 사용하는 해시 테이블에 특히 잘 어울리는 알고리즘이다. 문자열의 각 요소를 ASCII코드 번호(0~127)로 바꾸고 이 값들을 각각 더하여 접으면 문자열을 해시 테이블 내의 주소로 바꿀 수 있다.
아래는 문자열 키를 자릿수 접기 알고리즘을 통해 해시 값을 만들어 내는 코드이다.
int hash(char* key, int keyLength, int tableSize)
{
int i = 0;
int hashValue = 0;
// 문자열의 각 요소를 ASCII코드 번호로 변환하여 더한다
for( i = 0 ; i < keyLength ; i++ )
hashValue += key[i];
reutrn hashValue % tableSize;
}
그런데 이 코드는 한 가지 문제가 있다. 해시 테이블의 크기가 12289이고 문자열 키의 최대 길이가 10자리라고 한다면 해시 함수는 10 * 127 = 1,270 이므로 0 ~ 1270 사이의 주소만을 반환하게 되어 1271 ~ 12288 사이의 주소가 전혀 활용되지 않게 된다.
12289를 2진수로 표현하면 14개의 비트로 이루어진다. 반면 위 코드에 있는 hash() 함수가 반환하는 최대의 주소값은 1270인데 11개 비트만을 사용한다. 이 사실을 보면 3개의 비트는 절대 사용하지 않는다는 사실을 알 수 있다. 이 3개의 비트를 모두 활용한다면 앞의 문제를 해결할 수 있다.
hash() 함수가 남는 비트까지 모두 활용할 수 있도록 만들어 주면 된다.
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;
}
해시 함수의 한계: 충돌
해시 함수가 서로 다른 입력 값에 대해 동일한 해시 테이블 주소를 반환하는 것을 일컫어 '충돌(Collision)'이라고 한다.
어떤 해시 함수든, 그 알고리즘이 아무리 정교하게 설계되었다 하더라도 모든 입력 값에 대해 고유한 해시 값을 만들지는 못한다.
-
충돌 해결하기
해시 테이블의 충돌을 해결하는 방법에는 크게 두 가지가 잇다. 첫 번째는 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 개방 해싱(Open Hashing)이고, 또 다른 하나는 처음에 주어진 해시 테이블의 공간 안에서 문제를 해결하는 폐쇄 해싱(Closed Hashing)이다.
체이닝
체이닝(Chaining)은 해시 함수로 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법이다. 충돌이 일어나면 링크드 리스트에 사슬처럼 주렁주렁 엮는다는 의미에서 붙여진 이름이다. 체이닝 기반의 해시 테이블은 데이터 대신 링크드 리스트에 대한 포인터를 관리한다. 해시 테이블의 외부에 데이터를 저장하는 체이닝은 개발 해싱 알고리즘이다.
데이터를 해시 테이블에 삽입하고 탐색하는 연산은 새 알고리즘에 맞추어 바꿀 필요가 있다. 삽입 연산은 충돌이 앞으로 '발생할' 것을 고려해서, 삭제 연산과 탐색 연산은 충돌이 이미 '발생했을' 것을 고려해서 설계해야 한다.
-
체이닝 기반 해시 테이블의 탐색
- 찾고자 하는 목표값을 해싱하여 링크드 리스트가 저장되어 있ㄴ느 주소를 찾는다.
- 이 주소를 이요하여 해시 테이블에 저장되어 있는 링크드 리스트에 대한 포인터를 생성한다.
- 링크드 리스트의 앞에서부터 뒤까지 차례대로 이동하며 목표값이 저장되어 있는지 비교한다. 목표값과 링크드 리스트 내의 노드 값이 일치하면 해당 노드의 주소를 반환한다.
-
체이닝 기반 해시 테이블의 삽입
먼저 해시 함수를 이용해서 데이터가 삽입될 링크드 리스트의 주소를 얻어낸 후에, 링크드 리스트가 비어 있으면 데이터를 바로 삽입하고 그렇지 않은 경우에는 링크드 리스트의 '헤드 앞에' 삽입한다
새로운 데이터가 삽입될 때 충돌이 발생하면 새 데이터를 링크들 리스트의 가장 앞(즉, 헤드의 앞)에 삽입하면 된다.
- 예제 Chaining.h
-
|
#ifndef CHAINING_H__ #define CHAINING_H__
#include <stdio.h> #include <stdlib.h> #include <string.h>
typedef char* keyType; typedef char* valueType;
typedef struct tagNode { keyType key; valueType value;
tagNode* next; }NODE;
typedef NODE* list;
typedef struct tagHashTable { int tableSize; list* table; }HashTable;
HashTable* CHT_createHashTable(int tableSize); void CHT_destroyHashTable(HashTable* HT);
NODE* CHT_createNode(keyType key, valueType value); void CHT_destroyNode(NODE* node);
void CHT_set(HashTable* HT, keyType key, valueType value); valueType CHT_get(HashTable* HT, keyType key); int CHT_hash(keyType key, int keyLength, int tableSize);
void CHT_destroyList(list l);
#endif |
- 예제 Chaining.c
|
#include "Chaining.h" #pragma warning(disable:4996)
HashTable* CHT_createHashTable(int tableSize) { HashTable* HT = (HashTable*)malloc(sizeof(HashTable)); HT->table = (list*)malloc(sizeof(NODE) * tableSize);
memset(HT->table, 0, sizeof(list) * tableSize);
HT->tableSize = tableSize;
return HT; } void CHT_destroyHashTable(HashTable* HT) { // 각 링크드 리스트를 자유 저장소에서 제거하기 int i = 0; for( i = 0 ; i < HT->tableSize ; i++ ) { list l = HT->table[i]; CHT_destroyList(l); }
// 해시 테이블을 자유 저장소에서 제거하기 free(HT->table); free(HT); }
NODE* CHT_createNode(keyType key, valueType value) { NODE* node = (NODE*)malloc(sizeof(NODE));
node->key = (char*)malloc(sizeof(char*) * strlen(key) + 1); strcpy(node->key, key);
node->value = (char*)malloc(sizeof(char*) * strlen(value) + 1); strcpy(node->value, value); node->next = NULL;
return node; } void CHT_destroyNode(NODE* node) { free(node->key); free(node->value); free(node); }
void CHT_set(HashTable* HT, keyType key, valueType value) { int addr = CHT_hash(key, strlen(key), HT->tableSize); NODE* node = CHT_createNode(key, value);
// 해당 주소가 비어 있으면 if( HT->table[addr] == NULL ) { HT->table[addr] = node; } // 해당 주소가 비어있지 않으면 else { list l = HT->table[addr]; node->next = l; HT->table[addr] = node;
printf("Collision occured : key(%s), addr(%d)\n", key, addr); } } valueType CHT_get(HashTable* HT, keyType key) { // 주소를 해싱 int addr = CHT_hash(key, strlen(key), HT->tableSize);
// 해당 주소에 있는 링크드 리스트를 가져옴 list l = HT->table[addr];
list target = NULL;
while(1) { if( strcmp(l->key, key) == 0 ) { target = l; break; }
if( l->next == NULL ) break; else l = l->next; }
return target->value; } int CHT_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; }
void CHT_destroyList(list l) { if( l == NULL ) return ;
if( l->next != NULL ) CHT_destroyList(l->next);
CHT_destroyNode(l); } |
- 예제 main.c
|
#include "Chaining.h"
void main(void) { HashTable *ht = CHT_createHashTable(12289);
CHT_set(ht, "MSFT", "Microsoft"); CHT_set(ht, "JAVA", "Sun"); CHT_set(ht, "REDH", "RedHat"); CHT_set(ht, "APAC", "Apache"); CHT_set(ht, "ZYMZZ", "Unisys"); // APAC와 충돌 CHT_set(ht, "IBM", "IBM"); CHT_set(ht, "ORCL", "Oracle"); CHT_set(ht, "CSCO", "Cisco"); CHT_set(ht, "GOOG", "google"); CHT_set(ht, "YHOO", "Yahoo"); CHT_set(ht, "NOVL", "Novel");
printf("\n"); printf("key:%s, value:%s\n", "MSFT", CHT_get(ht, "MSFT")); printf("key:%s, value:%s\n", "REDH", CHT_get(ht, "REDH")); printf("key:%s, value:%s\n", "APAC", CHT_get(ht, "APAC")); printf("key:%s, value:%s\n", "ZYMZZ", CHT_get(ht, "ZYMZZ")); printf("key:%s, value:%s\n", "JAVA", CHT_get(ht, "JAVA")); printf("key:%s, value:%s\n", "IBM", CHT_get(ht, "IBM")); printf("key:%s, value:%s\n", "ORCL", CHT_get(ht, "ORCL")); printf("key:%s, value:%s\n", "CSCO", CHT_get(ht, "CSCO")); printf("key:%s, value:%s\n", "GOOG", CHT_get(ht, "GOOG")); printf("key:%s, value:%s\n", "YHOO", CHT_get(ht, "YHOO")); printf("key:%s, value:%s\n", "NOVL", CHT_get(ht, "NOVL"));
CHT_destroyHashTable(ht); } |
-
체이닝의 성능을 더 끌어올리려면?
체이닝은 원하는 데이터를 찾기 위해 순차 탐색을 해야 하는 링크드 리스트의 단점을 고스란히 갖고 있다. 해시 테이블은 '극한의 탐색'을 위해 고안되었는데 순차 탐색으로 그 성능을 제대로 발휘하지 못한다.
해시 함수의 성능이 좋지 않아 충돌이 잦은 경우에는 해시 테이블 + 이진 탐색 트리의 결합이 훌륭한 선택이 될 수 있다.
개방 주소법
개방 주소법(Open Addressing)은 충돌이 일어날 때 해시 함수에 의해 얻어진 주소가 아니더라도 얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘이다. 체이닝은 오픈 해싱 기법인 동시에 폐쇄 주소법(Closed Addressing) 알고리즘이기도 하다.
개방 주소법은 충돌이 일어나면 해시 테이블 내의 새로운 주소를 탐사(Probe)하여 충돌된 데이터를 입력하는 방식으로 동작한다.
-
선형 탐색
선형 탐색(Linear Probing)은 가장 간단한 탐사 방법이다. 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭으로 다음 주소로 이동한다. 그 주소에 다른 데이터가 있어 충돌이 발생하면 또 그 다음 주소로 이동한다. 이렇게 해서 비어 있는 주소를 찾아내면 데이터를 입력한다.
55가 입력될 때 충돌이 발생하면 고정된 폭만큼 이동하여 빈 주소를 찾는다.
-
제곱 탐색
제곱 탐사(Quadratic Probing)의 기본 개념은 선형 탐사와 비교해서 크게 다르지 않다. 선형 탐사가 다음 주소를 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어난다는 것이 다를 뿐이다.
81이 입력될때 첫번째 충돌이 일어나면 1의제곱 1만큼 이동한 후 두 번째 충돌 시 2의2제곱 4만큼 이동하여 빈 공간을 찾는다.
-
이중 해싱(Double Hasing)
클러스터를 제대로 방지할 수 있는 방법은 탐사할 주소의 규칙성을 없애버리는 길 뿐이다.
해시 함수에 키를 입력하여 얻어낸 주소에서 충돌이 일어나면 새로운 주소를 향해 이동해야 한다. 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 또 다른 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다.
int hash(int key)
{
return key % 13;
}
int hash2(int key)
{
return (key % 11) + 2;
|
-
재해싱
남은 공간이 없는 해시 테이블에서는 충돌이 많이 발생하게 된다.
재해싱(Rehashing)은 이 문제를 해결할 수 있는 방법 중의 하나 이다. 재해싱은 해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱한다.
테이블의 공간 사용률이 70 ~ 80%에 이르면 성능 저하가 나타난다고 한다. 그러니 재해싱을 이 전에 수행해야 성능 저하가 나타나는 것을 막을 수 있을 것이다.
- 예제 OpenAddressing.h
|
#ifndef _OPENADDRESSING_H_ #define _OPENADDRESSING_H_
#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 { int occupiedCount; int tableSize;
ElementType* table; }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 |
- 예제 OpenAddressing.c
|
#include "OpenAddressing.h"
#pragma warning(disable:4996)
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->tableSize = tableSize; ht->occupiedCount = 0;
return ht; } void OAHT_destroyHashTable(HashTable* ht) { // 1. 각 링크드 리스트를 자유 저장소에서 제거 int i = 0; for( i = 0 ; i < ht->tableSize ; i++ ) { OAHT_clearElement(&(ht->table[i])); }
// 2, 해시 테이블 제거 free(ht->table); free(ht); } void OAHT_clearElement(ElementType* element) { if( element->status == EMPTY ) return;
free(element->key); free(element->value); }
void OAHT_set(HashTable** ht, keyType key, valueType value) { int keyLength, addr, stepSize; double usage;
usage = (double)(*ht)->occupiedCount / (*ht)->tableSize;
// 점유율 50% 넘으면 재해싱 if( usage > 0.5 ) { OAHT_reHash(ht); }
keyLength = strlen(key); addr = OAHT_hash(key, keyLength, (*ht)->tableSize); stepSize = OAHT_hash2(key, keyLength, (*ht)->tableSize);
while( (*ht)->table[addr].status != EMPTY && strcmp((*ht)->table[addr].key, key) != 0 ) { printf("collision occured! : key(%s), addr(%d), stepSize(%d)\n", key, addr, stepSize);
addr = (addr + stepSize) % (*ht)->tableSize; }
(*ht)->table[addr].key = (keyType)malloc(sizeof(char)* (keyLength+1)); strcpy((*ht)->table[addr].key, key);
(*ht)->table[addr].value = (valueType)malloc(sizeof(char) * strlen(value)+1);
strcpy((*ht)->table[addr].value, value);
(*ht)->table[addr].status = OCCUPIED;
(*ht)->occupiedCount++;
printf("key(%s) entered address(%d)\n", key, addr); } valueType OAHT_get(HashTable* ht, keyType key) { int keyLength = strlen(key);
int addr = OAHT_hash(key, keyLength, ht->tableSize); int stepSize = OAHT_hash2(key, keyLength, ht->tableSize);
while( ht->table[addr].status != EMPTY && strcmp(ht->table[addr].key, key) != 0 ) { addr = (addr+stepSize) % ht->tableSize; }
return ht->table[addr].value; } 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; } int OAHT_hash2(keyType key, int keyLength, int tableSize) { int i = 0; int hashValue = 0;
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", newHT->tableSize);
// 이전 해시 테이블에 있던 데이털르 새 해시 테이블로 옮김 for( i = 0 ; i < (*ht)->tableSize ; i++ ) { if( oldTable[i].status == OCCUPIED ) { OAHT_set(&newHT, oldTable[i].key, oldTable[i].value); } }
// 이전 해시 테이블 해제 OAHT_destroyHashTable( (*ht) );
// ht포인터에 새로운 해시 테이블 주소 대입 (*ht) = newHT; } |
- 예제 main.c
|
#include "OpenAddressing.h"
void main() { HashTable *ht = OAHT_createHashTable(11);
OAHT_set(&ht, "MSFT", "Microsoft"); OAHT_set(&ht, "JAVA", "Sun"); OAHT_set(&ht, "REDH", "RedHat"); OAHT_set(&ht, "APAC", "Apache"); OAHT_set(&ht, "ZYMZZ", "Unisys"); // APAC와 충돌 OAHT_set(&ht, "IBM", "IBM"); OAHT_set(&ht, "ORCL", "Oracle"); OAHT_set(&ht, "CSCO", "Cisco"); OAHT_set(&ht, "GOOG", "google"); OAHT_set(&ht, "YHOO", "Yahoo"); OAHT_set(&ht, "NOVL", "Novel");
printf("\n"); printf("key:%s, value:%s\n", "MSFT", OAHT_get(ht, "MSFT")); printf("key:%s, value:%s\n", "REDH", OAHT_get(ht, "REDH")); printf("key:%s, value:%s\n", "APAC", OAHT_get(ht, "APAC")); printf("key:%s, value:%s\n", "ZYMZZ", OAHT_get(ht, "ZYMZZ")); printf("key:%s, value:%s\n", "JAVA", OAHT_get(ht, "JAVA")); printf("key:%s, value:%s\n", "IBM", OAHT_get(ht, "IBM")); printf("key:%s, value:%s\n", "ORCL", OAHT_get(ht, "ORCL")); printf("key:%s, value:%s\n", "CSCO", OAHT_get(ht, "CSCO")); printf("key:%s, value:%s\n", "GOOG", OAHT_get(ht, "GOOG")); printf("key:%s, value:%s\n", "YHOO", OAHT_get(ht, "YHOO")); printf("key:%s, value:%s\n", "NOVL", OAHT_get(ht, "NOVL"));
OAHT_destroyHashTable(ht); } |
'책정리 > 뇌를 자극하는 알고리즘' 카테고리의 다른 글
| 10장 문자열 검색 (0) | 2015.03.31 |
|---|---|
| 9장 그래프 (0) | 2015.03.29 |
| 7장 우선순위 큐와 힙 (0) | 2015.03.25 |
| 6장 탐색 (0) | 2015.03.25 |
| 5장 정렬 (0) | 2015.03.23 |