[알고리즘/자료구조] 해시 테이블(Hash Table)

해시 테이블

해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.

소스

#include <stdio.h>
#include <iostream>
#include <conio.h>
 
using namespace std;
 
class HashNode
{
public:
   int key;
   int value;
};
class HashTable
{
public:
   int size;
   HashNode* Table;
 
   HashTable* create_HashTable(int initialize);
   void set_HashTable(HashTable* HT, int key, int value);
   int get_HashTable(HashTable* HT, int key);
   int Hash(int key, int size);
};
 
HashTable* create_HashTable(int initialize)
{
   HashTable* HT = (HashTable*)malloc(sizeof(HashTable));
   HT -> Table = (HashNode*)malloc(sizeof(HashNode) * initialize);
   HT -> size = initialize;
 
   return HT;
}
 
int Hash(int key, int size)
{
    int address = key % size;
    return address;
}
 
void set_HashTable(HashTable* HT, int key, int value)
{
   int address = Hash(key, HT -> size);
 
   HT -> Table[address].key = key;
   HT -> Table[address].value = value;
}
 
int get_HashTable(HashTable* HT, int key)
{
   int address = Hash(key, HT -> size);
 
   return HT -> Table[address].value;
}
 
void main( void )
{
   HashTable* HT = create_HashTable(1323);
 
   set_HashTable(HT, 123, 82374);
   set_HashTable(HT, 13, 756);
   set_HashTable(HT, 193, 65);
   set_HashTable(HT, 3583, 91);
   set_HashTable(HT, 167, 107);
   set_HashTable(HT, 33, 0);
   set_HashTable(HT, 423, 3);
   set_HashTable(HT, 1654, 568);
   set_HashTable(HT, 773, 15234);
 
   cout << " Key : [13] Value : [" << get_HashTable(HT,13) <<"]" << endl;
   cout << " Key : [33] Value : [" << get_HashTable(HT,33) <<"]" << endl;
   cout << " Key : [123] Value : [" << get_HashTable(HT,123) <<"]" << endl;
   cout << " Key : [167] Value : [" << get_HashTable(HT,167) <<"]" << endl;
   cout << " Key : [193] Value : [" << get_HashTable(HT,193) <<"]" << endl;
   cout << " Key : [423] Value : [" << get_HashTable(HT,423) <<"]" << endl;
   cout << " Key : [773] Value : [" << get_HashTable(HT,773) <<"]" << endl;
   cout << " Key : [1654] Value : [" << get_HashTable(HT,1654) <<"]" << endl;
   cout << " Key : [3583] Value : [" << get_HashTable(HT,3583) <<"]" << endl;
 
   getch();
}

결과화면

출처

위키피디아

https://en.wikipedia.org/wiki/Hash_table